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.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.79-86, 2008
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00290826
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 26 juin 2008 - 15:13:33
Dernière modification le : vendredi 11 juillet 2008 - 18:29:01
Document(s) archivé(s) le : vendredi 28 mai 2010 - 20:21:02

Fichier

pages-079-86-article34.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.79-86, 2008. 〈inria-00290826〉

Partager

Métriques

Consultations de la notice

270

Téléchargements de fichiers

236