On Minimizing Average Weighted Completion Time: A PTAS for Scheduling General Multiprocessor Tasks
Aleksei V. Fishkin5
, Klaus Jansen5
and Lorant Porkolab6 
| (5) |
Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität zu Kiel, Olshausenstrasse 40, 24 098 Kiel, Germany |
| (6) |
Applied Decision Analysis, PricewaterhouseCoopers, 1 Embankment Place, London, WC2N 6RH, UK |
Abstract
We study the problem of scheduling n independent general multiprocessor tasks on a fixed number of processors, where the objective is to compute a non-preemptive
schedule minimizing the average weighted completion time. For each task, its execution time is given as a function of the
subset of processors assigned to the task. We propose here a polynomial-time approximation scheme for the problem that computes
a (1 + ε)-approximate solution in O(n log n) time for any fixed ε > 0 accuracy. This provides a generalization and integration of some recent polynomial-time approximation
schemes for scheduling jobs on unrelated machines [1,18] and multiprocessor tasks on dedicated processors [2], respectively, with the average weighted completion time objective, since the latter models are included as special cases
in our problem.
Keywords Parallel processing - scheduling - multiprocessor tasks
Supported in part by DFG - Graduiertenkolleg “Effiziente Algorithmen und Mehrskalenmethoden” and by EU project APPOL “Approximation
and On-line Algorithms”, IST-1999-14084
References secured to subscribers.