Approximation algorithms for Open Shop variations subject to energy consumption

Yu. V. Zakharova

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 30 (2024) no. 4, pp. 117-133

Résumé

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.

Détail

Keywords: open shop, schedule, NP-hardness, algorithm.

Bibliographie

[1] Kubiak W., A book of open shop scheduling, Springer Internat. Publ., Cham, 2022, 290 pp. | DOI

[2] Tanaev V.S., Sotskov Yu.N., Strusevich V.A., Teoriya raspisanii: Mnogostadiinye sistemy, Nauka, M., 1989, 327 pp.

[3] Gonzalez T., Sahni S., “Open shop scheduling to minimize finish time”, J. ACM, 23:4 (1976), 665–679 | DOI | MR | Zbl

[4] Barany I., Fiala T., “Nearly optimum solution of multimachine scheduling problems”, Szigma Mathematika Kozgazdasagi Folyoirat, 15 (1982), 177–191 (in Hungarian) | MR | Zbl

[5] Jurisch B., Kubiak W., “Two-machine open shops with renewable resources”, Oper. Res., 45:4 (1997), 544–552 | DOI | Zbl

[6] Shabtay D., Kaspi M., “Parallel machine scheduling with a convex resource consumption function”, European J. Oper. Res., 173:1 (2006), 92–107 | DOI | MR | Zbl

[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, 138–142 | DOI

[8] Shabtay D., Kaspi M., “Minimizing the makespan in open-shop scheduling problems with a convex resource consumption function”, Naval Research Logistics, 53:3 (2006), 204–216 | DOI | MR | Zbl

[9] Adak Z., Arioglu Akan M.O., Bulkan S., “Multiprocessor open shop problem: literature review and future directions”, J. Comb. Optim., 40 (2020), 547–569 | DOI | MR

[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, 19 (2016), 3–19 | DOI | MR | Zbl

[11] Li D., Wu J., Energy-aware scheduling on multiprocessor platforms, Ser. Springer Science and Business Media, Springer, NY, 2012, 59 pp. | DOI

[12] Kononov A., Kovalenko Y., “Approximation algorithms for energy-efficient scheduling of parallel jobs”, J. Scheduling, 23:6 (2020), 693–709 | DOI | MR | Zbl

[13] Kononov A., Zakharova Y., “Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion”, J. Glob. Optim., 83 (2022), 539–564 | DOI | MR | Zbl

[14] Kononov A., Zakharova Y., “Speed scaling scheduling of multiprocessor jobs with energy constraint and total completion time criterion”, Inter. J. Artif. Intel., 21:2 (2023), 109–129 | MR

[15] Li K., “Energy efficient scheduling of parallel tasks on multiprocessor computers”, J. Supercomput., 60 (2020), 223–247 | DOI

[16] Zakharova Yu., Sakhno M., “Complexity and heuristic algorithms for speed scaling scheduling of parallel jobs with energy constraint”, Opublikovana onlain: 6.10.2024, J. Comput. Appl. Math., 2024, 116254 | DOI | MR

[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, 635–640 | DOI

[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, 7:6 (2019), 357–381 | DOI

[19] Mouzon G., Yildirim M.B., Twomey J., “Operational methods for minimization of energy consumption of manufacturing equipment”, Inter. J. Prod. Res., 45:18–19 (2007), 4247–4271 | DOI | Zbl

[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., 248:3 (2016), 772–788 | DOI | MR | Zbl

[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., 118 (2022), 108459 | DOI

[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., 85 (2016), 1303–1314 | DOI

[23] Stewart R., Raith A., Sinnen O., “Optimising makespan and energy consumption in task scheduling for parallel systems”, Comp. Oper. Res., 154 (2023), 106212 | DOI | MR | Zbl

[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, 26 (2018), 463–485 | DOI

[25] Kononov A., Kovalenko Y., “On speed scaling scheduling of parallel jobs with preemption”, Proc. Internat. Conf. on Discrete Optimization and Operations Research, Ser. Lecture Notes in Computer Science, 9869, Springer, Cham, 2016, 309–321 | DOI | MR | Zbl

[26] Garey M., Johnson D., Computers and intractability. A Guide to the theory of NP-completeness, W.H. Freeman and Company, San Francisco, CA, 1979, 339 pp. | MR | Zbl

[27] Nesterov Y., Lectures on convex optimization, Springer, Cham, 2018, 603 pp. | DOI | MR | Zbl

[28] Boyd S., Vandenberghe L., Convex Optimization, Cambridge Univ. Press, Cambridge, 2009, 714 pp. | MR

[29] Shmoys D.B., Stein C., Wein J., “Improved approximation algorithms for shop scheduling problems”, SIAM J. Comp., 23:3 (1994), 617–632 | DOI | MR | Zbl

[30] “Deterministic and stochastic scheduling”, Proceedings of the NATO Advanced Study Institute Series, 84, eds. Dempster A.H., Lenstra J.K., Rinnooy Kan A.H.G., Springer, Dordrecht, 1982, 181–196 | DOI | MR

[31] de Werra D., “Graph-theoretical models for preemptive scheduling”, Advances in Project Scheduling, Elsevier, Amsterdam, 1989, 171–185 | DOI | MR

[32] Soper A.J., “A cyclical search for the two machine flow shop and open shop to minimise finishing time”, J. Sched., 18:3, 311–314 | DOI | MR | Zbl

[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., 24:4 (2021), 405–412 | DOI | MR | Zbl

[34] Kunz K.S., Numerical analysis, McGraw-Hill, NY, 1957, 381 pp. | MR | Zbl

[35] Grotschel M., Lovasz L., Schrijver A., Geometric algorithms and combinatorial optimizations, Springer, Berlin, 1993, 362 pp. | DOI | MR

[36] Edmonds J., “Maximum matching and a polyhedron with O,l-vertices”, J. Res. Not. Bur. Stondords, 698:1–2 (1965), 125–130 | DOI | MR