The continuous assignment problem and its application to preemptive and non-preemptive scheduling with irregular cost functions

F. Sourd

LIP6 2002/019: Rapport de Recherche LIP6 / LIP6 research reports
21 pages - Septembre/September 2002 - Document en anglais.

Get it : 278 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Systèmes d'Aide à la Décision et à la Formation

Titre français : 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
Titre anglais : The continuous assignment problem and its application to preemptive and non-preemptive scheduling with irregular cost functions

Résumé : 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.

Abstract : 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.

Mots-clés : Ordonnancement Juste-à-temps, partitionement géométrique, relaxation préemptive

Key-words : Just-in-time scheduling, geometric partitioning, preemptive relaxation

Publications internes LIP6 2002 / LIP6 research reports 2002

Responsable Éditorial / Editor :Nicole.Nardy@lip6.fr