Scheduling Independent Tasks on Non-Identical Parallel Machines to Minimize Mean Flow-time
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
A collection of tasks having known processing time requirements on a set of non-identical parallel machines is to be scheduled so that the mean flow- time of the tasks is as small as possible. In this paper it is shown that a trivial extension of a simple algorithm for a restricted case performs well, and often optimally, in the general case. A principal result is that for every problem, some renumbering of the tasks will cause this algorithm to produce an optimal schedule. Upper bounds on the worst-case performance of the algorithm are given, and average performance is explored using Monte Carlo techniques.
- Operations Research
- Computer Hardware