Geodesic
Minimizing total completion time on parallel machines with unit length jobs that need one additional resource
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 601-612

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

The paper considers a scheduling problem on parallel identical machines to minimize the sum of the completion times. All jobs are of unit length and require one unit of one of the additional resources. We offer an algorithm that is much faster and simpler than previously available.
Keywords: resource constrained scheduling, unit length jobs, total completion time, parallel identical machines. 
V. A. Strusevich. Minimizing total completion time on parallel machines with unit length jobs that need one additional resource. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 601-612. http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a30/
@article{SEMR_2022_19_2_a30,
     author = {V. A. Strusevich},
     title = {Minimizing total completion time on parallel machines with unit length jobs that need one additional resource},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {601--612},
     year = {2022},
     volume = {19},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a30/}
}
TY  - JOUR
AU  - V. A. Strusevich
TI  - Minimizing total completion time on parallel machines with unit length jobs that need one additional resource
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2022
SP  - 601
EP  - 612
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a30/
LA  - en
ID  - SEMR_2022_19_2_a30
ER  - 
%0 Journal Article
%A V. A. Strusevich
%T Minimizing total completion time on parallel machines with unit length jobs that need one additional resource
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2022
%P 601-612
%V 19
%N 2
%U http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a30/
%G en
%F SEMR_2022_19_2_a30

[1] J. Błažewicz, N. Brauner, G. Finke, “Scheduling with discrete resource constraints”, Handbook of scheduling. Algorithms, models, and performance analysis, ed. Leung, J.Y.-T., Chapman Hall/CRC, Boca Raton, 2004, 23-1–23-18 | MR

[2] J. Błažewicz, J.K. Lenstra, A.H.G. Rinnooy Kan, “Scheduling subject to resource constraints: classification and complexity”, Discr. Appl. Math., 5 (1983), 11–24 | DOI | MR | Zbl

[3] J. Błažewicz, K.H. Ecker, E. Pesch, G. Schmidt, M. Sterna, J. Weglarz, “Scheduling under resource constraints”, Handbook of Scheduling, eds. J. Błažewicz et al., Springer, Cambridge, 2019, 475–525 | MR

[4] R.W. Conway, W.L. Maxwell, L.W. Miller, Theory of scheduling, Addison-Wesley, Reading, 1967 | MR | Zbl

[5] E.B. Edis, C. Oguz, I. Ozkarahan, “Parallel machine scheduling with additional resources: notation, classification, models and solution methods”, Eur. J. Oper. Res., 230:3 (2013), 449–463 | DOI | MR | Zbl

[6] E. Hebrard, M.-J. Hugueta, N. Jozefowiez, A. Maillard, C. Pralet, G. Verfaillie, “Approximation of the parallel machine scheduling problem with additional unit resources”, Discr. Appl. Math., 215 (2016), 126–135 | DOI | MR | Zbl

[7] T. Janssen, C. Swennenhuis, A. Bitar, T. Bosman, D. Gijswijt, L. van Iersel, S. Dausère-Pérèz, C. Yugma, Parallel machine scheduling with a single resource per job, 2018, arXiv: 1809.05009v3

[8] H. Kellerer, V.A. Strusevich, “Scheduling problems for parallel dedicated machines under multiple resource constraints”, Discr. Appl. Math., 133:1-3 (2003), 45–68 | DOI | MR | Zbl

[9] A.W. Marshall, I. Olkin, Inequalities: theory of majorization and its applications, Academic Press, New York etc, 1979 | MR | Zbl

[10] R. McNaughton, “Scheduling with deadlines and loss functions”, Manag. Sci., 6 (1959), 1–12 | DOI | MR | Zbl

[11] J.B. Orlin, “A faster strongly polynomial minimum cost flow algorithm”, Proc. 20th ACM Symp. Theory Comput., STOC'88, 1988, 377–387

[12] V.A. Strusevich, “Approximation algorithms for makespan minimization on parallel machines under resource constraints”, J. Oper. Res. Soc., 72:9 (2021), 2135–2146 | DOI