A Greedy Heuristic for Single Machine Sequencing with Precedence Constraints
提出一个贪心启发式算法，解决带优先约束的单机排序问题，适用于多种加权或非加权的完工时间、流程时间等优化目标，在68个测试问题中58个找到最优解，比精确算法更易实现且耗时更少。
We present a greedy heuristic for the n job/1 machine scheduling problem with precedence constraints. This method is useful whenever the manager's optimization criteria is the sum of weighted or unweighted completion times, the sum of weighted or unweighted flow times, (with or without release dates), the sum of weighted or unweighted working times, the sum of weighted or unweighted lateness, average completion time, average flow time, average waiting time or average lateness. The greedy heuristic found the optimal solution for 58 of 68 test problems for which a branch and bound method was used to find the optimal solution. The heuristic is, of course, much easier to implement (and executes in less time). The greedy heuristic fared well in comparison with a simple myopic heuristic presented by Morton and Dharan (Morton. T. E., B. G. Dharan. 1978. Algoristics for single machine sequencing with precedence constraints. Management Sci. 24 (10) 1011–1020.).