Scheduling Independent Tasks on Non-Identical Parallel Machines to Minimize Mean Flow-time,

摘要

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