Department of Logistics

Permanent URI for this community

https://scholar.sun.ac.za/handle/10019.1/71

Browse

Browsing Department of Logistics by Subject "Algorithms"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    An algorithmic approach to the 2D oriented strip packing problem
    (Stellenbosch : Stellenbosch University, 2007-12) Ntene, Nthabiseng; Van Vuuren, J. H.; Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics.
    ENGLISH ABSTRACT: Packing problems in industry may be categorised into the two classes of bin packing and strip packing problems. The former involves packing items into the minimum number of fixed sized bins, while in the latter the items are packed into a single open-ended bin (referred to as a strip) such that the total packing height is minimised. The items in both problem categories may not overlap. The entire set of items may be known in advance in which case the problem is referred to as an offiine problem. On the other hand, in online packing problems, only one item is available at a time and the next item only becomes available once the current item has been packed. Problems where some information about the items to be packed (such as a sorting) is available in advance are referred to as almost online packing problems. Offiine strip packing problems may be solved using exact algorithms, level heuristics or plane heuristics while online packing problems may be solved using level heuristics, shelf heuristics or plane heuristics. In level heuristics the strip is divided into horizontal levels whose heights are equal to the heights of the tallest items packed on the levels, whereas in shelf algorithms the strip is also partitioned into horizontal levels, but with additional space above the tallest rectangles on the levels to cater for future variation of item heights. On the other hand, in plane 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 in this dissertation, and the rectangles may not be rotated. An algorithmic approach is employed whereby several algorithms (heuristic and exact) are implemented. A new offl.ine level algorithm is introduced which seeks to fully utilise available space within a level. For online packing problems, a new approach is proposed when creating additional space via shelf algorithms. A new online plane algorithm is also presented. The study aims to find (among the new and a host of known algorithms) the best algorithm to use for different instances of two-dimensional strip packing problems. In reality, such problems often involve a large number of items-therefore the need arises for a computerised decision support system. Such a system, implementing all the (known and new) algorithms described and tested is also presented in this dissertation.