Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

On Minimizing Average Weighted Completion Time: A PTAS for Scheduling General Multiprocessor Tasks

Aleksei V. FishkinContact Information, Klaus JansenContact Information and Lorant PorkolabContact Information

(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

Contact Information Aleksei V. Fishkin
Email: avf@informatik.uni-kiel.de

Contact Information Klaus Jansen
Email: kj@informatik.uni-kiel.de

Contact Information Lorant Porkolab
Email: lorant.porkolab@uk.pwcglobal.com
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb19
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)