Metaheuristic solution of the two-dimensional strip packing problem

[摘要] ENGLISH ABSTRACT: In the two-dimensional strip packing problem, the objective is to pack a set of rectangular itemsin a non-overlapping manner into a single, rectangular object ofxed width but unlimited height,such that the resulting height of the packed items is a minimum. This problem has a wide rangeof 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 andmetaheuristic techniques | has been the major concern of most strip packing-related researchdue to the complexity and combinatorial nature of the problem.A new systematic way of comparing the relative performances of strip packing algorithms isintroduced in this dissertation. A large, representative set of strip packing benchmark instancesfrom various repositories in the literature is clustered into di erent classes of test problemsbased on their underlying features. The various strip packing algorithms considered are all implementedon the same computer, and their relative e ectiveness is contrasted for the di erentdata categories. More speci cally, the aim in this dissertation is to study the e ect of characteristicsinherent to the benchmark instances employed in comparisons of the relative performancesof various strip packing algorithms, with a speci c view to develop decision support capable ofidentifying the most suitable algorithms for use in the context of speci c classes of strip packingproblem instances.Two improved strip packing metaheuristics are also proposed in this dissertation. These algorithmshave 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 metaheuristicsfrom the literature in terms of both solution quality achieved and execution time required in thecontext of the clustered benchmark data. It is found that the new algorithms indeed comparefavourably with other existing strip packing metaheuristics in the literature. It is also foundthat speci c properties of the test problems a ect the solution qualities and relative rankingsachieved by the various packing algorithms.One of the most importantndings in this dissertation is that the characteristics of the benchmarkinstances considered for comparative algorithmic study purposes should be taken intoaccount in the future in order to avoid biased research conclusions.

[发布机构] Stellenbosch University