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
- Keywords : Just-in-time scheduling, geometric partitioning, preemptive relaxation
- Publisher : Nicole.Nardy (at) nulllip6.fr
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.