We consider the open shop scheduling problem subject to speed scaling and energy consumption. The computational complexity is analyzed and approaches to solving various variants of the problem are proposed. The algorithms use a two-stage scheduling scheme. At the first stage, bounds on the objective function and processing times of jobs are constructed. At the second stage, the speed scaling problem is reduced to the classic problem with fixed job speeds, and list-type methods are applied for scheduling. As a result, NP-hardness is proved in the general case, and polynomial-time exact and approximation algorithms are proposed for the practically important special cases when preemptions are allowed or not, when the set of speeds is discrete or continuous, and when energy consumption is bounded or optimized. A model of mixed integer convex programming is constructed based on continuous time representation using the notion of event points.
Keywords: open shop, schedule, NP-hardness, algorithm
Received October 6, 2024
Revised October 20, 2024
Accepted October 28, 2024
Funding Agency: The research was supported by Russian Science Foundation (project no. 22-71-10015, https://rscf.ru/en/project/22-71-10015/).
Yulia Victorovna Zakharova, Cand. Sci. (Phys.-Math.), Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Omsk Department, Omsk, 644099 Russia; Dostoevsky Omsk State University, Omsk, 644077 Russia, e-mail: yzakharova@ofim.oscsbras.ru
REFERENCES
1. Kubiak W. A book of open shop scheduling. Cham, Springer Internat. Publ., 2022, 290 p. doi: 10.1007/978-3-030-91025-9
2. Tanaev V.S., Sotskov Y.N., Strusevich V.A. Scheduling theory, multi-stage systems. Springer Dordrecht, 1994. 406 p. Original Russian text was published in TanaevV.S., SotskovY.N., StrusevichV.A. Teoriya raspisanij: mnogostadijnye sistemy, Moscow, Nauka Publ., 1989, 327 p. ISBN: 5-02-013984-X.
3. Gonzalez T., Sahni S. Open shop scheduling to minimize finish time. J. ACM, 1976, vol. 23, no. 4, pp. 665–679. doi: 10.1145/321978.321985
4. Bárány I., Fiala T. Nearly optimum solution of multimachine scheduling problems (in Hungarian). Szigma Math. Közgazdasági Folyóirat, 1982, vol. 15, pp. 177–191.
5. Jurisch B., Kubiak W. Two-machine open shops with renewable resources. Oper. Res., 1997, vol. 45, no. 4, pp. 544–552. doi: 10.1287/opre.45.4.544
6. Shabtay D., Kaspi M. Parallel machine scheduling with a convex resource consumption function. European J. Oper. Res., 2006, vol. 173, no. 1, pp. 92–107. doi: 10.1016/j.ejor.2004.12.008
7. Bampis E., Letsios D., Lucarelli G. A note on multiprocessor speed scaling with precedence constraints. In: Proc. 26th ACM Symposium on Parallelism in algorithms and architectures (SPAA’14), 2014, pp. 138–142. doi: 10.1145/2612669.2612672
8. Shabtay D., Kaspi M. Minimizing the makespan in open-shop scheduling problems with a convex resource consumption function. Naval Research Logistics, 2006, vol. 53, no. 3, pp. 204–216. doi: 10.1002/nav.20133
9. Adak Z., Arioglu Akan M. Ö., Bulkan S. Multiprocessor open shop problem: literature review and future directions. J. Comb. Optim., 2020, vol. 40, no. 1, pp. 547–569. doi: 10.1007/s10878-020-00591-3
10. Gerards M.E.T., Hurink J.L., Holzenspies P.K.F. A survey of offline algorithms for energy minimization under deadline constraints. J. Scheduling, 2016, vol. 19, pp. 3–19. doi: 10.1007/s10951-015-0463-8
11. Li D., Wu J. Energy-aware scheduling on multiprocessor platforms. Ser.: Springer Science and Business Media, NY, Springer, 2012, 59 p. doi: 10.1007/978-1-4614-5224-9
12. Kononov A., Kovalenko Y. Approximation algorithms for energy-efficient scheduling of parallel jobs. J. Scheduling, 2020, vol. 23, no. 6, pp. 693–709. doi: 10.1007/s10951-020-00653-8
13. Kononov A., Zakharova Y. Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion. J. Glob. Optim., 2022, vol. 83, pp. 539–564. doi: 10.1007/s10898-021-01115-x
14. Kononov A., Zakharova Y. Speed scaling scheduling of multiprocessor jobs with energy constraint and total completion time criterion. Inter. J. Artif. Intel., 2023, vol. 21, no. 2, pp. 109–129.
15. Li K. Energy efficient scheduling of parallel tasks on multiprocessor computers. J. Supercomput., 2020, vol. 60, pp. 223–247. doi: 10.1007/s11227-010-0416-0
16. Zakharova Yu., Sakhno M. Complexity and heuristic algorithms for speed scaling scheduling of parallel jobs with energy constraint. J. Comput. Appl. Math., 2024, art. 116254. Published online: September 16, 2024. doi: 10.1016/j.cam.2024.116254
17. Kong F., Guan N., Deng Q., Yi W. Energy-efficient scheduling for parallel real-time tasks based on level-packing. In: Proc. 2011 ACM Symposium on Applied Computing (SAC’11), 2011, pp. 635–640. doi: 10.1145/1982185.1982326
18. Gao M., He K., Li L., Wang Q., Liu C. A review on energy consumption, energy efficiency and energy saving of metal forming processes from different hierarchies. Processes, 2019, vol. 7, no. 6, pp. 357–381. doi: 10.3390/pr7060357
19. Mouzon G., Yildirim M.B., Twomey J. Operational methods for minimization of energy consumption of manufacturing equipment. Inter. J. Prod. Res., 2007, vol. 45, no. 18-–19, pp. 4247–4271. doi: 10.1080/00207540701450013
20. Mansouri S.A., Aktas E., Besikci U. Green scheduling of a two-machine flow-shop: trade-off between makespan and energy consumption. European J. Oper. Res., 2016, vol. 248, no. 3, pp. 772–788. doi: 10.1016/j.ejor.2015.08.064
21. He L.J., Cao Y.L., Li W.F., Cao J.J., Zhong L.C. Optimization of energy-efficient open shop scheduling with an adaptive multi-objective differential evolution algorithm. Appl. Soft Comput., 2022, vol. 118, art. 108459. doi: 10.1016/j.asoc.2022.108459
22. Salido M.A., Escamilla J., Giret A., Barber F. A genetic algorithm for energy-efficiency in job-shop scheduling. The Inter. J. Adv. Manufact. Techn., 2016, vol. 85, pp. 1303–1314. doi: 10.1007/s00170-015-7987-0
23. Stewart R., Raith A., Sinnen O. Optimising makespan and energy consumption in task scheduling for parallel systems. Comp. Oper. Res., 2023, vol. 154, art. 106212. doi: 10.1016/j.cor.2023.106212
24. Sathya Sofia A., GaneshKumar P. Multi-objective task scheduling to minimize energy consumption and makespan of cloud computing using NSGA-II. J. Netw. Syst. Manage., 2018, vol. 26, pp. 463–485. doi: 10.1007/s10922-017-9425-0
25. Kononov A., Kovalenko Y. On speed scaling scheduling of parallel jobs with preemption. In: Proc. Inter. Conf. “Discrete optimization and operations research” (DOOR’ 2016). Lecture notes in computer science. Cham, Springer, 2016, vol. 9869, pp. 309–321. doi: 10.1007/978-3-319-44914-2_25
26. Garey M.R., Johnson D.S. Computers and intractability: a guide to the theory of NP-completeness. San Francisco, CA, W.H.Freeman and co., 1979, 338 p. ISBN: 0-7167-1045-5. Translated to Russian under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Moscow, Mir Publ., 1982, 416 p.
27. Nesterov Yu. Lectures on convex optimization. Cham, Springer, 2018, vol. 137, 603 p. doi: 10.1007/978-3-319-91578-4
28. Boyd S., Vandenberghe L. Convex optimization. UK, Cambridge; NY, Cambridge Univ. Press, 2004, 716 p.
29. Shmoys D.B., Stein C., Wein J. Improved approximation algorithms for shop scheduling problems. SIAM J. Comp., 1994, vol. 23, no. 3, pp. 617–632. doi: 10.1137/S009753979222676X
30. Dempster A.H., Lenstra J.K., Rinnooy Kan A.H.G. Deterministic and stochastic scheduling. In: Proc. of the NATO Advanced Study Institute Series, Dordrecht, Springer, 1982, vol. 84, pp. 181–196. doi: 10.1007/978-94-009-7801-0_9
31. de Werra D. Graph-theoretical models for preemptive scheduling. In book: Advances in project scheduling. Amsterdam, Elsevier, 1989, pp. 171–185. doi: 10.1016/B978-0-444-87358-3.50012-2
32. Soper A.J. A cyclical search for the two machine flow shop and open shop to minimise finishing time. J. Sched., vol. 18, no. 3, pp. 311–314. doi: 10.1007/s10951-013-0356-7
33. Khramova A.P., Chernykh I. A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing. J. Sched., 2021, vol. 24, no. 4, pp. 405–412. doi: 10.1007/s10951-021-00694-7
34. Kunz K.S. Numerical analysis. NY, McGraw-Hill, 1957, 381 p.
35. Grötschel M., Lovász L., Schrijver A. Geometric algorithms and combinatorial optimizations. Ser.: Algorithms and combinatorics (AC, vol. 2). Berlin, Heidelberg, Springer, 1993, 362 p. doi: 10.1007/978-3-642-78240-4
36. Edmonds J. Maximum matching and a polyhedron with O,l-vertices. J. Res. Nat. Bur. Stand., 1965, vol. 698, no. 1–2, pp. 125–130. doi: 10.6028/JRES.069B.013
Cite this article as: Yu.V. Zakharova. Approximation algorithms for Open Shop variations subject to energy consumption. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2024, vol. 30, no. 4, pp. 117–133.
