ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 12. Vol. 27. 2021

DOI: 10.17587/it.27.642-650

Yu. A. Mezentsev, Dr. of Tech. Sc., Professor, e-mail: mesyan@yandex.ru, Yu. L. Korotkova, Postgraduate Student, e-mail: juliapetrunina@yandex.ru, I. V. Estraich, Senior Lecturer, e-mail: ive7@yandex.ru, Novosibirsk State Technical University, Novosibirsk, Russian Federation

An Efficient Algorithm for Solving the Applied Problem Scheduling Optimization of a Parallel-Sequential System

The problem of optimal regulation of airline fleet schedules by reassigning aircraft to flights is considered. The optimal regulation of schedules is to create or change them in such a way that minimizes system losses due to current violations. As an estimate of losses, the total deviation of the adjusted schedule from the spetified departure schedules of aircraft is used. It is shown that the described technological system belongs to the category of parallel-sequential systems. Accordingly, the considered system control problem is NP-hard and does not have effective algorithms for exact solution. A brief overview of approaches to solving its modifications and related fleet management tasks is given. The original formal formulation is given, the decomposition of the problem is justified, and an algorithm for its approximate solution is presented. An illustrative example is given and comparative statistics of testing software implementations of the decomposition algorithm of the schedule control problem on real data are reflected, proving the actual effectiveness of the developed tools.
Keywords: optimal schedule control, minimum deviation criterion, decomposition, heuristic algorithm, step-by-step schedule formation

P. 642–650

To the contents