УДК 519.8
MSC: 90B35, 68M20, 90C59
DOI: 10.21538/0134-4889-2024-30-4-117-133
Исследование выполнено за счет гранта Российского научного фонда № 22-71-10015, https://rscf.ru/ project/22-71-10015/.
Рассматривается задача open shop с учетом расхода энергии. Исследуется вычислительная сложность и предлагаются подходы к решению для различных ее вариантов. Алгоритмы используют двухэтапную схему построения расписаний, где на первом этапе строятся оценки целевой функции и длительностей работ, а затем осуществляется переход от задачи с вариативными скоростями к задаче с фиксированными скоростями и используются методы списочного типа. В результате доказывается NP-трудность в общем случае и предлагаются полиномиальные точные и приближенные алгоритмы для практически значимых частных случаев, когда допускаются или нет прерывания, когда набор скоростей дискретен или непрерывен, когда потребление энергии ограничивается или оптимизируется. Строится модель частично целочисленного выпуклого программирования на основе непрерывного представления времени с использованием точек событий.
Ключевые слова: open shop, расписание, NP-трудность, алгоритм
СПИСОК ЛИТЕРАТУРЫ
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. Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний: Многостадийные системы. М.: Наука, 1989. 327 c.
3. Gonzalez T., Sahni S. Open shop scheduling to minimize finish time // J. ACM. 1976. Vol. 23, no. 4. P. 665–679. doi: 10.1145/321978.321985
4. Barany I., Fiala T. Nearly optimum solution of multimachine scheduling problems (in Hungarian) // Szigma Mathematika Kozgazdasagi Folyoirat. 1982. Vol. 15. P. 177–191.
5. Jurisch B., Kubiak W. Two-machine open shops with renewable resources // Oper. Res. 1997. Vol. 45, no. 4. P. 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. P. 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 // SPAA ’14: Proc. 26th ACM Symposium on Parallelism in algorithms and architectures. 2014. P. 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. С. 204–216. doi: 10.1002/nav.20133
9. Adak Z., Arioglu Akan M.O., Bulkan S. Multiprocessor open shop problem: literature review and future directions // J. Comb. Optim. 2020. Vol. 40. P. 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. P. 3–19. doi: 10.1007/s10951-015-0463-8
11. Li D., Wu J. Energy-aware scheduling on multiprocessor platforms. NY: Springer, 2012. 59 p. (Ser. Springer Science and Business Media). 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. P. 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. P. 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. P. 109–129.
15. Li K. Energy efficient scheduling of parallel tasks on multiprocessor computers // J. Supercomput. 2020. Vol. 60. P. 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. Опубликована онлайн: 6.10.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 // Proc. 2011 ACM Symposium on Applied Computing. 2011. P. 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. P. 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. P. 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, № 3. P. 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. P. 1303–1314. doi: 10.1007/s00170-015-7987
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. P. 463–485. doi:10.1007/s10922-017-9425-0
25. Kononov A., Kovalenko Y. On speed scaling scheduling of parallel jobs with preemption // Proc. Internat. Conf. on Discrete Optimization and Operations Research. Cham: Springer, 2016. Vol. 9869. P. 309–321. (Ser. Lecture Notes in Computer Science). doi: 10.1007/978-3-319-44914-2_25
26. Garey M., Johnson D. Computers and intractability. A Guide to the theory of NP-completeness. San Francisco, CA: W.H. Freeman and Company, 1979. 339 p.
27. Nesterov Y. Lectures on convex optimization. Cham: Springer, 2018. 603 p. doi: 10.1007/978-3-319-91578-4
28. Boyd S., Vandenberghe L. Convex Optimization. Cambridge: Cambridge Univ. Press, 2009. 714 p.
29. Shmoys D.B., Stein C., Wein J. Improved approximation algorithms for shop scheduling problems // SIAM J. Comp. 1994. Vol. 23, no. 3. P. 617–632. doi: 10.1137/S009753979222676X
30. Dempster A.H., Lenstra J.K., Rinnooy Kan A.H.G. Deterministic and stochastic scheduling // Proceedings of the NATO Advanced Study Institute Series. Dordrecht: Springer. 1982. Vol. 84. P. 181–96. doi: 10.1007/978-94-009-7801-0_9
31. de Werra D. Graph-theoretical models for preemptive scheduling // Advances in Project Scheduling. Amsterdam: Elsevier, 1989. P. 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. P. 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. P. 405–412. doi: 10.1007/s10951-021-00694-7
34. Kunz K.S. Numerical analysis. NY: McGraw-Hill, 1957. 381 p.
35. Grotschel M., Lovasz L., Schrijver A. Geometric algorithms and combinatorial optimizations. Berlin: 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. Not. Bur. Stondords. 1965. Vol. 698, no. 1–2. P. 125–130. doi: 10.6028/JRES.069B.013
Поступила 6.10.2024
После доработки 20.10.2024
Принята к публикации 28.10.2024
Захарова Юлия Викторовна
канд. физ.-мат. наук
старший науч. сотрудник
Институт математики им. С.Л. Соболева СО РАН, Омский филиал;
Омский государственный университет им. Ф.М. Достоевского
г. Омск
e-mail: yzakharova@ofim.oscsbras.ru
Ссылка на статью: Ю.В. Захарова. Приближенные алгоритмы для вариантов задачи open shop с учетом расхода энергии // Тр. Ин-та математики и механики УрО РАН. 2024. Т. 30, № 4. С. 117-133
English
Yu.V. Zakharova. Approximation algorithms for Open Shop variations subject to energy consumption
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 the 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
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.
[References -> on the "English" button bottom right]