1.School of business administration, Northeast University;2.College of Information Science and Engineering, Northeastern University
A four-block layout and its generation algorithm were proposed for unconstrained two-dimensional plate guillotine cutting problem of rectangular items.With this layout the plate was divided into four blocks, and each block was arranged recursively. A row of the same kind of rectangular items was selected and placed them in the left lower corner of the block. Along the upper and right boundaries of this row of rectangular items, the rest of the block was divided into two smaller sub blocks for further recursive investigation. Firstly, the recursive layout of rectangular items in all possible size blocks was generated by dynamic programming algorithm at one time; then the optimal four-block layout of rectangular items on the plate was determined by implicit enumeration algorithm.The algorithm was compared with several typical literature algorithms by using literature benchmark examples and random examples in accordance with the actual situation. The experimental results show that the time complexity of this algorithm is lower than or equal to the literature algorithm, and the value of layout is higher than that of literature algorithm.