An algorithmic approach to the 2D oriented strip packing problem

[摘要] ENGLISH ABSTRACT: Packing problems in industry may be categorised into the two classes of bin packing and strippacking problems. The former involves packing items into the minimum number of fixed sizedbins, while in the latter the items are packed into a single open-ended bin (referred to as astrip) such that the total packing height is minimised. The items in both problem categoriesmay not overlap. The entire set of items may be known in advance in which case the problem isreferred to as an offiine problem. On the other hand, in online packing problems, only one itemis available at a time and the next item only becomes available once the current item has beenpacked. Problems where some information about the items to be packed (such as a sorting) isavailable in advance are referred to as almost online packing problems.Offiine strip packing problems may be solved using exact algorithms, level heuristics or planeheuristics while online packing problems may be solved using level heuristics, shelf heuristicsor plane heuristics. In level heuristics the strip is divided into horizontal levels whose heightsare equal to the heights of the tallest items packed on the levels, whereas in shelf algorithmsthe strip is also partitioned into horizontal levels, but with additional space above the tallestrectangles on the levels to cater for future variation of item heights. On the other hand, inplane algorithms, the strip is not partitioned-items may be packed anywhere within the strip.Both online and offl.ine two-dimensional rectangle strip packing problems are considered inthis dissertation, and the rectangles may not be rotated. An algorithmic approach is employedwhereby several algorithms (heuristic and exact) are implemented. A new offl.ine level algorithmis introduced which seeks to fully utilise available space within a level. For online packingproblems, a new approach is proposed when creating additional space via shelf algorithms. Anew online plane algorithm is also presented. The study aims to find (among the new and a hostof known algorithms) the best algorithm to use for different instances of two-dimensional strippacking problems. In reality, such problems often involve a large number of items-thereforethe need arises for a computerised decision support system. Such a system, implementing allthe (known and new) algorithms described and tested is also presented in this dissertation.

[发布机构] Stellenbosch University