Fearghal O'Donncha, Albert Akhriev, et al.
Big Data 2021
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.
Fearghal O'Donncha, Albert Akhriev, et al.
Big Data 2021
Ken C.L. Wong, Satyananda Kashyap, et al.
Pattern Recognition Letters
Arthur Nádas
IEEE Transactions on Neural Networks
Xiaoxiao Guo, Shiyu Chang, et al.
AAAI 2019