SADYKOV, Ruslan

doi:10.1016/j.cor.2011.02.023

Métadonnées

Licence d’utilisation du document

SADYKOV, Ruslan
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]

Langue

Article de revue

Ce document a été publié dans

Computers and Operations Research. 2012, vol. 39, n° 6, p. 1265-1270

Elsevier

Résumé en anglais

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.< Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

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

Langue

Ce document a été publié dans

Résumé en anglais

URI

DOI

Origine

Unités de recherche