Ю.В. Захарова. Приближенные алгоритмы для вариантов задачи open shop с учетом расхода энергии ... С. 117-133

УДК 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]