| Autor: |
Sourd, Francis |
| Přispěvatelé: |
Systèmes d'aide à la décision et à la formation (SYSDEF), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), LIP6 |
| Jazyk: |
angličtina |
| Rok vydání: |
2002 |
| Předmět: |
|
| Zdroj: |
[Research Report] lip6.2002.019, LIP6. 2002 |
| Popis: |
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.; 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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
