A dominant class of schedules for malleable jobs in the problem to minimise the total weighted completion time

Ruslan Sadykov 1, 2
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : This paper is about scheduling parallel jobs, i.e. which can be executed on more than one machine at the same time. Malleable jobs is a special class of parallel jobs. The number of machines a malleable job is executed on may change during its execution. In this work, we consider the NP-hard problem of scheduling malleable jobs to minimize the total weighted completion time (or mean weighted flow time). For this problem, we introduce the class of ''ascending'' schedules in which, for each job, the number of machines assigned to it cannot decrease over time while this job is being processed. We prove that, under a natural assumption on the processing time functions of jobs, the set of ascending schedules is dominant for the problem. This result can be used to reduce the search space while looking for an optimal solution.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2012, 39 (6), pp.1265-1270. 〈10.1016/j.cor.2011.02.023〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00539875
Contributeur : Ruslan Sadykov <>
Soumis le : jeudi 25 novembre 2010 - 14:03:19
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Identifiants

Citation

Ruslan Sadykov. A dominant class of schedules for malleable jobs in the problem to minimise the total weighted completion time. Computers and Operations Research, Elsevier, 2012, 39 (6), pp.1265-1270. 〈10.1016/j.cor.2011.02.023〉. 〈inria-00539875〉

Partager

Métriques

Consultations de la notice

181