Accession Number:

AD0784894

Title:

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

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1974-06-01

Pagination or Media Count:

29.0

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.

Subject Categories:

  • Operations Research
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE