Metaheuristic solution of the two-dimensional strip packing problem
Date
2018-12
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
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.
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.
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.
Description
Thesis (PhD)--Stellenbosch University, 2018.
Keywords
Metals -- Cutting -- Problems, Metaheuristics, Cluster analysis, UCTD, Strip Packing Problem