UPM Institutional Repository

A genetic algorithm for two-dimensional bin packing with due dates


Bennell, Julia A. and Lee, Lai Soon and Potts, Chris N. (2013) A genetic algorithm for two-dimensional bin packing with due dates. International Journal of Production Economics, 145 (2). pp. 547-560. ISSN 0925-5273


This paper considers a new variant of the two-dimensional bin packing problem where each rectangle is assigned a due date and each bin has a fixed processing time. Hence the objective is not only to minimize the number of bins, but also to minimize the maximum lateness of the rectangles. This problem is motivated by the cutting of stock sheets and the potential increased efficiency that might be gained by drawing on a larger pool of demand pieces by mixing orders, while also aiming to ensure a certain level of customer service. We propose a genetic algorithm for searching the solution space, which uses a new placement heuristic for decoding the gene based on the best fit heuristic designed for the strip packing problems. The genetic algorithm employs an innovative crossover operator that considers several different children from each pair of parents. Further, the dual objective is optimized hierarchically with the primary objective periodically alternating between maximum lateness and number of bins. As a result, the approach produces several non-dominated solutions with different trade-offs. Two further approaches are implemented. One is based on a previous Unified Tabu Search, suitably modified to tackle this revised problem. The other is randomized descent and serves as a benchmark for comparing the results. Comprehensive computational results are presented, which show that the Unified Tabu Search still works well in minimizing the bins, but the genetic algorithm performs slightly better. When also considering maximum lateness, the genetic algorithm is considerably better.

Download File

PDF (Abstract)
A genetic algorithm for two.pdf

Download (85kB) | Preview

Additional Metadata

Item Type: Article
Divisions: Faculty of Science
DOI Number: https://doi.org/10.1016/j.ijpe.2013.04.040
Publisher: Elsevier
Keywords: Cutting and packing; Two-dimensional bin packing; Due date; Scheduling; Genetic algorithms.
Depositing User: Umikalthom Abdullah
Date Deposited: 24 Sep 2014 00:39
Last Modified: 25 Aug 2015 06:42
Altmetrics: http://www.altmetric.com/details.php?domain=psasir.upm.edu.my&doi=10.1016/j.ijpe.2013.04.040
URI: http://psasir.upm.edu.my/id/eprint/30331
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item