Metaheuristic solution of the two-dimensional strip packing problem
| dc.contributor.advisor | Van Vuuren, J. H. | en_ZA |
| dc.contributor.author | Rakotonirainy, Rosephine Georgina | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Engineering. Dept. of Industrial Engineering. | en_ZA |
| dc.date.accessioned | 2018-10-12T08:14:08Z | |
| dc.date.accessioned | 2018-12-07T06:47:51Z | |
| dc.date.available | 2018-10-12T08:14:08Z | |
| dc.date.available | 2018-12-07T06:47:51Z | |
| dc.date.issued | 2018-12 | |
| dc.description | Thesis (PhD)--Stellenbosch University, 2018. | en_ZA |
| dc.description.abstract | ENGLISH ABSTRACT: In the two-dimensional strip packing problem, the objective is to pack a set of rectangular items in a non-overlapping manner into a single, rectangular object of xed width but unlimited height, such that the resulting height of the packed items is a minimum. This problem has a wide range of applications, especially in the wood, glass and paper industries. Over the past few years, the development of fast and e ective packing algorithms | mainly employing heuristic and metaheuristic techniques | has been the major concern of most strip packing-related research due to the complexity and combinatorial nature of the problem. A new systematic way of comparing the relative performances of strip packing algorithms is introduced in this dissertation. A large, representative set of strip packing benchmark instances from various repositories in the literature is clustered into di erent classes of test problems based on their underlying features. The various strip packing algorithms considered are all implemented on the same computer, and their relative e ectiveness is contrasted for the di erent data categories. More speci cally, the aim in this dissertation is to study the e ect of characteristics inherent to the benchmark instances employed in comparisons of the relative performances of various strip packing algorithms, with a speci c view to develop decision support capable of identifying the most suitable algorithms for use in the context of speci c classes of strip packing problem instances. Two improved strip packing metaheuristics are also proposed in this dissertation. These algorithms have been designed in such a way as to improve on the e ectiveness of existing algorithms. The two newly proposed algorithms are compared with a representative sample of metaheuristics from the literature in terms of both solution quality achieved and execution time required in the context of the clustered benchmark data. It is found that the new algorithms indeed compare favourably with other existing strip packing metaheuristics in the literature. It is also found that speci c properties of the test problems a ect the solution qualities and relative rankings achieved by the various packing algorithms. One of the most important ndings in this dissertation is that the characteristics of the benchmark instances considered for comparative algorithmic study purposes should be taken into account in the future in order to avoid biased research conclusions. | en_ZA |
| dc.description.abstract | AFRIKAANSE OPSOMMING: In die twee-dimensionele strookinpakkingsprobleem moet 'n versameling reghoekige voorwerpe op 'n nie-oorvleuelende wyse in 'n enkele reghoekige voorwerp van vaste breedte, maar onbeperkte hoogte, gepak word sodat die resulterende hoogte van die ingepakte voorwerpe 'n minimum is. Hierdie probleem het 'n wye verskeidenheid toepassings, veral in die hout-, glasen papierbedrywe. Oor die afgelope paar jaar het die ontwikkeling van vinnige en doeltre ende inpakkingsalgoritmes | wat hoofsaaklik berus op heuristiese en metaheuristiese tegnieke | aanleiding gegee tot die meeste strookinpakkings-verwante navorsing weens die kompleksiteit en kombinatoriese aard van die probleem. 'n Nuwe sistematiese manier word in hierdie proefskrif daargestel vir die relatiewe vergelyking van die doeltre endheid van strookinpakkingsalgoritmes. 'n Groot, verteenwoordigende versameling strookinpakkingstoetsprobleme uit verskillende versamelings in die literatuur word in 'n aantal klasse toetsprobleme op grond van hul onderliggende kenmerke gegroepeer. Die onderskeie strookinpakkingsalgoritmes wat oorweeg word, word almal op dieselfde rekenaar ge mplementeer, en hul relatiewe doeltre endhede word in die konteks van hierdie verskillende datakategorie e vergelyk. Die doel van hierdie proefskrif is om die e ek van eienskappe onderliggend aan die toetsprobleme wat tydens die relatiewe vergelyking van verskeie strookinpakkingsalgoritmes ingespan word, te bestudeer, met die oog op die ontwikkeling van besluitsteun ten opsigte van die mees gepaste algoritmes vir gebruik in die konteks van spesi eke klasse strookinpakkingsprobleemgevalle. Twee verbeterde strookinpakkingsmetaheuristieke word ook in hierdie proefskrif voorgestel. Hierdie algoritmes is ontwerp om op die doeltre endheid van bestaande algoritmes te verbeter. Die twee nuwe algoritmes word met 'n verteenwoordigende steekproef van metaheuristieke uit die literatuur ten opsigte van beide oplossingskwaliteit behaal en uitvoeringstyd vereis, in die konteks van die gegroepeerde toetsdata, vergelyk. Daar word bevind dat die nuwe algoritmes inderdaad gunstig vergelyk met ander bestaande strookinpakkingsmetaheuristieke in die literatuur. Daar word ook bevind dat spesi eke eienskappe van die toetsdata die oplossingskwaliteit en relatiewe prestasie van die verskillende algoritmes be nvloed. Een van die belangrikste bevindings in hierdie proefskrif is dat daar in die toekoms rekening gehou moet word met die eienskappe van toetsprobleme wat vir vergelykende algoritmiese studiedoeleindes ingespan word om sodoende bevooroordeelde navorsingsgevolgtrekkings te vermy. | af_ZA |
| dc.format.extent | 223 pages : illustrations | en_ZA |
| dc.identifier.uri | http://hdl.handle.net/10019.1/104853 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Stellenbosch : Stellenbosch University | en_ZA |
| dc.rights.holder | Stellenbosch University | en_ZA |
| dc.subject | Metals -- Cutting -- Problems | en_ZA |
| dc.subject | Metaheuristics | en_ZA |
| dc.subject | Cluster analysis | en_ZA |
| dc.subject | UCTD | en_ZA |
| dc.subject | Strip Packing Problem | en_ZA |
| dc.title | Metaheuristic solution of the two-dimensional strip packing problem | en_ZA |
| dc.type | Thesis | en_ZA |