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.
Supported in part by DFG - Graduiertenkolleg “Effiziente Algorithmen und Mehrskalenmethoden” and by EU project APPOL “Approximation and On-line Algorithms”, IST-1999-14084
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Millis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko, Approximation schemes for minimizing average weighted completion time with release dates, Proceedings 40th IEEE Symposium on Foundations of Computer Science (1999), 32–43.
F. Afrati, E. Bampis, A. V. Fishkin, K. Jansen, C. Kenyon, Scheduling to minimize the average completion time of dedicated tasks, Proceedings 20th Conference on Foundations of Software Technology and Theoretical Computer Science, LNCS 1974, Springer Verlag (2000), 454–464.
A. K. Amoura, E. Bampis, C. Kenyon, and Y. Manoussakis, Scheduling independent multiprocessor tasks, Proceedings 5th European Symposium on Algorithms, LNCS 1284, Springer Verlag (1997), 1–12.
F. Afrati, E. Bampis, C. Kenyon and I. Milis, A PTAS for the average weighted completion time problem on unrelated machines, Journal of Scheduling 3 (2000), 323–332.
A. Bar-Noy, M. Bellare, M. M. Halldórsson, H. Shachnai, and T. Tamir, On chromatic sums and distributed resource allocation, Information and Computation 140 (1998), 183–202.
A. Bar-Noy and M. M. Halldórsson and G. Kortsarz and R. Salman and H. Shachnai, Sum multicoloring of graphs, Proceedings 7th European Symposium on Algorithms, LNCS 1643, Springer Verlag (1999), 390–401.
J. L. Bruno, E. G. Coffman, Jr., R. Sethi, Algorithms for minimizing mean flow time, Proceedings of the IFIP Congress, North-Holland, Amsterdam, (1974), 504–510.
X. Cai, C.-Y. Lee, and C.-L. Li, Minimizing total completion time in two-processor task systems with prespecified processor allocation, Naval Research Logistics 45 (1998), 231–242.
S. Chakrabarti, C. A. Philips, A. S. Schulz, D. B. Shmoys, C. Stein, and J. Wein, Improved scheduling algorithms for minsum criteria, Proceedings 23rd International Colloquium on Automata, Languages and Programming, LNCS 1099, Springer Verlag (1996), 646–657.
J. Chen and A. Miranda, A polynomial time approximation scheme for general multiprocessor job scheduling, Proceedings 31st ACM Symposium on the Theory of Computing (1999), 418–427.
J. Du and J. Leung, Complexity of scheduling parallel task systems, SIAM Journal on Discrete Mathematics 2 (1989), 473–487.
U. Feige and J. Kilian, Zero-knowledge and the chromatic number, in Journal of Computer and System Science 57(2) (1998), 187–199.
A. V. Fishkin, K. Jansen, L. Porkolab, On minimizing average weighted completion time of multiprocessor tasks with release dates, to appear on ICALP01.
M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, CA, 1979.
L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein, Scheduling to minimize average time: Offline and online algorithm, Mathematics of Operation Research 22 (1997), 513–544.
J. A. Hoogeveen, S. L. Van de Velde, and B. Veltman, Complexity of scheduling multiprocessor tasks with prespecified processor allocations, Discrete Applied Mathematics 55 (1994), 259–272.
K. Jansen and L. Porkolab, General multiprocessor task scheduling: approximate solution in linear time, Proceedings 6th International Workshop on Algorithms and Data Structures, LNCS 1663, Springer Verlag (1999), 110–121.
M. Skutella and G. J. Woeginger, A PTAS for minimizing the weighted sum of job completion times on parallel machines, Proceedings 31st ACM Symposium on Theory of Computing (1999), 400–407.
W. E. Smith, Various optimizers for single-stage production, Naval Research Logistic Quarterly 3 (1956), 59–66.
J. Turek, W. Ludwig, J. Wolf, and P. Yu, Scheduling parallel tasks to minimize average response times, Proceedings 5th ACM-SIAM Symposium on Discrete Algorithms (1994), 112–121.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fishkin, A.V., Jansen, K., Porkolab, L. (2001). On Minimizing Average Weighted Completion Time: A PTAS for Scheduling General Multiprocessor Tasks. In: Freivalds, R. (eds) Fundamentals of Computation Theory. FCT 2001. Lecture Notes in Computer Science, vol 2138. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44669-9_56
Download citation
DOI: https://doi.org/10.1007/3-540-44669-9_56
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42487-1
Online ISBN: 978-3-540-44669-9
eBook Packages: Springer Book Archive