MAIN STAGES OF THE EVOLUTION OF NUMERICAL METHOD FOR DETERMINING THE PARAMETERS OF A MULTI-STAGE STOCHASTIC SYSTEM
Authors: Олейникова С.А. , Селищев И.А. , Тюников Д.А. 
Published: October 2022

Объектом исследования является многостадийная система, отличительная особенность которой заключается в случайной длительности последовательно-параллельных работ, которая зависит не только от случайных факторов, но и от выбора исполнителя. Таким образом, необходимо одновременно решить две задачи: задачу о назначениях, заключающуюся в определении зависимости между работами и специалистами, и задачу планирования, позволяющую назначить оптимальное время начала каждой работе. Для каждого класса этих задач существуют свои методы, однако они неприменимы для случая, когда данные задачи необходимо решать одновременно. В связи с этим требуется разработка собственных методов, отличительной особенностью которых является возможность получения комплексного решения двух задач. Анализ возможных подходов к решению исследуемой задачи позволил остановиться на эволюционных алгоритмах для ее решения. В частности, экспериментальные исследования показали, что генетические алгоритмы являются достаточно эффективными для случаев, когда классические методы не применимы. Однако для получения близких к оптимальным решений необходимо разработать такие этапы, как скрещивание и мутация с учетом всех особенностей решаемой задачи. Именно этим вопросам будет посвящена данная работа. Научная новизна заключается в разработке подхода к скрещиванию, основанного на одноточечном кроссинговере и обеспечивающего возможность доопределения времени начала и окончания в хромосоме потомка с учетом графика занятости специалистов, а также мутации, позволяющей случайным образом менять гены исполнителя, начиная со случайно выбранной работы и доопределять гены начала и окончания работ. Практическая значимость заключается в возможности использования разработанных алгоритмов для любых многостадийных систем, требующих определения графика выполнения работ и закрепления за ними специалистов.

The object of research is a multi-stage system, the distinctive feature of which is the random duration of series-parallel work, which depends not only on random factors but also on the choice of the performer. Thus, it is necessary to solve two problems simultaneously: the assignment problem, which consists in determining the relationship between jobs and specialists, and the planning problem, which allows you to assign the optimal start time for each job. Each class of these tasks has its own methods, however, they are not applicable to the case when these tasks must be solved simultaneously. In this regard, we developed our own methods, a distinctive feature of which is the possibility of obtaining a comprehensive solution of two problems. An analysis of possible approaches to solving the problem under study made it possible to dwell on evolutionary algorithms for solving it. In particular, experimental studies have shown that genetic algorithms are quite efficient for cases where classical methods are not applicable. However, in order to obtain solutions, close to optimal, it is necessary to develop such stages as crossing and mutation, taking into account all the features of the problem being solved. It is these questions that this work will be devoted to. The scientific novelty lies in the development of an approach to crossing based on a single-point crossing over and providing the possibility of redefining the start and end times in the offspring chromosome, taking into account the employment schedule of specialists, as well as a mutation that allows you to randomly change the genes of the performer, starting from a randomly selected job and redefine the start genes and completion of work. The practical significance lies in the possibility of using the developed algorithms for any multi-stage systems that require the definition of a work schedule and the assignment of specialists to them