Approximation algorithms for shop scheduling problems with minsum objective
Approximation algorithms for shop scheduling problems with minsum objective
复制标题
具有最小和目标的车间调度问题的近似算法
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
M. Sviridenko
中科院分区：
文献类型：
--
作者：
M. Queyranne;M. Sviridenko
我们考虑了一类一般的多处理机车间调度问题，无论是抢占的还是非抢占的，具有工序之间的优先约束，具有作业或工序的发布日期，以及一类包括作业、工序和阶段完成时间的加权和的目标函数。我们给出了一种通用的近似方法，它结合了操作完成时间的线性规划松弛，以及没有发布日期的最大完工时间版本的任何算法。如果后者产生的调度的完工时间不大于ρ乘以由所有阶段平均负荷(或拥塞)和作业长度(或扩张)中的最大值组成的‘平凡下界’，则我们的方法产生一个可行的调度，其最小和目标不大于2Eρ乘以最优的2E≈5.44。具体地，这导致了具有多对数性能保证的多项式时间算法，用于最小和多处理机DAG-Shop问题J(P)|Rij，Dagj|ΣSwSCs，其中ΣSwSCs是一般的最小和目标，包括操作和作业完成时间、阶段完工时间和其他的加权和，而对于特殊情况J∥ΣCj，F(P)|Rj|ΣwjCj和O∥ΣCj，而最著名的早期性能保证是O(M)(其中m是阶段数)。我们还得到了单位加工时间和加权工序(或作业)完成时间目标的无圈作业车间问题J|pij=1，无圈-dagj|Σ的O(1)性能保证。我们的结果推广到一类更广泛的最小和目标函数，包括一些与负载平衡有关的凸目标。然后，我们给出了一个改进的5.83-近似算法来求解具有总加权作业完成时间目标的开放车间问题O|Rj|ΣwjCj。最后，我们给出了一个非常简单的方法，该方法给出了具有m个单处理机阶段和总加权作业完成时间目标的各种作业车间问题(抢占式、非抢占式和无等待)的O(M)近似算法。版权所有©2002 John Wiley&Sons，Ltd.
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 is a 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.