Geodesic
The problem of one machine with equal processing time and preemption
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 3, pp. 105-122 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider the problem of minimizing the weighted average execution time of equal-length jobs performance on one machine at the specified time of job arrival and the possibility of their interruption. The computational complexity of this problem is currently unknown. The article proposes an algorithm for preprocessing input data that allows reducing the problem to a narrower and more regular class of examples. The properties of optimal solutions are substantiated. Based on them, an algorithm for constructing a finite subset of solutions containing an optimal schedule has been developed. A parametric analysis of the schedules in this subset has been carried out that makes it possible to form a subclass of schedules that are optimal at some values of weights. A polynomially solvable case of the problem is isolated. Tab. 1, illustr. 10, bibliogr. 16.
Keywords: schedule theory, one machine, preemption. 
@article{DA_2024_31_3_a4,
     author = {K. A. Lyashkova and V. V. Servakh},
     title = {The problem of~one machine with equal processing time and preemption},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {105--122},
     year = {2024},
     volume = {31},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_3_a4/}
}
TY  - JOUR
AU  - K. A. Lyashkova
AU  - V. V. Servakh
TI  - The problem of one machine with equal processing time and preemption
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 105
EP  - 122
VL  - 31
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_3_a4/
LA  - ru
ID  - DA_2024_31_3_a4
ER  - 
%0 Journal Article
%A K. A. Lyashkova
%A V. V. Servakh
%T The problem of one machine with equal processing time and preemption
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 105-122
%V 31
%N 3
%U http://geodesic.mathdoc.fr/item/DA_2024_31_3_a4/
%G ru
%F DA_2024_31_3_a4
K. A. Lyashkova; V. V. Servakh. The problem of one machine with equal processing time and preemption. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 3, pp. 105-122. http://geodesic.mathdoc.fr/item/DA_2024_31_3_a4/

[1] M. L. Pinedo, Scheduling: Theory, algorithms, systems, Springer, New York, 2008, 678 pp. | DOI

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

[3] P. Baptiste, “Scheduling equal-length jobs on identical parallel machines”, Discrete Appl. Math., 103:1-3 (2000), 21–32 | DOI

[4] J. Labetoulle, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, “Preemptive scheduling of uniform machines subject to release dates”, Progress in combinatorial optimization, Acad. Press, Toronto, 1984, 245–261 | DOI

[5] K. R. Baker, Introduction to sequencing and scheduling, John Wiley Sons, New York, 1974, 318 pp.

[6] P. Baptiste, J. Carlier, A. V. Kononov, M. Queyranne, S. V. Sevast'yanov, and M. I. Sviridenko, “Structural properties of optimal schedules with preemption”, J. Appl. Ind. Math., 4:4 (2010), 455–474 | DOI

[7] M. Batsyn, B. Goldengorin, P. M. Pardalos, P. Sukhov, “Onlineheuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time”, Optim. Methods Softw., 29 (2014), 955–963 | DOI

[8] M. Batsyn, B. Goldengorin, P. Sukhov, P. M. Pardalos, “Lower and up per bounds for the preemptive single machine scheduling problem with equal processing times”, Proc. Models, algorithms, and technologies for network analysis, 2nd Int. Conf. Network Analysis (Nizhny Novgorod, Russia, May 7-9, 2012), Springer Proc. Math. Stat., 59, Springer, New York, 2013, 11–27 | DOI

[9] M. X. Goemans, M. Queyranne, A. S. Schulz, M. Skutella, Y. Wang, “Single machine scheduling with release dates”, SIAM J. Discrete Math., 15:2 (2002), 165–192 | DOI

[10] S. A. Kravchenko, F. Werner, “Scheduling jobs with equal processing times”, IFAC Proc. Volumes, 42:4 (2009), 1262–1267 | DOI

[11] A. Fomin, B. Goldengorin, An efficient model for the preemptive single machine scheduling of equal-length jobs, Cornell Univ., Ithaca, NY, 2020, arXiv: 2012.08152 | DOI

[12] K. A. Chernykh, V. V. Servakh, “The structure of the optimal solution of the problem of one machine with the possibility of interruptions of jobs”, Proc. 14th Int. Asian School-Seminar «Optimization Problems of Complex Systems» (Kara-Oi, Kyrgyzstan, July 20-31, 2018), IEEE, Piscataway, 2018, 312–321

[13] K. A. Chernykh, V. V. Servakh, “Combinatorial structure of optimal solutions to the problem of a single machine with preemption”, Proc. 15th Int. Asian School-Seminar «Optimization Problems of Complex Systems» (Novosibirsk, Russia, Aug. 26-30, 2019), IEEE, Piscataway, 2019, 21–26 | DOI

[14] K. A. Chernykh, V. V. Servakh, “Analysis of optimal solutions to the problem of a single machine with preemption”, Mathematical optimization theory and operations research, Recent trends. Rev. Sel. Pap. 20th Int. Conf. (Irkutsk, Russia, July 5-10, 2021), Commun. Comput. Inf. Sci., 1476, Springer, Cham, 2021, 163–174 | DOI

[15] F. Jaramillo, M. Erkoc, “Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling”, Comput. Ind. Eng, 107 (2017), 109–119 | DOI

[16] F. Jaramillo, B. Keles, M. Erkoc, “Modeling single machine preemptive scheduling problems for computational efficiency”, Ann. Oper. Res, 285 (2020), 197–222 | DOI