GUILLOTINEABLE BIN PACKING - A GENETIC APPROACH

Autor(en): KROGER, B
Stichwörter: 2-DIMENSIONAL BIN PACKING; Business & Economics; Management; Operations Research & Management Science; PARALLEL GENETIC ALGORITHM; SIMULATED ANNEALING
Erscheinungsdatum: 1995
Herausgeber: ELSEVIER SCIENCE BV
Journal: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volumen: 84
Ausgabe: 3
Startseite: 645
Seitenende: 661
Zusammenfassung: 
For a constrained, two-dimensional Bin Packing Problem this paper introduces a sequential and a parallel genetic algorithm. A guillotine constraint is directly reflected by the encoding mechanism and thus is ensured at any stage of the algorithm. As an enlargement, the concept of meta-rectangles is proposed and incorporated into the algorithm. Each meta-rectangle temporarily fixes (rectangular) hyperplanes of existing solutions. By this the hierarchical structure of guillotineable packing schemes is exploited to reduce the problem's complexity without affecting the quality of the generated solutions. The presented algorithm is able to generate almost optimal packing schemes and even in its sequential version the algorithm empirically is proven to be superior to different approaches like random search or simulated annealing.
ISSN: 03772217
DOI: 10.1016/0377-2217(95)00029-P

Show full item record

Page view(s)

2
Last Week
0
Last month
0
checked on Mar 1, 2024

Google ScholarTM

Check

Altmetric