article

Heuristics and lower bounds for the bin packing problem with conflicts

Authors:

Michel Gendreau,

Gilbert Laporte,

Frédéric SemetAuthors Info & Claims

Computers and Operations Research, Volume 31, Issue 3

Pages 347 - 358

https://doi.org/10.1016/S0305-0548(02)00195-8

Published: 01 March 2004 Publication History

Abstract

In the bin packing problem with conflicts, the aim is to pack items into the minimum number of bins subject to incompatibility restrictions. Two lower bounding procedures and six heuristics for this problem are developed and compared.

References

[1]

{1} Laporte G, Desroches S. Examination timetabling by computer. Computers & Operations Research 1984;11:351-60.

Crossref

Google Scholar

[2]

{2} Jansen K. An approximation scheme for bin packing with conflicts. Journal of Combinatorial Optimization 1999;3: 363-77.

Google Scholar

[3]

{3} Christofides N, Mingozzi A, Toth P. Loading problems. In: Christofides N, Mingozzi A, Toth P, Sandi C, editors. Combinatorial optimization. Chichester: Wiley, 1979. p. 339-69.

Google Scholar

[4]

{4} Martello S, Toth P. Knapsack problems. Chichester: Wiley, 1990a.

Google Scholar

[5]

{5} Hansen P, Hertz A, Kuplinsky J. Bounded vertex colorings of graphs. Discrete Mathematics 1993;111:305-12.

Crossref

Google Scholar

[6]

{6} Dycknoff H. A typology of cutting and packing problems. European Journal of Operational Research 1990;44: 145-59.

Google Scholar

[7]

{7} Jansen K, Oehring S. Approximation algorithms for time constrained scheduling. Information and Computation 1997;132:85-108.

Crossref

Google Scholar

[8]

{8} Baker BS, Coffman EG. Mutual exclusion scheduling. Theoretical Computer Science 1996;162:225-43.

Crossref

Google Scholar

[9]

{9} Bodlaender H-L, Jansen K. On the complexity of scheduling incompatible jobs with unit-times. Mathematical Foundations of Computer Science, MFCS 93, LNCS 1993;711:291-300.

Crossref

Google Scholar

[10]

{10} Carter MW, Laporte G, Lee SY. Examination timetabling: algorithmic strategies and applications. Journal of the Operational Research Society 1996;47:373-83.

Google Scholar

[11]

{11} Coffman Jr. EG, Garey MR, Johnson DS. Approximation algorithms for bin-packing--an updated survey. In: Ausiello G, Lucertini M, Serafini P, editors. Algorithm design for computer system design. Vienna: Springer, 1984. p. 49-106.

Google Scholar

[12]

{12} Brélaz D. New methods to color the vertices of a graph. Communications of the Association for Computing Machinery 1979;22:251-6.

Crossref

Google Scholar

[13]

{13} Johnson DS. Approximation algorithms for combinatorial problems. Journal of Computer and System Science 1974;9:256-78.

Google Scholar

[14]

{14} Syslo MM, Deo N, Kowalik JS. Discrete optimization algorithms with PASCAL programs. Englewood Cliffs: Prentice-Hall, 1983.

Crossref

Google Scholar

[15]

{15} Falkenauer E. A hybrid grouping genetic algorithm. Journal of Heuristics 1996;2:5-30.

Google Scholar

[16]

{16} Soriano P, Gendreau M. Tabu search algorithms for the maximum clique problem. In: Johnson DS, Trick MA, editors. Cliques, coloring and satisfiabitity. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 26. Providence: American Mathematical Society, 1996. p. 221-42.

Google Scholar

[17]

{17} Martello S, Toth P. Lower bounds and reduction procedures for the bin packing problem. Discrete Applied Mathematics 1990b;28:59-70.

Crossref

Google Scholar

Cited By

View all

Rodrigues GCunha CGuarino Neto LVieira J(2024)An adaptive large neighborhood search metaheuristic for the Generalized Bin Packing problem with incompatible categoriesComputers and Industrial Engineering10.1016/j.cie.2023.109586185:COnline publication date: 27-Feb-2024
https://dl.acm.org/doi/10.1016/j.cie.2023.109586
Chi YDai WFan YRuan JHwang KCai W(2024)Total cost ownership optimization of private clouds: a rack minimization perspectiveWireless Networks10.1007/s11276-021-02757-130:5(3855-3869)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11276-021-02757-1
Baghel DRavsky ASegal-Halevi E(2024)k-Times Bin Packing and its Application to Fair Electricity DistributionAlgorithmic Game Theory10.1007/978-3-031-71033-9_27(483-500)Online publication date: 3-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71033-9_27
Show More Cited By

Index Terms

Heuristics and lower bounds for the bin packing problem with conflicts
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
  2. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching

Recommendations

Improved lower bounds for the online bin packing problem with cardinality constraints

The bin packing problem has been extensively studied and numerous variants have been considered. The $$k$$ k - item bin packing problem is one of the variants introduced by Krause et al. (J ACM 22:522---550, 1975 ). In addition to the formulation of the ...
Approximation lower bounds in online LIB bin packing and covering
Special issue: Selected papers of the 13th Australasian workshop on combinatorial algorithms

We consider the NP Hard problems of online Bin Packing and online Bin Covering while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items - we call such a version, the ...
Efficient lower bounds and heuristics for the variable cost and size bin packing problem

We consider the variable cost and size bin packing problem, a generalization of the well-known bin packing problem, where a set of items must be packed into a set of heterogeneous bins characterized by possibly different volumes and fixed selection ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Operations Research

Computers and Operations Research Volume 31, Issue 3

March 2004

159 pages

ISSN:0305-0548

Issue’s Table of Contents

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 March 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Rodrigues GCunha CGuarino Neto LVieira J(2024)An adaptive large neighborhood search metaheuristic for the Generalized Bin Packing problem with incompatible categoriesComputers and Industrial Engineering10.1016/j.cie.2023.109586185:COnline publication date: 27-Feb-2024
https://dl.acm.org/doi/10.1016/j.cie.2023.109586
Chi YDai WFan YRuan JHwang KCai W(2024)Total cost ownership optimization of private clouds: a rack minimization perspectiveWireless Networks10.1007/s11276-021-02757-130:5(3855-3869)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11276-021-02757-1
Baghel DRavsky ASegal-Halevi E(2024)k-Times Bin Packing and its Application to Fair Electricity DistributionAlgorithmic Game Theory10.1007/978-3-031-71033-9_27(483-500)Online publication date: 3-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71033-9_27
Jin XQin HCheng C(2023)A tailored adaptive large neighborhood search algorithm for the air cargo partitioning problem with a piecewise linear cost functionSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-09033-827:23(17639-17656)Online publication date: 3-Aug-2023
https://dl.acm.org/doi/10.1007/s00500-023-09033-8
Letelier OClautiaux FSadykov R(2022)Bin Packing Problem with Time LagsINFORMS Journal on Computing10.1287/ijoc.2022.116534:4(2249-2270)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1287/ijoc.2022.1165
Mehrani SCardonha CBergman D(2022)Models and Algorithms for the Bin-Packing Problem with Minimum Color FragmentationINFORMS Journal on Computing10.1287/ijoc.2021.112034:2(1070-1085)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1287/ijoc.2021.1120
Costa LContardo CDesaulniers GYarkony J(2022)Stabilized Column Generation Via the Dynamic Separation of Aggregated RowsINFORMS Journal on Computing10.1287/ijoc.2021.109434:2(1141-1156)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1287/ijoc.2021.1094
da Silva Barros BPinheiro RSouza UOchi L(2022)Using adaptive memory in GRASP to find minimum conflict-free spanning treesSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-022-07602-x27:8(4699-4712)Online publication date: 13-Nov-2022
https://dl.acm.org/doi/10.1007/s00500-022-07602-x
Capobianco GD’Ambrosio CPavone LRaiconi AVitale GSebastiano F(2022)A hybrid metaheuristic for the Knapsack Problem with ForfeitsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-021-06331-x26:2(749-762)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s00500-021-06331-x
Barros BOchi LPinheiro RSouza U(2022)On Conflict-Free Spanning Tree: Algorithms and ComplexityAlgorithms and Discrete Applied Mathematics10.1007/978-3-030-95018-7_8(91-102)Online publication date: 10-Feb-2022
https://dl.acm.org/doi/10.1007/978-3-030-95018-7_8
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Improved lower bounds for the online bin packing problem with cardinality constraints

Approximation lower bounds in online LIB bin packing and covering

Efficient lower bounds and heuristics for the variable cost and size bin packing problem

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations