Keywords
Multiprocessors, Production scheduling
Abstract
The problem of scheduling tasks onto multiprocessor systems has increasing practical importance as more applications are being addressed with multiprocessor systems. Actual applications and multiprocessor systems have many characteristics which become constraints to the general scheduling problem of minimizing the schedule length. These practical constraints include precedence relations and communication delays between tasks, yet few researchers have considered both these constraints when developing schedulers.
This work examines a more general multiprocessor scheduling problem, which includes these practical scheduling constraints, and develops a new scheduling heuristic using a list scheduler with dynamically computed priorities. The dynamic priority heuristic is compared against an optimal scheduler and against other researchers’ approaches for thousands of randomly generated scheduling problems. The dynamic priority heuristic produces schedules with lengths which are 10% to 20% over optimal on the average. The dynamic priority heuristic performs better than other researchers’ approaches for scheduling problems with the practical constraints. We conclude that it is important to consider practical constraints in the design of a scheduler and that a simple heuristic can still achieve good performance in this area.
Notes
If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu
Graduation Date
1986
Semester
Spring
Advisor
Mukherjee, Amar
Degree
Doctor of Philosophy (Ph.D.)
College
College of Arts and Sciences
Department
Computer Science
Format
Pages
127 p.
Language
English
Rights
Public Domain
Length of Campus-only Access
None
Access Status
Doctoral Dissertation (Open Access)
Identifier
DP0020311
STARS Citation
Donovan, Kenneth Burton, "Multiprocessor scheduling with practical constraints" (1986). Retrospective Theses and Dissertations. 4901.
https://stars.library.ucf.edu/rtd/4901
Accessibility Status
Searchable text