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

被引:54
作者
Bennell, Julia A. [1 ]
Lee, Lai Soon [2 ]
Potts, Chris N. [3 ]
机构
[1] Univ Southampton, Sch Management, Southampton SO17 1BJ, Hants, England
[2] Univ Putra Malaysia, Dept Math, Serdang 43400, Selangor, Malaysia
[3] Univ Southampton, Sch Math, Southampton SO17 1BJ, Hants, England
基金
英国工程与自然科学研究理事会;
关键词
Cutting and packing; Two-dimensional bin packing; Due date; Scheduling; Genetic algorithms; COMBINED CUTTING-STOCK; LOT-SIZING PROBLEM; ORTHOGONAL PACKING; HEURISTIC ALGORITHMS; TABU-SEARCH;
D O I
10.1016/j.ijpe.2013.04.040
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
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. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码:547 / 560
页数:14
相关论文
共 50 条
[41]   Single batch processing machine scheduling with two-dimensional bin packing constraints [J].
Li, Xueping ;
Zhang, Kaike .
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2018, 196 :113-121
[42]   A hybrid evolutionary algorithm for the two-dimensional packing problem [J].
Kierkosz, Igor ;
Luczak, Maciej .
CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 2014, 22 (04) :729-753
[43]   A simple randomized algorithm for two-dimensional strip packing [J].
Yang, Shuangyuan ;
Han, Shuihua ;
Ye, Weiguo .
COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (01) :1-8
[44]   Real-Polarized Genetic Algorithm for the Three-Dimensional Bin Packing Problem [J].
Dornas, Andre Homem ;
Cruzeiro Martins, Flavio Vinicius ;
Machry Sarubbi, Joao Fernando ;
Wanner, Elizabeth Fialho .
PROCEEDINGS OF THE 2017 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'17), 2017, :785-792
[45]   The Two-Dimensional Finite Bin Packing Problem. Part II: New lower and upper bounds [J].
Marco A. Boschetti ;
Aristide Mingozzi .
Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2003, 1 :135-147
[46]   A two-stage intelligent search algorithm for the two-dimensional strip packing problem [J].
Leung, Stephen C. H. ;
Zhang, Defu ;
Sim, Kwang Mong .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 215 (01) :57-69
[47]   The Two-Dimensional Finite Bin Packing Problem. Part II: New lower and upper bounds [J].
Boschetti, Marco A. ;
Mingozzi, Aristide .
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2003, 1 (02) :135-147
[48]   A column generation-based algorithm for two-stage, two-dimensional bin packing problem with a variant variable sized constraint [J].
Zhang, Qi ;
Liu, Shixin ;
Qin, Shujin ;
Shi, Yarong .
PROCEEDINGS OF THE 36TH CHINESE CONTROL CONFERENCE (CCC 2017), 2017, :2841-2845
[49]   Applying triple-block patterns in solving the two-dimensional bin packing problem [J].
Cui, Yi-Ping ;
Yao, Yi ;
Zhang, Defu .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2018, 69 (03) :402-415
[50]   A new exact method for the two-dimensional bin-packing problem with fixed orientation [J].
Clautiaux, Francois ;
Carlier, Jacques ;
Moukrim, Aziz .
OPERATIONS RESEARCH LETTERS, 2007, 35 (03) :357-364