TY - GEN
T1 - Scheduling unit-time tasks with limited resources
AU - Yao, Andrew Chi Chin
N1 - Publisher Copyright:
© by Springer-Verlag Berlin.
PY - 1975
Y1 - 1975
N2 - A set of tasks are to be scheduled on a multiprocessing system with s resources. Each task takes one unit time to complete, and requires certain amounts of resources. The schedule is to be consistent with a prescribed partial order relation on the task, and the total demand for each resource must not exceed a fixed amount at any instant. In this paper we analyze the worst-case behavior of several heuristic scheduling algorithms. Let ω be the time taken for executing all the tasks according to a priority list, and ω0 be the time required when scheduled in an optimal way. It is shown that, independent of the number of processors, ω/ω0 ≦ sω0/2 + 0(s) for any list. When certain heuristic algorithms are used to prepare the list, a significantly improved upper bound can be derived: ω/ω0 ≦ const. × s + 0(1). Some generalizations are possible to the case when the "unit-time" restriction is removed. When the partial order relation is empty, the problem becomes a natural generalization of the bin-packing problem. Tighter bounds for this special situation are given.
AB - A set of tasks are to be scheduled on a multiprocessing system with s resources. Each task takes one unit time to complete, and requires certain amounts of resources. The schedule is to be consistent with a prescribed partial order relation on the task, and the total demand for each resource must not exceed a fixed amount at any instant. In this paper we analyze the worst-case behavior of several heuristic scheduling algorithms. Let ω be the time taken for executing all the tasks according to a priority list, and ω0 be the time required when scheduled in an optimal way. It is shown that, independent of the number of processors, ω/ω0 ≦ sω0/2 + 0(s) for any list. When certain heuristic algorithms are used to prepare the list, a significantly improved upper bound can be derived: ω/ω0 ≦ const. × s + 0(1). Some generalizations are possible to the case when the "unit-time" restriction is removed. When the partial order relation is empty, the problem becomes a natural generalization of the bin-packing problem. Tighter bounds for this special situation are given.
UR - https://www.scopus.com/pages/publications/84912808859
U2 - 10.1007/3-540-07135-0_107
DO - 10.1007/3-540-07135-0_107
M3 - 会议稿件
AN - SCOPUS:84912808859
SN - 9783540071358
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 17
EP - 36
BT - Parallel Processing - Proceedings of the Sagamore Computer Conference
A2 - Feng, Tse-Yun
PB - Springer Verlag
T2 - International Sagamore Computer Conference on Parallel Processing, 1974
Y2 - 20 August 1974 through 23 August 1974
ER -