Geodesic
Application of idempotent algebra methods in~genetic algorithm for solving the scheduling problem
Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 112-124.

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

The resource-constrained project scheduling problem in monetary form is considered. The criterion for the optimal start schedule for each project activity is the maximum net present value, which fulfills the constraints on sufficiency of funds and takes into account the technological relationship between the activities. This problem is NP-hard in a strong sense. It is proved that the project schedule can be represented as a solution of a linear equation over an idempotent semiring. A sufficient condition has been established for the admissibility of the schedule in terms of the partial order of work and the duration of the project. It is proved that each of the project schedules can be represented as a product of a matrix of a special form, calculated on the basis of the partial order matrix of the project, and a vector from an idempotent semimodule. For the coordinates of the vector, upper and lower limits have been determined, taking into account the timing of the activity. A description of the genetic algorithm for solving the problem is given. The algorithm is based on the evolution of a population whose individuals represent solutions of an idempotent equation for a partial order matrix of the project. The computational experiments demonstrate the effectiveness of the algorithm.
Keywords: scheduling problem, investment project, NPV, idempotent mathematics, genetic algorithm. 
@article{PDM_2022_4_a10,
     author = {A. M. Bulavchuk and D. V. Semenova},
     title = {Application of idempotent algebra methods in~genetic algorithm for solving the scheduling problem},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {112--124},
     publisher = {mathdoc},
     number = {4},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2022_4_a10/}
}
TY  - JOUR
AU  - A. M. Bulavchuk
AU  - D. V. Semenova
TI  - Application of idempotent algebra methods in~genetic algorithm for solving the scheduling problem
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2022
SP  - 112
EP  - 124
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2022_4_a10/
LA  - ru
ID  - PDM_2022_4_a10
ER  - 
%0 Journal Article
%A A. M. Bulavchuk
%A D. V. Semenova
%T Application of idempotent algebra methods in~genetic algorithm for solving the scheduling problem
%J Prikladnaâ diskretnaâ matematika
%D 2022
%P 112-124
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2022_4_a10/
%G ru
%F PDM_2022_4_a10
A. M. Bulavchuk; D. V. Semenova. Application of idempotent algebra methods in~genetic algorithm for solving the scheduling problem. Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 112-124. http://geodesic.mathdoc.fr/item/PDM_2022_4_a10/

[1] Gimadi E. Kh. and Puzynina N. M., “Problem of the calendar planning of a large-scale design under the conditions of limited resources: experience in the construction of software”, Upravliaemie Systemy, 1983, no. 23, 24–32 (in Russian)

[2] Gimadi E. Kh., Zalyubovskii V. V., and Sevast'yanov S. V., “Polynomial solvability of scheduling problems with storable resources and directive deadlines”, Diskretn. Anal. Issled. Oper., Ser. 2, 7:1 (2000), 9–34 (in Russian) | MR

[3] Goncharov E. N. and Leonov V. V., “Genetic algorithm for the resource-constrained project scheduling problem”, Avtomatika i Telemekhanika, 2017, no. 6, 173–179 (in Russian)

[4] Goncharov E. N. and Mishin D. V., “Exact algorithm for the resource-constrained project scheduling problem”, Prikladnaya Matematika i Fundamental'naya Informatika, 4:1 (2017), 43–53 (in Russian)

[5] Hartmann S. and Briskorn D., “An updated survey of variants and extensions of the resource-constrained project scheduling problem”, Eur. J. Operat. Res., 2022, no. 1, 1–14 | DOI | MR

[6] Habibi F., Barzinpour F., and Sadjadi S., “Resource-constrained project scheduling problem: review of past and recent developments”, J. Project Management, 3:2 (2018), 55–88 | DOI

[7] Kazakovtseva E. A. and Servakh V. V., “Complexity of the project scheduling problem”, Diskretn. Analiz i Issled. Oper., 22:4 (2015), 35–49 (in Russian) | MR

[8] Servakh V. V. and Soukhikh S. L., “Hybrid algorithm for scheduling with regard for reinvestment of profits”, Avtomatika i Telemekhanika, 2004, no. 3, 100–107 (in Russian)

[9] Bulavchuk A. M. and Semenova D. V., “Genetic algorithm based on idempotent algebra methods for RCPSP”, IEEE 15th Intern. Conf. AICT, 2021, 1–4

[10] Litvinov G. L., Maslov V. P., and Sobolevsky A. N., “Idempotent mathematics and interval analysis”, Vychislitel'nye Tekhnologii, 6:6 (2001), 41–70 (in Russian) | MR

[11] Krivulin N. K., Methods of Idempotent Algebra in Problems of Complex Systems Modeling and Analysis, St. Petersburg University Press, St. Petersburg, 2009, 255 pp. (in Russian)

[12] Omelchenko A. V., Graph Theory, MCCME Publ., M., 2018, 416 pp. (in Russian)

[13] Kochetov Y. A. and Stolyar A. A., “New greedy euristics for the the resource constrained project scheduling problem”, Diskretn. Analiz i Issled. Oper., 12:1 (2005), 12–36 (in Russian) | MR

[14] Project scheduling problem library, , 2022 https://www.om-db.wi.tum.de/psplib/