Scheduling Independent Tasks on Non-Identical Parallel Machines to Minimize Mean Flow-time
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1974
- Accession Number
- AD0784894
Entities
People
- Douglas S Clark
Organizations
- Carnegie Mellon University