Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!amdcad!ames!ucbcad!ucbvax!SMUVM1.BITNET!E1AR0002
From: E1AR0002@SMUVM1.BITNET (Leff, Southern Methodist University)
Newsgroups: comp.ai.digest
Subject: Seminar - Heuristic Functions for Task Scheduling (SMU)
Message-ID: <8709290655.AA09832@ucbvax.Berkeley.EDU>
Date: Sun, 27-Sep-87 00:55:00 EDT
Article-I.D.: ucbvax.8709290655.AA09832
Posted: Sun Sep 27 00:55:00 1987
Date-Received: Wed, 30-Sep-87 06:36:29 EDT
Sender: usenet@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 16
Approved: ailist@kl.sri.com

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).