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

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

0.00 Avg rating0 Votes
Article ID: iaor20119713
Volume: 39
Issue: 6
Start Page Number: 1265
End Page Number: 1270
Publication Date: Jun 2012
Journal: Computers and Operations Research
Authors:
Keywords: scheduling, combinatorial optimization
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.

Reviews

Required fields are marked *. Your email address will not be published.