Abstract
In the classical scheduling theory, it is widely assumed that a task can be processed by only one processor at a time. With the rapid development of technology, this assumption is no longer valid. In this work we present a problem of scheduling tasks, each of which requires for its processing a set of processors simultaneously and which can be executed on several alternative sets of processors. Scheduling algorithms based on dynamic and linear programming are presented that construct minimum length non-preemptive and preemptive schedules, respectively. Results of computational experiments are also reported.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M.J. Atallah, C. Lock Black and D.C. Marinescu, Models and algorithms for coscheduling computer-intensive tasks on a network of workstations, J. Parallel Distributed Comput. 16(1992)319–327.
K.R. Baker,Introduction to Sequencing and Scheduling, (Wiley, New York, 1974).
L. Bianco, J. Blażewicz, P. Dell'Olmo and M. Drozdowski, Scheduling preemptive multiprocessor tasks on dedicated processors, Perf. Eval. 20(1994)361–371.
G. Bozoki and J.P. Richard, A branch-and-bound algorithm for continuous-process task shop scheduling problem, AIIE Trans. 2(1970)246–252.
J. Blażewicz, W. Cellary, R. Slowiński and J. Węglarz,Scheduling under Resource Constraints: Deterministic Models (J.C. Baltzer, Basel, 1986).
J. Blażewicz, P. Dell'Olmo, M. Drozdowski and M.G. Speranza, Scheduling multiprocessor tasks on three dedicated processors, IPL 41(1992)275–280.
J. Blażewicz, M. Drabowski and J. Węglarz, Scheduling multiprocessor tasks to minimize schedule length, IEEE Trans. Comput. C-35(1986)389–393.
J. Blażewicz, M. Drozdowski, G. Schmidt and D. de Werra, Scheduling independent multiprocessor tasks on a uniformk-processor system, Parallel Comput. 20(1994)15–28.
J. Blażewicz, K. Ecker, G. Schmidt and J. Węglarz,Scheduling in Computer and Manufacturing Systems (Springer, New York, 1993).
J. Blażewicz, J.K. Lenstra and A.H.G. Rinnooy Kan, Scheduling subject to resource constraints: Classification of complexity, Discr. Appl. Math. 5(1983)11–24.
G.I. Chen and T.H. Lai, Preemptive scheduling of independent jobs on a hypercube, IPL 28(1988)201–206.
E.G. Coffman, Jr. (ed.),Computer and Job-Shop Scheduling Theory (Wiley, New York, 1976).
J. Du and J.Y.-T. Leung, Complexity of scheduling parallel task systems, SIAM J. Discr. Math. 2(1989)473–487.
R.I. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discr. Math. 5(1979)287–326.
D.G. Feitelson and L. Rudoloh, Gang scheduling performance benefits for fine-grain synchronization, J. Parallel Distributed Comput. 16(1992)306–318.
R. Jain, K. Somalwar, J. Werth and J.C. Browne, Scheduling parallel I/O operations in multiple bus systems, J. Parallel Distributed Comput. 16(1992)352–362.
H. Krawczyk and M. Kubale, An approximation algorithm for diagnostic test scheduling in multicomputer systems, IEEE Trans. Comput. C-34(1985)869–872.
M. Kubale, The complexity of scheduling independent two-processor tasks on dedicated processors, IPL 24(1987)141–147.
M. Kubale, Preemptive scheduling of two-processor tasks on dedicated processors, Zeszyty Naukowe Politechniki Śląskiej, Seria: Automatyka z. 100, No. 1082 (1990) 147–153, in Polish.
J. Plehn, Preemptive scheduling of independent jobs with release times and deadlines on a hypercube IPL 34(1990)161–166.
B. Veltman, B.J. Lageweg and J.K. Lenstra, Multiprocessor scheduling with communication delays, Parallel Comput. 16(1990)173–182.
B. Veltman, Multiprocessor scheduling with communication delays, Ph.D. Thesis, CWI, Amsterdam (1993).
Q. Wang and K.H. Cheng, A heuristic of scheduling parallel tasks and its analysis, SIAM J. Comput. 21(1992)281–294.
Author information
Authors and Affiliations
Additional information
This research was partially supported by a KBN grant and by project CRIT.
Rights and permissions
About this article
Cite this article
Bianco, L., Blazewicz, J., Dell'Olmo, P. et al. Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors. Ann Oper Res 58, 493–517 (1995). https://doi.org/10.1007/BF02057160
Issue Date:
DOI: https://doi.org/10.1007/BF02057160