Ordonnancement d'atelier avec contraintes d'écart minimal et maximal entre opérations

Freddy Deppner 1
1 MACSI - Industrial system modeling, analysis and operation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Résumé : Les contraintes d'écart temporel minimum et maximum entre diverses opérations d'un travail sont des contraintes qui n'ont bénéficié que de peu d'attention comparativement à d'autres problématiques en ordonnancement d'atelier. Ceci est dû en partie au fait que construire une solution valide est en soi un problème NP-complet dans le cas général. Le but de cet article est de montrer comment modifier un algorithme de construction à base de liste de priorités afin d'essayer d'obtenir une solution valide pour des cas particuliers d'ordonnancement d'atelier les plus généraux possibles. Cet algorithme repose sur une partition des opérations qui permet de réduire la combinatoire des cas possibles. Nous montrons que cet algorithme permet de construire une solution en temps polynomial sous certaines hypothèses. || Minimal and maximal time lags between operations of a job are constraints which have been little considered in the scheduling literature. The reason is that only building a feasible solution is a NP-complete problem in the general case. In this paper, we
Type de document :
Communication dans un congrès
4e Conférence Francophone de MOdélisation et SIMulation - MOSIM'03, Apr 2003, Toulouse, France, pp.430-436, 2003
Liste complète des métadonnées

https://hal.inria.fr/inria-00099827
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:41:36
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00099827, version 1

Collections

Citation

Freddy Deppner. Ordonnancement d'atelier avec contraintes d'écart minimal et maximal entre opérations. 4e Conférence Francophone de MOdélisation et SIMulation - MOSIM'03, Apr 2003, Toulouse, France, pp.430-436, 2003. 〈inria-00099827〉

Partager

Métriques

Consultations de la notice

250