A dominant class of schedules for malleable jobs in the problem to minimise the total weighted completion time
SADYKOV, Ruslan
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
SADYKOV, Ruslan
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
< Leer menos
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Idioma
en
Article de revue
Este ítem está publicado en
Computers and Operations Research. 2012, vol. 39, n° 6, p. 1265-1270
Elsevier
Resumen en inglés
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 ...Leer más >
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.< Leer menos
Orígen
Importado de HalCentros de investigación