zbMATH — the first resource for mathematics

An iterative algorithm for scheduling UET tasks with due dates and release times. (English) Zbl 1059.90078
A classical scheduling problem involving Unit Execution Time (UET) tasks is considered. A new polynominal-time iterative algorithm is presented for scheduling UET task system with parallel identical processors, precedence constraints, release times, and the criterion of maximum lateness. For the maximum lateness and makespan problems the algorithm allows to achieve the performance guarantees previously known only for the problems without release times.

90B35 Deterministic scheduling theory in operations research
Full Text: DOI
[1] Braschi, B.; Trystram, D., A new insight into the coffman – graham algorithm, SIAM journal on computing, 23, 662-669, (1994) · Zbl 0827.90069
[2] Brucker, P., Scheduling algorithms, (2001), Springer Berlin · Zbl 1051.90011
[3] Chen, B.; Potts, C.N.; Woeginger, G.J., A review of machine scheduling: complexity, algorithms and approximability, (), 21-169 · Zbl 0944.90022
[4] Garey, M.R.; Johnson, D.S., Scheduling tasks with nonuniform deadlines on two processors, Journal of the association for computing machinery, 23, 461-467, (1976) · Zbl 0338.68048
[5] Garey, M.R.; Johnson, D.S., Two-processor scheduling with start-time and deadlines, SIAM journal on computing, 6, 416-426, (1977) · Zbl 0369.90053
[6] Lam, S.; Sethi, R., Worst case analysis of two scheduling algorithms, SIAM journal on computing, 6, 518-536, (1977) · Zbl 0374.90031
[7] Ullman, J.D., NP-complete scheduling problems, Journal of computer and system sciences, 10, 384-393, (1975) · Zbl 0313.68054
[8] Y. Zinder, G. Singh, Preemptive scheduling on parallel processors with due dates. Research report 02-01, Department of Mathematical Sciences, University of Technology, Sydney, 2002 · Zbl 1080.90047
[9] Zinder, Y.; Roper, D., An iterative algorithm for scheduling unit-time operations with precedence constraints to minimise the maximum lateness, Annals of operations research, 81, 321-340, (1998) · Zbl 0908.90178
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.