UET scheduling

unit-execution-time scheduling

A special topic in scheduling theory, in which unit-execution-time (UET) systems are studied. In such a system, all jobs (tasks) or its operations have an equal processing requirement. Techniques in UET scheduling can very often be applied to pre-emptive scheduling, where the processing of a job can be interrupted and resumed later, although jobs can have different processing times. Pre-emptive scheduling can be regarded to some extent as similar to UET scheduling.

In terms of polynomial solvability, UET scheduling for uniform machines (processors), where machines are in parallel and can differ in speed, is simple for almost-all regular objective functions and, in most cases, even with release dates [a1], [a4], at which jobs become available for processing, provided that there are no other complications.

UET scheduling for non-parallel machines or in the presence of general precedence constraints is intractably difficult, while only a handful of special cases of such problems can be solved efficiently, notably the problem of scheduling identical machines with tree-type precedence constraints for minimizing the makespan or average job completion time [a3], [a2]. UET scheduling for non-parallel machines is at least as difficult as scheduling for identical parallel machines with arbitrary job processing times, [a5]. Nevertheless, study of UET scheduling helps understand the problem structure when differences among the processing times of jobs are dominated by other constraints.

References

[a1]	M.I. Dessouky, B.J. Lageweg, J.K. Lenstra, S.L. Van de Velde, "Scheduling identical jobs on uniform parallel machines" Statistica Neerlandica , 44 (1990) pp. 115–123
[a2]	M.R. Garey, D.S. Johnson, R.E. Tarjan, M. Yannakakis, "Scheduling opposing forests" SIAM J. Algebra Discrete Math. , 4 (1983) pp. 72–93
[a3]	T.C. Hu, "Parallel sequencing and assembly line problems" Oper. Res. , 9 (1961) pp. 841–848
[a4]	E.L. Lawler, "Sequencing to minimize the weighted number of tardy jobs" Revue Française d'Automatique Informatique: Recherche Operationnelle , S10 (1976) pp. 27–33
[a5]	V.G. Timkovsky, "Identical parallel machines vs. unit-time shops, preemptions vs. chains, and other offsets in scheduling complexity" Unpublished manuscript (1998)