Skip to Main content Skip to Navigation
Conference papers

Une contrainte globale de bin-packing avec précédences : application au problème d'équilibrage de lignes d'assemblage

Résumé : Les problèmes d'équilibrage de lignes d'assemblage (PELA) sont d'une importance primordiale pour l'industrie depuis l'invention de la première ligne d'assemblage de la Ford T imaginée par Henry Ford. L'objectif haut niveau de ces problèmes est d'optimiser la conception des lignes tout en respectant diverses contraintes. Les contraintes de précédences entre les tâches sont omniprésentes dans les PELA. Plus concrètement, l'objectif est alors de répartir les tâches entre divers postes de travail de sorte que le taux de production soit maximal. Ce problème peut être modélisé comme un problème de bin-packing avec des contraintes de précédence (BPCP) où les bins sont les postes de travail et les objets à placer correspondent aux tâches. Paul Shaw a introduit une contrainte globale pour le bin-packing. Malheureusement cette contrainte ne prend pas en compte les précédences du BPCP. Dans cet article, nous introduisons dans un premier temps des contraintes redondantes pour le BBCP combinant les précédences et le bin-packing. Ces contraintes redondantes permettant de résoudre des instances non solubles sans celles-ci en programmation par contraintes. Nous introduisons également une contrainte globale pour le BPPC qui permet d'élaguer d'avantage l'arbre de recherche. Enfin, nous expérimentons notre modèle de PC pour le BBCP afin résoudre le PELA. Nous proposons également deux heuristiques et montrons l'efficacité de notre approche sur des jeux de données standards du PELA. En comparaisons aux techniques dédiées n'utilisant pas la PC, notre approche est plus flexible. En effet elle permet aisément l'ajout de nouvelles contraintes pouvant survenir dans des applications réelles.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00290826
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, June 26, 2008 - 3:13:33 PM
Last modification on : Friday, July 11, 2008 - 6:29:01 PM
Long-term archiving on: : Friday, May 28, 2010 - 8:21:02 PM

File

pages-079-86-article34.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00290826, version 1

Collections

Citation

Pierre Schauss, Yves Deville. Une contrainte globale de bin-packing avec précédences : application au problème d'équilibrage de lignes d'assemblage. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.79-86. ⟨inria-00290826⟩

Share

Metrics

Record views

319

Files downloads

401