Abstract
Given a finite set of circles of different sizes we study the strip packing problem (SPP) as well as the Knapsack Problem (KP). The SPP asks for a placement of all circles within a rectangular strip of fixed width so that the variable length of the strip is minimized. The KP requires packing of a subset of the circles in a given rectangle so that the wasted area is minimized. To solve these problems some greedy algorithms were developed which enhance the algorithms proposed by Huang et al. (J Oper Res Soc 56:539–548, 2005). Furthermore, the new greedy algorithms were parallelized using a master slave approach. The resulting parallel methods were tested using the instances introduced by Stoyan and Yaskov (Eur J Oper Res 156:590–600, 2004). Additionally, two sets of 128 instances each for the SPP and for the KP were generated and results for these new instances are also reported.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bortfeldt A, Gehring H (2006) New large benchmark instances for the two-dimensional strip packing problem with rectangular pieces. In: Proceedings of the 39th annual Hawaii international conference of system sciences (HICCS’06) Track 2, p. 30b
Castillo I, Kampas FJ, Pinter JD (2008) Solving circle packing problems by global optimization: numerical results and industrial applications. Eur J Oper Res 191: 786–802
Crainic TG, Toulouse M (2003) Parallel strategies for meta-heuristics. In: Glover F, Kochenberger G (eds) Handbook on metaheuristics. Kluwer Academic Publishers, Boston, pp 475–513
Dowsland KA (1991) Palletisation of cylinders in cases. OR Spektrum 13: 171–172
Fraser HJ, George JA (1994) Integrated container loading software for pulp and paper industry. Eur J Oper Res 77: 466–474
George JA, George JM, Lamer BW (1995) Packing different-sized circles into a rectangular container. Eur J Oper Res 84: 693–712
Gill PE, Murray W, Wright MH (1981) Practical optimization. Academic Press, New York
Graham RL, Lubachevsky BD (1996) Repeated patterns of dense packings of equal disks in a square. Electronic Journal of Combinatorics 3, Report No. 16
Henderson D, Jacobson SH, Johnson AW (2003) The theory and practice of simulated annealing. In: Glover F, Kochenberger G (eds) Handbook on metaheuristics. Kluwer Academic Publishers, Boston, pp 287–319
Hifi M, M’Hallah R (2004) Approximate algorithms for constrained circular cutting problems. Comput Oper Res 31: 675–694
Hifi M, Paschos VTh, Zissimopoulos VA (2004) Simulated annealing approach for the circular cutting problem. Eur J Oper Res 159: 430–448
Huang WQ, Li Y, Gérard S, Li CM, Xu RC (2002) A ‘Learning From Human’ heuristic for solving unequal circle packing problem. In: Hao JK, Liu BD (eds) Proceedings of the first international workshop on heuristics Beijing, China. Tsinghua University, Beijing, China, pp 39–45
Huang WQ, Li Y, Jurkowiak B, Li CM (2003) A two-level search strategy for packing unequal circles into a circle container. In: Francesca R (ed) Proceedings of principles and practice of Constraint Programming CP2003, Kinsale, Ireland. Lecture Notes in Computer Science, vol 2833. Springer, Berlin, pp 868-872
Huang WQ, Li Y, Akeb H, Li CM (2005) Greedy algorithms for packing unequal circles into a rectangular container. J Oper Res Soc 56: 539–548
Lenstra JK, Rinnooy Kan AHG (1979) Complexity of packing, covering, and partitioning problems. In: Schrijver A (eds) Packing and covering in combinatorics. Mathematisch Centrum, Amsterdam, pp 275–291
Reeves C (2003) Genetic algorithms. In: Glover F, Kochenberger G (eds) Handbook on metaheuristics. Kluwer Academic Publishers, Boston, pp 55–81
SiS Sandra 2005 benchmark suite. SiSoftware. http://www.sisoftware.net, 2005
Stoyan YY, Yaskov G (2004) A mathematical model and a solution method for the problem of placing various-sized circles into a strip. Eur J Oper Res 156: 590–600
Stoyan YY, Yaskow G, Scheithauer G (2003) Packing of various radii solid spheres into a parallelepiped. Cent Eur J Oper Res 11: 389–407
Toth FJ (1953) Lagerungen in der Ebene, auf der Kugel und im Raum. Springer, Berlin
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kubach, T., Bortfeldt, A. & Gehring, H. Parallel greedy algorithms for packing unequal circles into a strip or a rectangle. Cent Eur J Oper Res 17, 461–477 (2009). https://doi.org/10.1007/s10100-009-0103-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10100-009-0103-5