About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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.
Related
Conference paper
Tensorial change analysis using probabilistic tensor regression
Conference paper