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/