Approximation algorithms for shop scheduling problems with minsum objective

Abstract

We consider a general class of multiprocessor shop scheduling problems, preemptive or non-preemptive, with precedence constraints between operations, with job or operation release dates, and with a class of objective functions including weighted sums of job, operations and stage completion times. We present a general approximation method combining a linear programming relaxation in the operation completion times, with any algorithm for the makespan version of these problems without release dates. If the latter produces a schedule with makespan no larger than ρ times the 'trivial lower bound' consisting of the largest of all stage average loads (or 'congestion') and job lengths (or 'dilation'), then our method produces a feasible schedule with minsum objective no larger than 2eρ times the optimum where 2e ≈ 5.44. This leads, in particular, to a polynomial time algorithm with polylogarithmic performance guarantee for the minsum multiprocessor dag-shop problem J(P)|rij,dagj|∑swsCs where ∑swsCs general minsum objective including weighted sum of operation and job completion times, stages makespans and others, whereas the best known earlier performance guarantees were O(m) (where m is the number of stages) for the special cases J ∥ ∑ Cj, F(P)|rj∑ wjCj and O∥∑ Cj. We also obtain a O(1) performance guarantee for the acyclic job shop problem J|pij = 1, acyclic-dagj| ∑swsCs with unit processing times and weighted sum of operation (or job) completion time objective. Our results extend to a broad class of minsum objective functions including some convex objectives related to load balancing. We then present an improved 5.83-approximation algorithm for the open shop problem O|rj| ∑wjCj with total weighted job completion time objective. We conclude with a very simple method which yields O(m)-approximation algorithms for various job shop problems (preemptive, non-preemptive, and no-wait) with m single-processor stages and total weighted job completion time objective. Copyright © 2002 John Wiley & Sons, Ltd.