Abstract
A malleable parallel task is one whose execution time is a function of the number of (identical) processors allotted to it. We study the problem of scheduling a set of n independent malleable tasks on an arbitrary number m of parallel processors and propose an asymptotic fully polynomial time approximation scheme. For any fixed ∈ > 0, the algorithm computes a non-preemptive schedule of length at most (1 + ∈) times the optimum (plus an additive term) and has running time polynomial in n,m and 1/∈.
Supported by EU Project APPOL I + II, Approximation and Online Algorithms, IST-1999-14084 and IST-2001-32012, by EU Research Training Network ARACNE, Approximation and Randomized Algorithms in Communication Networks, HPRNCT- 1999-00112 and by DAAD French-German Exchange Program Procope, Scheduling Malleable Tasks.
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
B. Baker, E. Coffman and R. Rivest, Orthogonal packings in two dimensions, SIAM Journal on Computing, 9(1980), 846–855.
K. Belkhale and P. Banerjee, Approximate algorithms for the partitionable independent task scheduling problem, International Conference on Parallel Processing (1990), Vol. 1, 72–75.
J. Blazewicz, W. Cellary, R. Slowinski, and J. Weglarz, Scheduling under resource constraints-deterministic models, Annals of Operations Research 7 (1986).
J. Blazewicz, M. Drabowski, and J. Weglarz, Scheduling multiprocessor tasks to minimize schedule length, IEEE Transactions on Computers, C-35-5 (1986), 389–393.
E. Coffman, M. Garey, D. Johnson and R. Tarjan, Performance bounds for leveloriented two dimensional packing algorithms, SIAM Journal on Computing, 9 (1980), 808–826.
M. Drozdowski, On the complexity of multiprocessor task scheduling, Bulletin of the Polish Academy of Sciences, 43 (1995), 381–392.
M. Drozdowski, Scheduling multiprocessor tasks-an overview, European Journal on Operations Research, 94 (1996), 215–230.
J. Du and J. Leung, Complexity of scheduling parallel task systems, SIAM Journal on Discrete Mathematics, 2 (1989), 473–487.
M.R. Garey and R. L. Graham, Bounds for multiprocessor scheduling with resource constraints, SIAM Journal on Computing 4 (1975), 187–200.
M.R. Garey, R. L. Graham, D. S. Johnson and A.C.-C. Yao, Resource constrained scheduling as generalized bin packing, Journal Combinatorial Theory A, 21 (1976), 251–298.
M. Garey and D. S. Johnson, Complexity results for multiprocessor scheduling under resource constraints, SIAM Journal on Computing 4 (1975), 397–411.
M.D. Grigoriadis, L. G. Khachiyan, L. Porkolab and J. Villavicencio, Approximate max-min resource sharing for structured concave optimization, SIAM Journal on Optimization, 11 (2001), 1081–1091.
M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer Verlag, Berlin, 1988.
K. Jansen and L. Porkolab, Linear-time approximation schemes for scheduling malleable parallel tasks, Algorithmica 32 (2002), 507–520.
K. Jansen and L. Porkolab, Computing optimal preemptive schedules for parallel tasks: Linear Programming Approaches, Proceedings 11th Annual International Symposium on Algorithms and Computation (2000), LNCS 1969, Springer Verlag, 398–409, and to appear in: Mathematical Programming.
K. Jansen and L. Porkolab, On preemptive resource constrained scheduling: polynomial-time approximation schemes, Proceedings 9th International Conference on Integer Programming and Combinatorial Optimization (2002), LNCS 2337, Springer Verlag, 329–349.
N. Karmarkar and R. M. Karp, An efficient approximation scheme for the one-dimensional bin packing problem, Proceedings 23rd IEEE Symposium on Foundations of Computer Science (1982), 312–320.
C. Kenyon and E. Remila, A near-optimal solution to a two-dimensional cutting stock problem, Mathematics of Operations Research 25 (2000), 645–656.
B. Korte and J. Vygen, Combinatorial optimization: Theory and Algorithms, Springer Verlag, Berlin, 2000.
E. Lawler, Fast approximation algorithms for knapsack problems, Mathematics of Operations Research, 4 (1979), 339–356.
J.K. Lenstra, D. B. Shmoys and E. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming, 24 (1990), 259–272.
W. Ludwig and P. Tiwari, Scheduling malleable and nonmalleable parallel tasks, Proceedings 5th ACM-SIAM Symposium on Discrete Algorithms (1994), 167–176.
G. Mounie, C. Rapine and D. Trystram, Efficient approximation algorithms for scheduling malleable tasks, Proceedings 11th ACM Symposium on Parallel Algorithms and Architectures (1999), 23–32.
S.A. Plotkin, D. B. Shmoys, and E. Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, 20 (1995), 257–301.
I. Schiermeyer, Reverse-Fit: A 2-optimal algorithm for packing rectangles, Proceedings 2nd European Symposium of Algorithms (1994), LNCS 855, 290–299.
A. Steinberg, A strip-packing algorithm with absolute performance bound two, SIAM Journal on Computing, 26 (1997), 401–409.
J. Turek, J. Wolf and P. Yu, Approximate algorithms for scheduling parallelizable tasks, Proceedings 4th ACM Symposium on Parallel Algorithms and Architectures (1992), 323–332.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jansen, K. (2002). Scheduling Malleable Parallel Tasks: An Asymptotic Fully Polynomial-Time Approximation Scheme. In: Möhring, R., Raman, R. (eds) Algorithms — ESA 2002. ESA 2002. Lecture Notes in Computer Science, vol 2461. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45749-6_50
Download citation
DOI: https://doi.org/10.1007/3-540-45749-6_50
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44180-9
Online ISBN: 978-3-540-45749-7
eBook Packages: Springer Book Archive