|Start Page Number:||2122|
|End Page Number:||2132|
|Publication Date:||Sep 2012|
|Journal:||Computers and Operations Research|
|Authors:||Hanafi Sad, Clautiaux Franois, Talbi El-Ghazali, Khanafer Ali|
|Keywords:||heuristics, programming: multiple criteria, heuristics: tabu search|
In the classical bin‐packing problem with conflicts (BPC), the goal is to minimize the number of bins used to pack a set of items subject to disjunction constraints. In this paper, we study a new version of BPC: the min‐conflict packing problem (MCBP), in which we minimize the number of violated conflicts when the number of bins is fixed. In order to find a tradeoff between the number of bins used and the violation of the conflict constraints, we also consider a bi‐objective version of this problem. We show that the special structure of its Pareto front allows to reformulate the problem as a small set of MCBP. We solved these two problems through heuristics, column‐generation methods, and a tabu search. Computational experiments are reported to assess the quality of our methods.