An algorithmic approach to the 2D oriented strip packing problem
| dc.contributor.advisor | Van Vuuren, J. H. | en_ZA |
| dc.contributor.author | Ntene, Nthabiseng | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics. | en_ZA |
| dc.date.accessioned | 2012-08-27T11:33:32Z | |
| dc.date.available | 2012-08-27T11:33:32Z | |
| dc.date.issued | 2007-12 | |
| dc.description | Dissertation (PhD) -- University of Stellenbosch, 2007. | |
| dc.description.abstract | 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. | |
| dc.description.abstract | AFRIKAANSE OPSOMMING: Inpakkingsproblerne in die nywerheid kan gewoonlik in een van twee groepe geklassifiseer word, naarnlik houer inpakkingsprobleme en strook inpakkingsprobleme. Eersgenoernde bestaan daaruit dat 'n lys voorwerpe in die kleinste rnoontlike aantal houers van vaste grootte ingepak word, terwyl in die laasgenoernde klas voorwerpe in 'n enkele houer of strook van vaste wydte, rnaar onbeperkte hoogte ingepak word rnet die doel orn die totale inpakkingshoogte te rninirneer. In beide klasse problerne rnag die voorwerpe nie oorvleuel nie. Die hele lys voorwerpe rnag vooraf bekend wees, in welke geval die problem as 'n afiyn probleern bekend staan. In aanlyn problerne, daarenteen, word die eienskappe van die volgende voorwerp in die lys eers bekend sodra die vorige voorwerp ingepak is. Problerne waar gedeeltelike inligting orntrent die lys voorwerpe wat ingepak rnoet word (soos byvoorbeeld 'n sortering van een of ander aard) vooraf bekend is, word bykans aanlyn problerne genoern. Afiyn inpakkingsproblerne rnag deur rniddel van eksakte algoritrnes, horisontale vlak heuristieke of platvlak heuristieke opgelos word, terwyl aanlyn inpakkingsproblerne tipies deur rniddel van horisontale vlak heuristieke, rak heuristieke of platvlak heuristieke opgelos rnag word. In horisontale vlak heuristieke word horisontale vlakke in die strook gevorrn, word die voorwerpe op hierdie vlakke gepak en is die vlakhoogtes gelyk aan die hoogste voorwerpe wat op die betrokke vlakke gepak is, terwyl by rak heuristieke die strook ook in horisontale vlakke verdeel word, rnaar rnet die verskil dat die vlakhoogtes hoer is as die hoogste voorwerpe wat op die betrokke vlakke gepak is, orn voorsiening te rnaak vir die rnoontlikheid dat selfs hoer voorwerpe later op die vlakke gepak rnag word. By platvlak heuristieke word die strook glad nie verdeel nie, en rnag voorwerpe enige plek in die strook gepak word. Beide aanlyn en afiyn twee-dirnensionele strook inpakkingsproblerne word in hierdie proefskrif beskou, waar die voorwerpe reghoeke is, en nie geroteer rnag word nie. 'n Algoritrniese benadering word gevolg waar verskeie algoritrnes (heuristies en eksak) gelrnplernenteer word. 'n Nuwe afiyn horisontale vlak heuristiek word ontwikkel wat poog orn die beskikbare vertikale spasie binne elke vlak volledig te benut. Vir aanlyn problerne word 'n nuwe benadering tot die ooplaat van vertikale spasie in rak heuristieke ook voorgestel. 'n Nuwe platvlak heuristiek word ook daargestel. Die studie het ten doel orn te bepaal watter van die (nuwe en bekende) heuristieke die beste gepas is vir verskillende twee-dirnensionele strook inpakkingsprobleern gevalle. ·werklike strook inpakkingsprobleern gevalle behels gewoonlik die inpakking van 'n groot hoeveelheid voorwerpe-daarorn ontstaan die behoefte orn 'n gerekenariseerde besluitnerningsteunstelsel. So 'n stelsel, waarin al die algoritrnes wat in hierdie proefskrif beskryf en getoets is, word ook daargestel. | |
| dc.format.extent | 180 pages : illustrations | |
| dc.identifier.uri | http://hdl.handle.net/10019.1/50676 | |
| dc.language.iso | en_ZA | |
| dc.publisher | Stellenbosch : Stellenbosch University | |
| dc.rights.holder | Stellenbosch University | |
| dc.subject | Packaging | en_ZA |
| dc.subject | Algorithms | en_ZA |
| dc.subject | Dissertations -- Logistics | en_ZA |
| dc.title | An algorithmic approach to the 2D oriented strip packing problem | en_ZA |
| dc.type | Thesis |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- ntene_algorithmic_2007.pdf
- Size:
- 12.63 MB
- Format:
- Adobe Portable Document Format
- Description: