LIP6 1999/032

• Rapports de recherche
  Ordonnancement en présence de dates souhaitées et de dates impératives
• F. Sourd, W. Nuijten
• 22 pages - 20/12/1999- document en - http://www.lip6.fr/lip6/reports/1999/lip6.1999.032.ps.gz - 130 Ko
• Contact : Francis.Sourd (at) nulllip6.fr
• Ancien Thème : SYSDEF
Ce papier traite des problèmes d'ordonnancement d'opérations avec une queue. Ces queues sont d'ordinaire utilisées dans la littérature pour modéliser des dates d'échéances, qu'elles soient impératives ou simplement souhaitées. Nous montrons qu'il peut être intéressant, particulièrement dans les problèmes d'ateliers, de considérer des opérations ayant à la fois une date de fin impérative et une date souhaitée, modélisée par une queue. Nous faisons ensuite un tour d'horizon des principaux problèmes à une machine et à machines parallèles pour voir quels sont ceux qui peuvent être résolus en temps polynomial en présence de dates de fin et de queues. Nous montrons que que ces deux données peuvent être modélisées par un fonction objectif fmax de type 'minimax'. De cette manière, plusieurs problèmes peuvent être résolus en temps quadratique. Mais, en regardant les propriétés particulières de ces problèmes, on arrive à montrer qu'ils peuvent être résolus en O(nlogn). Nous montrons également que P|pj=1|rj|fmax peut être résolus en temps O(n^2).
• Mots clés : ordonnancement, dates de début, dates de fin souhaitée, dates de fin impératives, problèmes d'ateliers, borne inférieure
• Directeur de la publication : Valerie.Mangin (at) nulllip6.fr