
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.).
Numerical mathematical programming methods, Deterministic scheduling theory in operations research, branch and bound method, test problems, single machine sequencing, greedy, programming: integer algorithms, branch and bound [production/scheduling, heuristic], greedy heuristic, precedence constraints
Numerical mathematical programming methods, Deterministic scheduling theory in operations research, branch and bound method, test problems, single machine sequencing, greedy, programming: integer algorithms, branch and bound [production/scheduling, heuristic], greedy heuristic, precedence constraints
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 10 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
