Lien entre problèmes d'ordonnancement et de bin-packing

François Clautiaux
Heudyasic - UTC, Compiègne

Les problèmes de bin packing en une ou deux dimensions sont 
fortement liés à des problèmes d'ordonnancement classiques. De 
nombreuses méthodes dédiées aux problèmes d'ordonnancement 
peuvent être appliquées au bin packing et réciproquement. Pour 
illustrer ce propos, deux méthodes seront présentées. La première 
est une méthode exacte pour un problème de bin packing en deux 
dimensions qui utilise une relaxation en un problème 
d'ordonnancement cumulatif. La deuxième est une méthode de calcul 
de bornes inférieures qui a été développée pour des problèmes 
d'ordonnancement par Jacques Carlier et Emmanuel Néron et que 
nous avons adaptée au bin packing en une et deux dimensions.