Algorithms for the Bin Packing Problem with Conflicts

References

• Baker B. S., Coffman E. G. Mutual exclusion scheduling. Theoret. Comput. Sci. (1996) 162(2):225–243Crossref, Google Scholar
• Bodlaender H. L., Jansen K., Borzyszkowski A. M., Sokolowski S. On the complexity of scheduling incompatible jobs with unit times. MFCS 1993: Proc. 18th Internat. Sympos. Math. Foundations Comput. Sci. (1993) (Springer-Verlag, London) 291–300Crossref, Google Scholar
• Caprara A., Toth P. Lower bounds and algorithms for the 2-dimensional vector packing problem. Discrete Appl. Math. (2001) 111(3):231–262Crossref, Google Scholar
• Carter M. W., Laporte G., Lee S. Y. Examination timetabling: Algorithmic strategies and applications. J. Oper. Res. Soc. (1996) 47(3):373–383Crossref, Google Scholar
• Christofides N., Mingozzi A., Toth P., Christofides N., Mingozzi A., Toth P., Sandi C. The vehicle routing problem. Combinatorial Optimization (1979) (John Wiley & Sons, Chichester, UK) 315–338Google Scholar
• Edmonds J. Paths, trees and flowers. Canadian J. Math. (1965) 17:449–467Crossref, Google Scholar
• Falkenauer E. A hybrid grouping genetic algorithm. J. Heuristics (1996) 2(1):5–30Crossref, Google Scholar
• Fekete S., Schepers J. New classes of fast lower bounds for bin packing problems. Math. Programming (2001) 91(1):11–31Crossref, Google Scholar
• Gabow H. N. An efficient implementation of Edmonds' algorithm for maximum matching on graphs. J. ACM (1976) 23(2):221–234Crossref, Google Scholar
• Galinier P., Hao J.-K. Hybrid evolutionary algorithms for graph coloring. J. Combin. Optim. (1999) 3(4):379–397Crossref, Google Scholar
• Gendreau M., Laporte G., Semet F. Heuristics and lower bounds for the bin packing problem with conflicts. Comput. Oper. Res. (2004) 31(3):347–358Crossref, Google Scholar
• Hansen P., Hertz A., Kuplinsky J. Bounded vertex colorings of graphs. Discrete Math. (1993) 111(1-3):305–312Crossref, Google Scholar
• ILOG CPLEX 10 user's manual and reference manual. (2006) . ILOG, Gentilly, France, http://www.ilog.com/Google Scholar
• Jansen K. An approximation scheme for bin packing with conflicts. J. Combin. Optim. (1999) 3(4):363–377Crossref, Google Scholar
• Jansen K., Öhring S. Approximation algorithms for time constrained scheduling. Inform. Comput. (1997) 132(2):85–108Crossref, Google Scholar
• Jensen T. R., Toft B.Graph Coloring Problems (1995) (John Wiley & Sons, New York) Wiley-Interscience Series in Discrete Mathematics and OptimizationGoogle Scholar
• Johnson D. S. Approximation algorithms for combinatorial problems. J. Comput. System Sci. (1974) 9(3):256–278Crossref, Google Scholar
• Laporte G., Desroches S. Examination timetabling by computer. Comput. Oper. Res. (1984) 11(4):351–360Crossref, Google Scholar
• Malaguti E., Toth P. A survey on vertex coloring problems. Internat. Trans. Oper. Res. (2010) 17(1):1–34Crossref, Google Scholar
• Malaguti E., Monaci M., Toth P. A metaheuristic approach for the vertex coloring problem. INFORMS J. Comput. (2008) 20(2):302–316Link, Google Scholar
• Malaguti E., Monaci M., Toth P. Models and heuristic algorithms for a weighted vertex coloring problem. J. Heuristics (2009) 15(5):503–526Crossref, Google Scholar
• Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990) (John Wiley & Sons, Chichester, UK) Google Scholar
• Mehrotra A., Trick M. A. A column generation approach for graph coloring. INFORMS J. Comput. (1996) 8(4):344–354Link, Google Scholar
• Monaci M., Toth P. A set-covering-based heuristic approach for bin-packing problems. INFORMS J. Comput. (2006) 18(1):71–85Link, Google Scholar
• Morgenstern C. A., Johnson D. S., Trick M. A. Distibuted coloration neighborhood search. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challange, 1993 (1996) (American Mathematical Society, Providence, RI) 335–357DIMACS Series in Discrete Mathematics and Theoretical Computer ScienceCrossref, Google Scholar
• Moscato P., Cotta C., Glover F., Kochenberger G. A. A gentle introduction to memetic algorithms. Handbook of Metaheuristics (2003) (Kluwer, Boston) 105–144Crossref, Google Scholar
• Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems. Math. Programming (1999) 86(3):565–594Crossref, Google Scholar