Skip to main content
SpringerLink
Log in

Multiple-type, two-dimensional bin packing problems: Applications and algorithms

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In this paper we consider a class of bin selection and packing problems (BPP) in which potential bins are of various types, have two resource constraints, and the resource requirement for each object differs for each bin type. The problem is to select bins and assign the objects to bins so as to minimize the sum of bin costs while meeting the two resource constraints. This problem represents an extension of the classical two-dimensional BPP in which bins are homogeneous. Typical applications of this research include computer storage device selection with file assignment, robot selection with work station assignment, and computer processor selection with task assignment. Three solution algorithms have been developed and tested: a simple greedy heuristic, a method based onsimulated annealing (SA) and an exact algorithm based onColumn Generation with Branch and Bound (CG). An LP-based method for generating tight lower bounds was also developed (LB). Several hundred test problems based on computer storage device selection and file assignment were generated and solved. The heuristic solved problems up to 100 objects in less than a second; average solution value was within about 3% of the optimum. SA improved solutions to an average gap of less than 1% but a significant increase in computing time. LB produced average lower bounds within 3% of optimum within a few seconds. CG is practical for small to moderately-sized problems — possibly as many as 50 objects.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E.H.L. Aarts and J. Korst,Simulated Annealing and Boltzmann Machines (Wiley, 1989).

  2. E.H.L. Aarts and P.J.M. van Laarhoven, Statistical cooling: A general approach to combinatorial problems, Phillips J. Res. 40(1985)193–226.

    Google Scholar 

  3. A.V. Aho, J.E. Hopcroft and J.D. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974) chapter 10.

    Google Scholar 

  4. E. Appleton and D.J. Williams,Industrial Robot Applications (Wiley, New York, 1987) chapter 3.

    Google Scholar 

  5. B.S. Baker, E.G. Coffman and R.L. Rivest, Orthogonal packings in two dimensions, SIAM J. Comp. 9(1980)846–855.

    Google Scholar 

  6. B.S. Baker, D.J. Brown and H.P. Katseff, A 5/4 algorithm for two-dimensional bin packing, J. Algor. 2(1981)348–368.

    Google Scholar 

  7. B.S. Baker and J.S. Schwarz, Shelf algorithms for two-dimensional packing problems, SIAM J. Comp. 12(1983)508–525.

    Google Scholar 

  8. M. Ball and M. Magazine, The design and analysis of heuristics, Networks 11(1981)215–219.

    Google Scholar 

  9. J.J. Bartholdi III, J.H. Vande Vate and J. Zhang, Expected performance of the shelf heuristic for 2-dimensional packing, Oper. Res. Lett. 8(1989)11–16.

    Google Scholar 

  10. S.P. Bradley, A.C. Hax and T.L. Magnanti,Applied Mathematical Programming (Addison-Wesley, 1977) chapter 12.

  11. D.J. Brown, B.S. Baker and H.P. Katseff, Lower bounds for on-line two-dimensional packing algorithms, Acta Inf. 18(1982)207–225.

    Google Scholar 

  12. F.R.K. Chung, M.R. Garey and D.S. Johnson, On packing two-dimensional bins, SIAM J. Alg. Discr. Methods 3(1982)66–76.

    Google Scholar 

  13. B. Chazelle, The bottom-left bin-packing heuristic: An efficient implementation, IEEE Trans. Comp. C-32(1983)697–707.

    Google Scholar 

  14. E.G. Codd, Multiprogramming scheduling, Commun. ACM, Parts 1 and 2(1960)347–350; Parts 3 and 4 (1960) 413–418.

  15. E.G. Coffman, M.R. Garey, D.S. Johnson and R.E. Tarjan, Performance bounds for level-oriented two-dimensional packing algorithms, SIAM J. Comp. 9(1980)808–826.

    Google Scholar 

  16. E.G. Coffman, M.R. Garey and D.S. Johnson, Approximation algorithms for bin-packing — an updated survey, in:Algorithm Design for Computer System Design, ed. G. Ausiello, M. Luccertini and P. Serafini (Springer, Vienna, 1984) pp. 49–106.

    Google Scholar 

  17. J. Cook and B.T. Han, Optimal robot selection and work station assignment for a CIM system, IEEE Trans. Robotics and Automation (February, 1994), to appear.

  18. D. Coppersmith and P. Raghavan, Multidimensional on-line bin packing: algorithms and worst-case analysis, Oper. Res. Lett. 8(1989)17–20.

    Google Scholar 

  19. G. Cornejols, R. Sridharan and J.M. Thizy, A comparison of heuristics and relaxations for the capacitated plant location problem, Eur. J. Oper. Res. 50(1991)280–297.

    Google Scholar 

  20. K.A. Dowsland and W.B. Dowsland, Packing problems, Eur. J. Oper. Res. 56(1992)2–14.

    Google Scholar 

  21. M.L. Fisher, The Lagrangian relaxation method for solving integer programming problem, Manag. Sci. 27(1981)1–18.

    Google Scholar 

  22. W. Fernandez de la Vega and G.S. Lueker, Bin packing can be solved within 1+ε in linear time, Combinatorica 1(1981)349–355.

    Google Scholar 

  23. M.R. Garey, R.L. Graham, D.S. Johnson and A.C.C. Yao, Resource constrained scheduling as generalized bin packing, J. Comb. Theory (A) 21(1976)257–298.

    Google Scholar 

  24. B. Gavish and H. Pirkul, Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Math. Progr. 31(1985)78–105.

    Google Scholar 

  25. A. Geoffrion and R. McBride, Lagrangian relaxation applied to capacitated facility location problems, AIIE Trans. 10(1978)40–47.

    Google Scholar 

  26. P.C. Gilmore and R.E. Gomory, A linear programming approach to the cutting-stock problem, Oper. Res. 9(1961)849–859.

    Google Scholar 

  27. P.C. Gilmore and R.E. Gomory, A linear programming approach to the cutting-stock problem-Part II, Oper. Res. 11(1963)863–888.

    Google Scholar 

  28. P.C. Gilmore and R.E. Gomory, Multistage cutting stock problems of two and more dimensions, Oper. Res. 13(1965)94–120.

    Google Scholar 

  29. F. Glover, Tabu search: a tutorial, Interfaces 20(1990)74–94.

    Google Scholar 

  30. F. Glover and R. Hubscher, Bin packing with tabu search, Graduate School of Business and Administration, University of Colorado at Boulder (1991).

  31. I. Golan, Performance bounds for orthogonal oriented two-dimensional packing algorithms, SIAM J. Comp. 10(1981)571–582.

    Google Scholar 

  32. B.T. Han and G. Diehr, An algorithm for device selection and file assignment, Eur. J. Oper. Res. 61(1992)326–344.

    Google Scholar 

  33. B.T. Han, Optimal file management for a storage system using magnetic and optical disks, Inf. Dec. Technol., to appear.

  34. M. Hofri, Two-dimensional packing: Expected performance of simple level algorithms, Inf. Control 45(1980)1–17.

    Google Scholar 

  35. W.H. Inmon, EIS and data warehouse, Database Progr. Design (November, 1992)70–73.

  36. D.S. Johnson, Fast algorithms for bin packing, J. Comp. Syst. Sci. 8(1974)272–314.

    Google Scholar 

  37. D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimazion by simulated annealing: An experimental evaluation: Part I, Graph partitioning, Oper. Res. 37(1989)865–892.

    Google Scholar 

  38. D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by simulated annealing: An experimental evaluation: Part II, Graph coloring and number partitioning, Oper. Res. 39(1991)378–406.

    Google Scholar 

  39. T. Kampke, Simulated annealing: Use of a new tool in bin packing, Ann Oper. Res. 16(1988)327–332.

    Google Scholar 

  40. N. Karmarkar and r.M. Karp, The differential method of set partitioning, Report UCB/CSD 82/113, Computer Science Division, University of California, Berkeley, California 94720 (1982).

    Google Scholar 

  41. S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing, Science 220(1983)671–680.

    Google Scholar 

  42. B. O'Connell, Reinventing data management, DEC Professional (February, 1993)40–45.

  43. W.T. Rhee and M. Talagrand, Multidimensional optimal bin packing with items of random size, Math. Oper. Res. 16(1991)490–503.

    Google Scholar 

  44. S.C. Sarin and W.E. Wilhelm, Prototype models for two-dimensional layout design of robot systems, IIE Trans. 16(1984)206–215.

    Google Scholar 

  45. D. Sleator, A 2.5 times optimal algorithm for packing in two dimensions, Inf. Proc. Lett. 10(1980)37–40.

    Google Scholar 

  46. J.D. Ullman, Complexity of sequencing problems, in:Computer and Job-shop Scheduling Theory, ed. E.G. Coffman, Jr. (Wiley, New York, 1975).

    Google Scholar 

  47. P.J.M. van Laarhoven,Theoretical and Computational Aspects of Simulated Annealing, Centre for Mathematics and Computer Science, Amsterdam, The Netherlands (1988).

    Google Scholar 

  48. P.J.M. van Laarhoven and E.H.L. Aarts,Simulated Annealing: Theory and Applications (Kluwer Academic, Boston, MA, 1988).

    Google Scholar 

  49. A.C.C. Yao, New algorithms for bin packing, J. ACM 27(1980)207–227.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Management and Systems, College of Business and Economics, Washington State University, 99164-4726, Pullman, WA, USA

    Bernard T. Han

  2. Center for High Technology Management, College of Business Administration, California State University, 92096, San Marcos, CA, USA

    George Diehr

  3. Jones School of Business, 1 College Circle, State University of New York — Geneseo, 14454, Geneseo, NY, USA

    Jack S. Cook

Authors
  1. Bernard T. Han
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. George Diehr
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jack S. Cook
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Han, B.T., Diehr, G. & Cook, J.S. Multiple-type, two-dimensional bin packing problems: Applications and algorithms. Ann Oper Res 50, 239–261 (1994). https://doi.org/10.1007/BF02085642

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02085642

Keywords

Search

Navigation