A Set-Covering-Based Heuristic Approach for Bin-Packing Problems

References

• Baker B. S., Coffman E. G., Rivest R. L. Orthogonal packing in two dimensions. SIAM J. Comput. (1980) 9:846–855Crossref, Google Scholar
• Beasley J. E. Algorithms for unconstrained two-dimensional guillotine cutting. J. Oper. Res. Soc. (1985a) 36:297–306Crossref, Google Scholar
• Beasley J. E. An exact two-dimensional non-guillotine cutting tree search procedure. Oper. Res. (1985b) 33:49–64Link, Google Scholar
• Beasley J. E. OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. (1990) 41:1069–1072Crossref, Google Scholar
• Bengtsson B. E. Packing rectangular pieces—A heuristic approach. Comput. J. (1982) 25:353–357Crossref, Google Scholar
• Berkey J. O., Wang P. Y. Two dimensional finite bin packing algorithms. J. Oper. Res. Soc. (1987) 38:423–429Crossref, Google Scholar
• Bodin L., Golden B., Assad A., Ball M. Routing and scheduling of vehicles and crews: The state of the art. Comp. Oper. Res. (1983) 10:63–211Crossref, Google Scholar
• Boschetti M. A., Mingozzi A. Two-dimensional finite bin packing problems. Part I: New lower and upper bounds. 4OR (2003a) 1:27–42Crossref, Google Scholar
• Boschetti M. A., Mingozzi A. Two-dimensional finite bin packing problems. Part II: New lower and upper bounds. 4OR (2003b) 2:135–147Google Scholar
• Caprara A., Toth P. Lower bounds and algorithms for the 2-dimensional vector packing problem. Discrete Appl. Math. (2001) 111:231–262Crossref, Google Scholar
• Caprara A., Fischetti M., Toth P. A heuristic method for the set covering problem. Oper. Res. (1999) 47:730–743Link, Google Scholar
• Caprara A., Monaci M., Toth P., Voss S., Daduna J. R. A global method for crew planning in railway applications. Computer-Aided Scheduling of Public Transport. Lecture Notes in Economics and Mathematical Systems (2001) (Springer-Verlag, Berlin, Germany) 17–36Crossref, Google Scholar
• Caprara A., Monaci M., Toth P. Greedy procedures for the multi-constraint bin packing problem. (2002) . Technical report OR/02/12, Dipartimento di Elettronica, Informatica e Sistemistica, Università di Bologna, Bologna, ItalyGoogle Scholar
• Caprara A., Fischetti M., Toth P., Vigo D., Guida P. L. Algorithms for railway crew management. Math. Programming (1997) 79:125–141Crossref, Google Scholar
• Chekuri C., Khanna S. On multi-dimensional packing problems. Proc. 10th Annual ACM-SIAM Symp. Discrete Algorithms (SODA99) (1999) (ACM Press, Baltimore, Maryland) 185–194Google Scholar
• Christofides N., Whitlock C. An algorithm for two-dimensional cutting problems. Oper. Res. (1977) 25:30–44Link, Google Scholar
• Chung F. K. R., Garey M. R., Johnson D. S. On packing two-dimensional bins. SIAM J. Algebraic Discrete Methods (1982) 3:66–76Crossref, Google Scholar
• Dyckhoff H., Scheithauer G., Terno J., Dell'Amico M., Maffioli F., Martello S. Cutting and packing (C&P). Annotated Bibliographies in Combinatorial Optimization (1997) (John Wiley and Sons, Chichester, U.K.) 393–413Google Scholar
• Færø O., Pisinger D., Zachariasen M. Guided local search for the three-dimensional bin packing problem. INFORMS J. Comput. (2003) 15:267–283Link, Google Scholar
• Fekete S. P., Schepers J. On more-dimensional packing III: Exact algorithms. (1997) . Technical report ZPR/97/290, Mathematisches Institut, Universität zu Köln, Köln, GermanyGoogle Scholar
• Fekete S. P., Schepers J. A combinatorial characterization of high-dimensional orthogonal packing. Math. Oper. Res. (2004a) 29:353–368Link, Google Scholar
• Fekete S. P., Schepers J. A general framework for bounds for higher-dimensional orthogonal packing problems. Math. Methods Oper. Res. (2004b) 60:311–329Crossref, Google Scholar
• Fernandez de la Vega W., Lueker G. S. Bin packing can be solved within 1 + ε in linear time. Combinatorica (1981) 1:349–355Crossref, Google Scholar
• Frenk J. B., Galambos G. G. Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem. Computing (1987) 39:201–217Crossref, Google Scholar
• Garey M. R., Graham R. L., Johnson D. S., Yao A. C. Resource constrained scheduling as generalized bin packing. J. Combin. Theory (A) (1976) 21:257–298Crossref, Google Scholar
• Gilmore P. C., Gomory R. E. Multistage cutting problems of two and more dimensions. Oper. Res. (1965) 13:94–119Link, Google Scholar
• Kellerer H., Kotov V. An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing. Oper. Res. Lett. (2003) 31:35–41Crossref, Google Scholar
• Kelly J. P., Xu J. A set-partitioning-based heuristic for the vehicle routing problem. INFORMS J. Comput. (1999) 11:161–172Link, Google Scholar
• Lodi A., Martello S, Monaci M. Two-dimensional packing problems: A survey. Eur. J. Oper. Res. (2002) 141:241–252Crossref, Google Scholar
• Lodi A., Martello S., Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS J. Comput. (1999a) 11:345–357Link, Google Scholar
• Lodi A., Martello S., Vigo D. Approximation algorithms for the oriented two-dimensional bin packing problem. Eur. J. Oper. Res. (1999b) 112:158–166Crossref, Google Scholar
• Marsten R., Shepardson F. Exact solution of crew scheduling problems using the set partitioning model: Recent successful applications. Networks (1981) 112:167–177Google Scholar
• Martello S., Vigo D. Exact solution of the two-dimensional finite bin packing problem. Management Sci. (1998) 44:388–399Link, Google Scholar
• Martello S., Vigo D. New computational results for the exact solution of the two-dimensional finite bin packing problem. (2001) . Technical report OR/01/06, Dipartimento di Elettronica, Informatica e Sistemistica, Università di Bologna, Bologna, ItalyGoogle Scholar
• Maruyama K., Chang S. K., Tang D. T. A general packing algorithm for multidimensional resource requirements. Internat. J. Comput. Inform. Sci. (1977) 6:131–149Crossref, Google Scholar
• Spieksma F. C. R. A branch-and-bound algorithm for the two-dimensional vector packing problem. Comput. Oper. Res. (1994) 21:19–25Crossref, Google Scholar
• Valerio de Carvalho J. M. V. Exact solution of cutting stock problems using column generation and branch-and-bound. Internat. Trans. Oper. Res. (1998) 5:35–44Crossref, Google Scholar
• Vance P. H. Branch-and-price algorithms for the one-dimensional cutting stock problem. Comput. Optim. Appl. (1998) 9:211–228Crossref, Google Scholar
• Vance P. H., Barnhart C., Johnson E. L., Nemhauser G. L. Solving binary cutting stock problems by column generation and branch-and-bound. Comput. Optim. Appl. (1994) 3:111–130Crossref, Google Scholar
• Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems. Math. Programming (1999) 86:565–594Crossref, Google Scholar
• Voudouris C., Tsang E. Guided local search and its application to the traveling salesman problem. Eur. J. Oper. Res. (1999) 113:469–499Crossref, Google Scholar
• Wedelin D. An algorithm for large scale 0-1 integer programming with application to airline crew scheduling. Ann. Oper. Res. (1995) 57:283–301Crossref, Google Scholar
• Woeginger G. There is no asymptotic ptas for two-dimensional vector packing. Inform. Processing Lett. (1997) 64:293–297Crossref, Google Scholar
• Yao A. C. New algorithms for bin packing. J. ACM (1980) 27:207–227Crossref, Google Scholar