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.