Abstract
Given a set of time slots and jobs, each of which has a degree of parallelism, an interval constraint (typically an arrival time and a deadline), and a processing time, we consider the problem of minimizing the number of machines for scheduling all the jobs while satisfying the constraints. This paper starts with a Linear Programming (LP) formulation and argues that its decision version is with an integral polyhedron. Meanwhile, we determine the problem’s feasibility with the LP, whether the given jobs can be accommodated by a given number of machines over allocated time slots, based on the property of the integrality. Then, we show that the feasibility leads to an LP-based algorithm, in which the optimal solution can be obtained in polynomial time. Moreover, our algorithm can also optimally compute a schedule to the problem rather than merely determining the minimum number of required machines, which compares favorably to the Earliest Deadline First (EDF) algorithm and the Least Laxity First (LLF) algorithm in solution quality.
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
Similar content being viewed by others
References
Azar, Y., Cohen, S.: An improved algorithm for online machine minimization. Oper. Res. Lett. 46(1), 128–133 (2018)
van Bevern, R., Niedermeier, R., Suchý, O.: A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack. J. Scheduling 20(3), 255–265 (2016). https://doi.org/10.1007/s10951-016-0478-9
Chen, C., Zhang, H., Xu, Y.: Online machine minimization with lookahead. J. Comb. Optim. (2020). https://doi.org/10.1007/s10878-020-00633-w
Chen, L., Megow, N., Schewior, K.: An \(\cal{O}\)(log m)-competitive algorithm for online machine minimization. SIAM J. Comput. 47(6), 2057–2077 (2018)
Chuzhoy, J., Guha, S., Khanna, S., Naor, J.S.: Machine minimization for scheduling jobs with interval constraints. In: 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 81–90. IEEE (2004)
Cieliebak, M., Erlebach, T., Hennecke, F., Weber, B., Widmayer, P.: Scheduling with release times and deadlines on a minimum number of machines. In: Levy, J.-J., Mayr, E.W., Mitchell, J.C. (eds.) TCS 2004. IIFIP, vol. 155, pp. 209–222. Springer, Boston, (2004). https://doi.org/10.1007/1-4020-8141-3_18
Dertouzos, M.L., Mok, A.K.: Multiprocessor online scheduling of hard-real-time tasks. IEEE Trans. Softw. Eng. 15(12), 1497–1506 (1989)
Devanur, N., Makarychev, K., Panigrahi, D., Yaroslavtsev, G.: Online algorithms for machine minimization. CoRR abs/1403.0486 (2014)
Garey, M.R., Johnson, D.S.: Two-processor scheduling with start-times and deadlines. SIAM J. Comput. 6(3), 416–426 (1977)
George, L., Rivierre, N., Spuri, M.: Preemptive and non-preemptive real-time uniprocessor scheduling. In: Ph.D. thesis, Inria (1996)
Horn, W.: Some simple scheduling algorithms. Naval Res. Logistics Q. 21(1), 177–185 (1974)
Im, S., Moseley, B., Pruhs, K., Stein, C.: An \(\cal{O}\)(log log m)-competitive algorithm for online machine minimization. In: 2017 IEEE Real-Time Systems Symposium (RTSS), pp. 343–350. IEEE (2017)
Kao, M.-J., Chen, J.-J., Rutter, I., Wagner, D.: Competitive design and analysis for machine-minimizing job scheduling problem. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 75–84. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35261-4_11
Korte, B., Vygen, J., Korte, B., Vygen, J.: Combinatorial optimization, vol. 2. Springer, Berlin (2012)
Lewis, H.R.: Computers and intractability: a guide to the theory of np-completeness Siam Rev. 24(1), 90 (1983)
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Courier Corporation, New York (1998)
Phillips, C.A., Stein, C., Torng, E., Wein, J.: Optimal time-critical scheduling via resource augmentation. In: Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, pp. 140–149 (1997)
Raghavan, P., Tompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365–374 (1987)
Saha, B.: Renting a cloud. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013), vol. 24, pp. 437–448. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2013)
Acknowledgements
The authors are supported by Natural Science Foundation of China (No. 61772005), Outstanding Youth Innovation Team Project for Universities of Shandong Province (No. 2020KJN008), Natural Science Foundation of Fujian Province (No. 2020J01845) and Educational Research Project for Young and Middle-aged Teachers of Fujian Provincial Department of Education (No. JAT190613).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Xu, X., Guo, L. (2021). Efficient Algorithms for Scheduling Parallel Jobs with Interval Constraints in Clouds. In: Du, DZ., Du, D., Wu, C., Xu, D. (eds) Combinatorial Optimization and Applications. COCOA 2021. Lecture Notes in Computer Science(), vol 13135. Springer, Cham. https://doi.org/10.1007/978-3-030-92681-6_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-92681-6_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92680-9
Online ISBN: 978-3-030-92681-6
eBook Packages: Computer ScienceComputer Science (R0)