Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
复制标题
DOI：
10.1287/moor.17.1.22
复制
发表时间：
1992-02
期刊：
影响因子：
--
通讯作者：
Leslie A. Hall;D. Shmoys
中科院分区：
文献类型：
--
作者：
Leslie A. Hall;D. Shmoys
本文研究了一类带发布日期和交货期的工件在同一台机器上的排序问题。对于工件间有优先约束的问题，我们给出了一个4/3近似算法，对于无优先约束的问题，我们给出了两个多项式近似算法。在每个算法的核心是杰克逊的规则-一个简单的，但看似强大的启发式的问题。
We consider the scheduling problem in which jobs with release dates and delivery times are to be scheduled on one machine. We present a 4/3-approximation algorithm for the problem with precedence constraints among the jobs, and two polynomial approximation schemes for the problem without precedence constraints. At the core of each of the algorithms presented is Jackson's Rule-a simple but seemingly robust heuristic for the problem.