Scheduling a Single Machine to Minimize the Number of Late Jobs
Scheduling a Single Machine to Minimize the Number of Late Jobs
复制标题
DOI：
--
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
E. Lawler
中科院分区：
文献类型：
--
作者：
E. Lawler
假设n个作业，每个作业都有特定的发布日期、到期日和加工时间，计划由一台机器处理，目标是最小化到到期日仍未完成的作业数量。以两个算法和一个NP完备性证明的形式给出了三个结果。我们的第一个结果是证明了如果发货日期和到期日是“相容的”，即相似的排序，那么在所有发货日期相同的情况下，通过一个自然推广的Moore的过程，可以在O(Nlogn)时间内找到一个最优调度。这一结果改进了Kise、Ibaraki和Mine对该问题的O(n平方)解。对于我们的第二个结果，在发布日期和到期日之间没有假定特定的关系，并且允许时间表是抢先的。我们证明了在O(n立方体W立方体)时间内可以找到一个最小化延迟作业加权数量的调度，其中W是分配给作业的整数权重之和。如果作业是未加权的，那么实际上W=n，时间界减少到O(n到6)，从而给出了一个问题的多项式有界算法，该问题的求解过程以前是未知的。对于我们的第三个结果，我们假设所有的发布日期都是相等的，并且每个作业除了其到期日之外都有一个截止日期。我们证明了在遵守所有的最后期限的同时最小化延迟作业的数量(相对于交货期)是一个NP难问题。这一结果解决了J.Sidney的一个结果提出的一个悬而未决的问题。
Suppose n jobs, each with a specified release date, due date and processing time, are to be scheduled for processing by a single machine, with the objective of minimizing the number of jobs that are not completed by their due dates. Three results, in the form of two algorithms and one NP-completeness proof, are presented. Our first result is to show that if release dates and due dates are "compatible," I. e. similarly ordered, an optimal schedule can be found in O(n log n) time by a procedure that is a natural generalization of that of Moore for the case in which all release dates are equal. This result improves on an O(n squared) solution to this problem by Kise, Ibaraki and Mine. For our Second result, no particular relationship is assumed between the release dates and the due dates and the schedule is allowed to be preemptive. We show that a schedule minimizing the weighted number of late jobs can be found in O(n cubed W cubed) time where W is the sum of the integer weights assigned to the jobs. If the jobs are unweighted, then in effect W=n and the time bound reduces to O(n to the 6), thereby yielding a polynomial-bounded algorithm for a problem for which no such solution procedure was previously known. For our third result, we suppose that all release dates are equal and that each job has a deadline in addition to its due date. We show that it is an NP-hard problem to minimize the number of late jobs (with respect to due dates) while observing all deadlines. This result resolves an open question suggested by a result of J. Sidney.