E1AR0002@SMUVM1.BITNET (Leff, Southern Methodist University) (09/27/87)
Three Practical Heuristic Functions for Task Scheduling:
Descriptions and Analyses
SPEAKER: Mingfang Wang (mwang%smu@csnet-relay) LOCATION: 315 SIC
Southern Methodist University TIME: 1:30 pm
ABSTRACT
Generally, task scheduling in a multi-processing environment is an
NP-hard problem. Here, three task scheduling algorithms using different
heuristic functions are presented and analyzed. These algorithms fall into
the category of \fIpriority list\fR methods. The algorithms are analyzed
both analytically and through simulations. The trade-off is between the time
complexity of the task scheduling and the optimalily of the schedule. A fast
algorithm can have a time complexity of O(n * log n),
but the task schedule produced by the algorithm is not as good as those with
time complexity of O(n^2).