LIP6 2002/019

• Reports «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 - 09/24/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
It is with the aim of solving scheduling problems with irregular cost functions that this paper focuses on the continuous assignment problem. It consists in partitioning a d dimensional region.into subregions of prescribed volumes so that the total cost is minimized. The dual problem of the continuous assignment problem is an unconstrained maximisation of a non-smooth concave function. The preemptive variant of the scheduling problem with irregular cost functions corresponds to the one-dimensional continuous assignment problem and a lower bound for the non-preemptive variant can be derived. It is computationally tested in a branch-and-bound algorithm.