I.Introduction Floorplanning is an essential step in the hierarchical physical design of deep sub-micron very large scale integration(VLSI)circuits.It involves planning the positions and shapes of a set of blocks on a chip to optimize circuit performances.Blocks must be placed without being overlapped.As the technology moves into the deep sub-micron era,circuit sizes and complexities are growing rapidly and floorplanning has become even more important than it was before.Although floorplanning has been studied extensively,most previous works used simulated annealing (SA)as the search algorithm and handled rectilinear blocks by partitioning them into a set of rectangular sub-blocks.Therefore,it is still challenging and practically useful to find a nonslicing floorplan representation that is not only suitable for evolutionary algorithms (EAs)because of their high potential,but can also handle both rectangular and rectilinear blocks,similarly and simultaneously,without partitioning rectilinear blocks into sub-blocks.This paper presents the moving block sequence(MBS)as a new nonslicing floorplan representation to meet the above requirements. Our idea of the MBS originates from the observation that placing blocks on a chip has some similarities to playing the game,Tetris As in Tetris we place blocks on a chip,one by one.Each block starts from an initial position and moves on the chip,until it reaches an appropriate position.In Tetris each block always appears on the top of the screen,and it is the players who find an appropriate position for each block during the descending process.In the MBS,on the other hand,four initial positions are designed from where the blocks could be moved to other places,according to the move rules. An MBS is designed to be composed of two tuples,one denoting the permutation of3 I. Introduction Floorplanning is an essential step in the hierarchical physical design of deep sub-micron very large scale integration (VLSI) circuits. It involves planning the positions and shapes of a set of blocks on a chip to optimize circuit performances. Blocks must be placed without being overlapped. As the technology moves into the deep sub-micron era, circuit sizes and complexities are growing rapidly and floorplanning has become even more important than it was before. Although floorplanning has been studied extensively, most previous works used simulated annealing (SA) as the search algorithm and handled rectilinear blocks by partitioning them into a set of rectangular sub-blocks. Therefore, it is still challenging and practically useful to find a nonslicing floorplan representation that is not only suitable for evolutionary algorithms (EAs) because of their high potential, but can also handle both rectangular and rectilinear blocks, similarly and simultaneously, without partitioning rectilinear blocks into sub-blocks. This paper presents the moving block sequence (MBS) as a new nonslicing floorplan representation to meet the above requirements. Our idea of the MBS originates from the observation that placing blocks on a chip has some similarities to playing the game, Tetris®. As in Tetris®, we place blocks on a chip, one by one. Each block starts from an initial position and moves on the chip, until it reaches an appropriate position. In Tetris®, each block always appears on the top of the screen, and it is the players who find an appropriate position for each block during the descending process. In the MBS, on the other hand, four initial positions are designed from where the blocks could be moved to other places, according to the move rules. An MBS is designed to be composed of two tuples, one denoting the permutation of