Browsing by Author "Rakotonirainy, Rosephine Georgina"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Metaheuristic solution of the two-dimensional strip packing problem
    (Stellenbosch : Stellenbosch University, 2018-12) Rakotonirainy, Rosephine Georgina; Van Vuuren, J. H.; Stellenbosch University. Faculty of Engineering. Dept. of Industrial Engineering.
    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.