Geodesic
Constructive algorithms for the scheduling problem on~two processors with the maximum time offset criterion taking into account parallelization and energy consumption
Prikladnaâ diskretnaâ matematika, no. 1 (2025), pp. 118-128.

Voir la notice de l'article provenant de la source Math-Net.Ru

We provide theoretical and experimental analysis of the computational complexity of one scheduling problem arising in computer systems and applications. The feature of the statement is the parallelization of operations and resource-dependent durations of operations. Here the processor speed affects the duration of operations and power consumption. For each operation the number of required processors is given. The criterion is the minimization of the maximum lateness under the given energy budget. We prove that the problem is NP-hard using the polynomial reduction from the well-known 3-Partition problem and constructing non-idle instances. An approximate algorithm with polynomial running time is proposed. The algorithm consists of reducing the two-processor problem to the single-processor one. A convex program is proposed for solving the single-processor problem. We investigate the block properties of the solutions generated by the algorithm and show that their objective value is at most doubled optimum maximum lateness plus the maximal due date. The experimental results show the applicability of the proposed algorithm. We construct a series of instances in which the relative deviation from the lower bound is less than 15 %. We also experimentally identify a tendency in decreasing the relative deviation when the number of fully parallelizable operations increases. The theoretical analysis guarantees that the problem is polynomially solvable when all operations are fully parallelizable.
Keywords: schedule, resource, algorithm, NP-hardness. 
@article{PDM_2025_1_a7,
     author = {Y. V. Zakharova and A. O. Evtina},
     title = {Constructive algorithms for the scheduling problem on~two processors with the maximum time offset criterion taking into account parallelization and energy consumption},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {118--128},
     publisher = {mathdoc},
     number = {1},
     year = {2025},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2025_1_a7/}
}
TY  - JOUR
AU  - Y. V. Zakharova
AU  - A. O. Evtina
TI  - Constructive algorithms for the scheduling problem on~two processors with the maximum time offset criterion taking into account parallelization and energy consumption
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2025
SP  - 118
EP  - 128
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2025_1_a7/
LA  - ru
ID  - PDM_2025_1_a7
ER  - 
%0 Journal Article
%A Y. V. Zakharova
%A A. O. Evtina
%T Constructive algorithms for the scheduling problem on~two processors with the maximum time offset criterion taking into account parallelization and energy consumption
%J Prikladnaâ diskretnaâ matematika
%D 2025
%P 118-128
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2025_1_a7/
%G ru
%F PDM_2025_1_a7
Y. V. Zakharova; A. O. Evtina. Constructive algorithms for the scheduling problem on~two processors with the maximum time offset criterion taking into account parallelization and energy consumption. Prikladnaâ diskretnaâ matematika, no. 1 (2025), pp. 118-128. http://geodesic.mathdoc.fr/item/PDM_2025_1_a7/

[1] Drozdowski M., Scheduling for Parallel Processing, Springer, Dordrecht, 2009, 386 pp. | MR

[2] Servakh V. V., “An efficiently solvable case of the scheduling problem with renewable resources”, Diskretn. Analiz i Issled. Oper., ser. 2, 7:1 (2000), 75–82 (in Russian) | MR

[3] Kovalenko Yu. V., “On the calendar planning problem with renewable resource”, Autom. Remote Control, 73:6 (2012), 1046–1055 | DOI | MR

[4] Goncharov E. N., “An improved genetic algorithm for the resource-constrained project scheduling problem”, Advances in Optimization and Applications, eds. N. Olenev, Yu. Evtushenko, M. Jaćimović, et al., Springer, Cham, 2022, 35–47 | DOI | MR

[5] Zhuravlev S., Blagodurov S., and Fedorova A., “Addressing shared resource contention in multicore processors via scheduling”, Comput. Archit. News, 38:1 (2010), 129–142 | DOI

[6] Eremeev A. V. and Sakhno M. Yu., “Multi-core processor scheduling with respect to the mutual influence of jobs”, Vych. Met. Programmirovanie, 24:1 (2023), 115–126 (in Russian)

[7] Kononov A. and Kovalenko Y., “On speed scaling scheduling of parallel jobs with preemption”, LNCS, 9869, 2016, 309–321 | MR

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

[9] Gerards M. E. T., Hurink J. L., and Holzenspies P. K. F., “A survey of offline algorithms for energy minimization under deadline constraints”, J. Scheduling, 19 (2016), 3–19 | DOI | MR

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

[11] Complexity Results for Scheduling Problems, , 2024 https://www2.informatik.uni-osnabrueck.de/knust/class/

[12] Lee C.-Y. and Cai X., “Scheduling one and two-processor tasks on two parallel processors”, IIE Trans., 31 (1999), 445–455

[13] Lenstra J. K., Rinnooy Kan A. H. G., and Brucker P., “Complexity of machine scheduling problems”, Ann. Discrete Math., 1 (1977), 343–362 | DOI | MR

[14] Grotschel M., Lovasz L., and Schrijver A., Geometric Algorithms and Combinatorial Optimizations, Springer, Heidelberg, 2009, 332 pp. | MR

[15] Garey M. and Johnson D., Computers and Intractability. A Guide to the Theory of NP-completeness, W. H. Freeman and Company, N.Y., 1979, 338 pp. | MR