New and improved algorithms for minsum shop scheduling

We consider a general class of multiprocessor shop scheduling problems with a reinsure objective, and present approxima-tion methods based on linear programming relaxations in the operation completion times. These LP relaxations use new classes of valid inequalities for multistage jobs. We first con-sider open shop problems with total weighted job completion time objective. For the nonpreemptive problem O[ [ ~ wj Cj, we introduce "LP-based precedence constraints " and derive a 5.83-approximation algorithm. For its preemptive ver-sion, O[pmtn [ y~wjCj, we show that a simple job-based greedy algorithm, using directly the LP solution, yields a 3o approximation. We then consider a general class of multipro-cessor shop scheduling problems, preemptive or nonpreemp-tive, with precedence constraints between operations, with job or operation release dates, and with a general reinsure objective. This class of objectives includes, among others, weighted sums of operations completion times, job comple-tion times, stage mal~espans and the overall makespan. We combine the LP relaxation with two known techniques: (i) partitioning the set of operations using time intervals with geometrically increasing lengths; and (ii) an approximation algorithm for the makespan version of these problems with-out release dates. When the latter produces a schedule with makespan no larger than p times the "trivial lower bound" consisting of the largest of all stage average loads (or "con-gestion?) and job lengths (or "dilation"), we obtain a 2ep-approximation, where 2 e < 5.44. This leads in particular to a polylogarithmic approximation for the reinsure multi-processor dag-shop problem, and a O(1) approximation for the reinsure, acyclic job shop problem with unit processing times. These performance guarantees also bound the gap between optimum preemptive and nonpreernptive schedules for these problems. *Research supported by a research grant from NSERC (the Natural Sciences and Research Council of Canada) to the first author