Extending Two-Dimensional Bin Packing Problem: Consideration of Priority for Items

Document Type: Research Paper

Authors

Industrial Engineering Department, Faculty of Engineering, University of Tehran, P.O. Box: 11155/4563, Tehran, Iran.

Abstract

In this paper a two-dimensional non-oriented guillotine bin packing problem is studied when items have different priorities. Our objective is to maximize the total profit which is total revenues minus costs of used bins and wasted area. A genetic algorithm is developed to solve this problem where a new coding scheme is introduced. To evaluate the performance of the proposed GA, first an upper bound is presented. Then, a series of computational experiments are conducted to evaluate the quality of GA solutions comparing with upper bound values. From the computational analysis, it appears that the GA algorithm is able to give good solutions.

Keywords

Main Subjects


[1] Berkey J.O., Wang P.Y. (1987), Two-dimensional finite bin packing algorithms; Journal of the
Operational Research Society 38; 423-429.
[2] Correa J.R. (2004), Near-optimal solutions to two-dimensional bin packing with 90° rotations;
Electronic Notes in Discrete Mathematics 18; 89–95.
[3] Correa J.R. (2006), Resource augmentation in two-dimensional packing with orthogonal rotations;
Operations Research Letters 34; 85–93.
[4] Davis L. (1985), Applying adaptive search algorithms to epistatic domains; Proceedings of the 9th Int.
Joint Conference on Artificial Intelligence; 162-164.
[5] Dyckhoff H. (1990), A typology of cutting and packing problems; European Journal of Operational
Research 44; 145–159.
[6] Fritsch A., Vornberger O. (1995), Cutting Stock by Iterated Matching; Operations Research
Proceedings, Selected Papers of the Int. Conf. on OR 94, U. Derigs, A. Bachem, A. Drexl (eds);
Springer Verlag; 92-97.
[7] Hopper E., Turton B. (1997), Application of Genetic Algorithms to Packing Problems: A Review;
Proceedings of the 2nd On-line World Conference on Soft Computing in Engineering Design and
Manufacturing; Springer Verlag, London; 279-288.
[8] Kröger B. (1995), Guillotineable bin packing: A genetic approach; European Journal of Operational
Research 84; 645–661.
[9] Lodi A., Martello S., Vigo D. (1998), Neighborhood search algorithm for the guillotine non-oriented
two-dimensional bin packing problem; In S. Voss, S. Martello, L.H Osman, and C. Roucairol, editors,
Meta-Heuristics: Advances and Trends in Local search Paradigms for optimization; Kluwer Academic
Publishers, Boston; 125-139.
[10] Lodi A., Martello S., Vigo D. (1999), Heuristic and metaheuristic approaches for a class of two
Dimensional Bin Packing Problems; INFORMS J. Comput 11; 345–357.
[11] Lodi A., Martello S., Vigo D. (2002), Recent advances on two-dimensional bin packing problems;
Discrete Applied Mathematics 123; 379-396.
[12] Lodi A., Martello S., Vigo D. (2004), TSpack: A Unified Tabu Search Code for Multi-Dimensional
Bin Packing Problems; Annals of Operations Research 131; 203-213.
[13] Martello S., Vigo D. (1998), Exact solution of the two-dimensional finite bin packing problem;
Management Science 44; 388-399.
[14] Polyakovsky S., M’Hallah R. (2009), An agent-based approach to the two-dimensional guillotine bin
packing problem; European Journal of Operational Research 192; 767–781.
[15] Puchinger J., Raidl G.R. (2006), Models and algorithms for three-stage two-dimensional bin packing;
European Journal of Operational Research 183; 1304-1327.

[16] Sevaux M., Dauzère-Pérès S. (2003), Genetic algorithms to minimize the weighted number of late jobs
on a single machine; European Journal of Operational Research 151; 296–306.
[17] Smith D. (1985), Bin-packing with adaptive search; in Grefenstette (ed.). Proceedings of International
Conference on Genetic Algorithms and their Applications; Lawrence Erlbaum; 202-206.
[18] Vasko F.J., Wolf F.E., Stott K.L. (1989), A practical solution to a fuzzy two dimensional cutting stock
problem; Fuzzy Sets and Systems 29; 259-275.
[19] Wäscher G., Haußn er H., Schumann H. (2007), An improved typology of cutting and packing
problems; European Journal of Operational Research 183(3); 1109-1130.