LIP6 2002/019

• Rapports de recherche
  Le problème d'affectation continue : application à l'ordonnancement préemptif et non préemptif en présence de fonctions de coût non régulières
• F. Sourd
• 21 pages - 24/09/2002- document en - http://www.lip6.fr/lip6/reports/2002/lip6.2002.019.pdf - 284 Ko
• Contact : Francis.Sourd (at) nulllip6.fr
• Ancien Thème : SYSDEF
C'est dans le but de résoudre.les problèmes d'ordonnancement avec des fonctions de coût irrégulières que ce papier se concentre sur le problème d'affectation continue. Ce problème consiste à partitioner une région à d dimensions en sous-régions de volumes fixés, de.manière.à ce que le coût total soit minimisé. Le problème dual revient à maximiser sans contraintes une fonction concave mais non différentiable. La variante préemptive du problème d'ordonnancement avec critères irrégulier correspond au problème d'affectation en dimension 1 et une borne inférieure peut en être déduite pour la variante non préemptive. Cette borne est testée expérimentalement dans un algorithme par séparation et évaluation.
• Mots clés : Ordonnancement Juste-à-temps, partitionement géométrique, relaxation préemptive
• Directeur de la publication : Nicole.Nardy (at) nulllip6.fr