Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms
Abstract
We consider scheduling monotonic moldable tasks on multiple platforms, where each platform contains a set of processors. A moldable task can be split into several pieces of equal size and processed simultaneously on multiple processors. Tasks are not allowed to be processed spanning over platforms. This scheduling model has many applications, ranging from parallel computing to the berth and quay crane allocation and the workforce assignment problem. We develop several approximation algorithms aiming at minimizing the makespan. More precisely, we provide a 2-approximation algorithm for identical platforms, a Fully Polynomial Time Approximation Scheme (FPATS) under the assumption of large processor counts and a 2-approximation algorithm for a fixed number of heterogeneous platforms. Most of the proposed algorithms combine a dual approximation scheme with a novel approach to improve the dual approximation algorithm. All results can be extended to the contiguous case, i.e., a task can only be executed by contiguously numbered processors.
References
[1]
Blazewicz J, Cheng TE, Machowiak M, and Oguz C Berth and quay crane allocation: a moldable task scheduling model Journal of the Operational Research Society 2011 62 7 1189-1197
[2]
Bougeret, M., Dutot, P. F., Jansen, K., Otte, C., & Trystram, D. (2010a). Approximating the non-contiguous multiple organization packing problem. In: IFIP International Conference on Theoretical Computer Science, (pp. 316–327). Springer.
[3]
Bougeret, M., Dutot, P. -F., Jansen, K., Otte, C., & Trystram, D. (2010b). A fast 5/2-approximation algorithm for hierarchical scheduling. In: European Conference on Parallel Processing, (pp. 157–167). Springer.
[4]
Bougeret M, Dutot P-F, Jansen K, Robenek C, and Trystram D Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms Discrete Mathematics, Algorithms and Applications 2011 3 04 553-586
[5]
Bougeret, M., Dutot, P. -F., Jansen, K., Robenek, C., & Trystram, D. (2012). Tight approximation for scheduling parallel jobs on identical clusters. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, (pp. 878–885). IEEE.
[6]
Bougeret M, Dutot P-F, Trystram D, Jansen K, and Robenek C Improved approximation algorithms for scheduling parallel jobs on identical clusters Theoretical Computer Science 2015 600 70-85
[7]
Brent RP The parallel evaluation of general arithmetic expressions Journal of the ACM (JACM) 1974 21 2 201-206
[8]
Caprara A, Kellerer H, and Pferschy U The multiple subset sum problem SIAM Journal on Optimization 2000 11 2 308-319
[9]
Dolgui A, Kovalev S, Kovalyov MY, Malyutin S, and Soukhal A Optimal workforce assignment to operations of a paced assembly line European Journal of Operational Research 2018 264 1 200-211
[10]
Drozdowski M Scheduling for parallel processing 2009 Springer
[11]
Du J and Leung JY-T Complexity of scheduling parallel task systems SIAM Journal on Discrete Mathematics 1989 2 4 473-487
[12]
Dutot, P. -F., Jansen, K., Robenek, C., & Trystram, D. (2013). A (2+ )-approximation for scheduling parallel jobs in platforms. In: European Conference on Parallel Processing, (pp. 78–89). Springer.
[13]
Dutton, R. A., Mao, W., Chen, J., & Watson III, W. (2008). Parallel job scheduling with overhead: A benchmark study. In: 2008 International Conference on Networking, Architecture, and Storage, (pp. 326–333). IEEE.
[14]
Hochbaum, D. S., & Shmoys, D. B. (1987). Using dual approximation algorithms for scheduling problems theoretical and practical results. (vol. 34, pp. 144–162), New York, NY, USA. Association for Computing Machinery.
[15]
Jansen K Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme Algorithmica 2004 PP 39 187-200
[16]
Jansen, K. (2012). A (3/2+) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 12, (pp. 224–235), New York, NY, USA. Association for Computing Machinery.
[17]
Jansen, K., & Land, F. (2018). Scheduling monotone moldable jobs in linear time. In: 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), (pp. 172–181).
[18]
Jansen K and Porkolab L Linear-time approximation schemes for scheduling malleable parallel tasks Algorithmica 2002 32 3 507-520
[19]
Jansen, K., & Rau, M. (2019a). Closing the gap for pseudo-polynomial strip packing. In: 27th Annual European Symposium on Algorithms (ESA 2019), vol. 144 of Leibniz International Proceedings in Informatics (LIPIcs), (pp. 62:1–62:14), Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[20]
Jansen, K., & Rau, M. (2019b). Linear time algorithms for multiple cluster scheduling and multiple strip packing. In: European Conference on Parallel Processing, (pp. 103–116). Springer.
[21]
Jansen K and Thöle R Approximation algorithms for scheduling parallel jobs SIAM Journal on Computing 2010 39 8 3571-3615
[22]
Jansen K and Trystram D Scheduling parallel jobs on heterogeneous platforms Electronic Notes in Discrete Mathematics 2016 55 9-12
[23]
Johannes B Scheduling parallel jobs to minimize the Makespan Journal of Scheduling 2006 9 5 433-452
[24]
Ludwig, W., & Tiwari, P. (1994). Scheduling malleable and nonmalleable parallel tasks. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, (pp. 167–176). Society for Industrial and Applied Mathematics.
[25]
Mounié, G., Rapine, C., & Trystram, D. (1999). Efficient approximation algorithms for scheduling malleable tasks. In: Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’99, (pp. 23–32), New York, NY, USA. Association for Computing Machinery.
[26]
Mounié G, Rapine C, and Trystram D A -approximation algorithm for scheduling independent monotonic malleable tasks SIAM Journal on Computing 2007 37 2 401-412
[27]
Pascual F, Rzadca K, and Trystram D Cooperation in multi-organization scheduling Concurrency and Computation: Practice and Experience 2009 21 7 905-921
[28]
Schwiegelshohn, U., Tchernykh, A., & Yahyapour, R. (2008). Online scheduling in grids. In: IEEE international symposium on parallel and distributed processing (IPDPS 2008), (pp. 1–10). IEEE.
[29]
Tchernykh, A., Ramírez, J. M., Avetisyan, A., Kuzjurin, N., Grushin, D., & Zhuk, S. (2005). Two level job-scheduling strategies for a computational grid. In: International Conference on Parallel Processing and Applied Mathematics, (pp. 774–781). Springer.
[30]
Turek, J., Wolf, J. L., & Yu, P. S. (1992). Approximate algorithms for scheduling parallelizable tasks. In: Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, (pp. 323–332).
[31]
Wu F, Zhang X, and Chen B An improved approximation algorithm for scheduling montonic moldable tasks European Journal of Operational Research 2022
[32]
Ye, D., Han, X., & Zhang, G. (2009). On-line multiple-strip packing. In: International Conference on Combinatorial Optimization and Applications, (pp. 155–165). Springer.
[33]
Zhuk S Approximate algorithms to pack rectangles into several strips Discrete Mathematics and Applications 2006 16 1 73-85
Recommendations
Online scheduling of moldable parallel tasks
In this paper, we study an online scheduling problem with moldable parallel tasks on m processors. Each moldable task can be processed simultaneously on any number of processors of a parallel computer, and the processing time of a moldable task depends ...
Approximation algorithms for parallel machine scheduling with linear deterioration
This paper deals with a parallel machine scheduling problem. Different from fixed processing time assumption in the classical scheduling, a job's processing time is a simple linear increasing function of its starting time. The aim is makespan ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 25 January 2023
Accepted: 21 December 2022
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in