An Effective Scoring-Based Metaheuristic Algorithm for Rectilinear Block Placement

Due to the new packaging schemes such as multi-project wafer (MPW), the shape of integrated circuit blocks becomes more flexible and the demand for rectilinear block placement is rising. MPW can be modeled as the rectilinear block placement problem, which requires to place a set of L/T/U-shaped rectilinear blocks on a plane without overlapping. The objective is to minimize the area of the enveloping rectangle with the aspect ratio of the envelope close to 1:1. This paper presents an effective scoring-based metaheuristic algorithm (SMA) for the MPW problem. A skyline heuristic is proposed to find a suitable block for the lowest and leftmost space for the rectilinear block placement problem. Comparing to the previous algorithms for rectangle packing, our algorithm considers the characteristics of L/T/U-shaped blocks and different orientations in the scoring strategies for block selection. In order to improve the placement sequence, swapping and shifting operations are incorporated to iteratively change the current sequence. Computational experiments were conducted on ten benchmark instances from the Integrated Circuit EDA Elite Challenge 2020 (ICEEC 2020). The experimental results show that the average filling ratio of our algorithm is around 95% which demonstrates the effectiveness of SMA.