Hall, Leslie A.; Shmoys, David B. Jackson’s rule for single-machine scheduling: Making a good heuristic better. (English) Zbl 0781.90052 Math. Oper. Res. 17, No. 1, 22-35 (1992). The authors consider the scheduling problem in which jobs with release dates and delivery times are to be scheduled on one machine. They 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 Jackson’s Rule – a simple but seemingly robust heuristic for the problem – is presented. Reviewer: R.Słowinski (Poznań) Cited in 1 ReviewCited in 54 Documents MSC: 90B35 Deterministic scheduling theory in operations research 90-08 Computational methods for problems pertaining to operations research and mathematical programming Keywords:release dates; delivery times; one machine; precedence constraints; polynomial approximation schemes PDFBibTeX XMLCite \textit{L. A. Hall} and \textit{D. B. Shmoys}, Math. Oper. Res. 17, No. 1, 22--35 (1992; Zbl 0781.90052) Full Text: DOI Link