| Given a set of rectangular items and a strip of fixed width and variable height,strip packing problem is to pack all the items into the strip without overlapping and the goal is to minimize the height of used strip.Strip packing problem is a typical combinatorial optimization problem.This thesis presents two heuristic algorithms for the two-dimensional strip packing problem.These two algorithms are both based on skyline.The key to skyline algorithms is to choose an appropriate item to place on the skyline.The general method is to score the items and skyline.The first algorithm extends Leung and Zhang's[1]rule R by adding a new parameter a.The second algorithm relies on a scoring function,which is derived from reinforcement learning networks.This thesis compares the proposed two algorithms with three algorithms.The exper-iment used two data sets.These two data sets are generated by Bortfeldt and Gehring's[2]algorithm.The experiment shows that the two algorithms outperform the current known algorithms. |
