Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times

Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times

0.00 Avg rating0 Votes
Article ID: iaor20171911
Volume: 20
Issue: 2
Start Page Number: 115
End Page Number: 127
Publication Date: Apr 2017
Journal: Journal of Scheduling
Authors: ,
Keywords: scheduling, manufacturing industries, combinatorial optimization
Abstract:

We revisit the classic problem of preemptive scheduling on m uniformly related machines. In this problem, jobs can be arbitrarily split into parts, under the constraint that every job is processed completely, and that the parts of a job are not assigned to run in parallel on different machines. We study a new objective which is motivated by fairness, where the goal is to minimize the sum of the two maximal job completion times. We design a polynomial time algorithm for computing an optimal solution. The algorithm can act on any set of machine speeds and any set of input jobs. The algorithm has several cases, many of which are very different from algorithms for makespan minimization (algorithms that minimize the maximum completion time of any job), and from algorithms that minimize the total completion time of all jobs.

Reviews

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