Оптимизация в задачах теории расписаний с квадратичным критерием

Abstract

RU: Цель. В работе рассматриваются квадратичные оптимизационные модели для задач теории расписаний, возникающих при исследовании конвейерной системы машин (flow shop) со стандартными ограничениями. Полученные квадратичные модели является многоэкстремальными. Целью исследования является разработка эффективных методов построения оптимальных расписаний с использованием квадратичной регуляризации. Методика. Путем квадратичной регуляризации ограничения задачи конвейерной системы машин сводятся к максимизации евклидовой нормы вектора на выпуклом множестве. Использован метод точной квадратичной регуляризации, который позволяет находить глобальные решения в многоэкстремальных задачах. Результаты. Показано, что любая задача теории расписаний для конвейерной системы машин сводится к задаче максимума квадратичной функции с набором линейных и квадратичных ограничений Применен метод точной квадратичной регуляризации с линейным сдвигом координат для поиска глобального экстремума. Разработан алгоритм решения этого класса задач. Научная новизна. Проведенное преобразование задачи конвейерной системы машин позволяет решать все задачи такого типа методами выпуклой оптимизации и дихотомии, и не требует разрабатывать алгоритмы для отдельных классов задач теории расписаний. Показано, что с помощью линейного сдвига системы координат многоэкстремальная задача оптимизации может быть сведена к одноэкстремальной. Практическая значимость. Разработанная методика решения задач теории расписаний для конвейерной системы машин позволит получать оптимальные расписания выполнения задач. Это позволит минимизировать время выполнения операций в технологических процессах.

UK: Мета. У роботі розглядаються квадратичні оптимізаційні моделі для задач теорії розкладів, що виникають при дослідженні конвеєрної системи машин (flow shop) зі стандартними обмеженнями. Отримані квадратичні моделі є багатоекстремальними. Метою дослідження є розробка ефективних методів побудови оптимальних розкладів з використанням квадратичної регулярізації. Методика. Шляхом квадратичної регулярізації обмеження задачі конвеєрної системи машин зводяться до максимізації евклідової норми вектору на опуклій множині. Використано метод точної квадратичної регуляризації, який дозволяє знаходити глобальні розв’язки в багатоекстремальних задачах. Результати. Показано, що будь-яка задача теорії розкладів для конвеєрної системи машин зводиться до задачі максимуму квадратичної функції з набором лінійних і квадратичних обмежень. Застосовано метод точної квадратичної регуляризації з лінійним зсувом координат для пошуку глобального екстремуму. Розроблено алгоритм розв’язання цього класу задач. Наукова новизна. Проведене перетворення задачі конвеєрної системи машин дозволяє розв’язувати усі задачі цього класу за допомогою методів опуклої оптимізації та дихотомії, і не потребує розробляти алгоритми для окремих класів задач теорії розкладів. Показано, що за допомогою лінійного зрушення системи координат багатоекстремальна задача оптимізації може бути зведена до одно екстремальної. Практична значимість. Розроблена методика розв’язання задач теорії розкладів для конвеєрної системи машин дозволяє отримати оптимальні розклади виконання завдань. Це дозволить мінімізувати час виконання операцій у технологічних процесах.

EN: Goal. The paper considers quadratic optimization models for the problems of scheduling theory that arise in the study of conveyor machines system (flow shop) with standard constraints. The obtained quadratic models are multiextremal. The aim of the study is to develop effective methods for constructing optimal schedules using quadratic regularization. Methodology. Using quadratic regularization, the constraints of the problem of conveyor machines system are reduced to maximization of Euclidian vector norm at the convex set. We used the method of exact quadratic regularization, which allows us to find global solutions in multiextremal problems. Results. It is shown that any problem of scheduling theory for the conveyor machines system can be reduces to the problem of maximizing a quadratic function with a set of linear and quadratic constraints. A method of exact quadratic regularization with a linear coordinate shift was used to find the global extremum. An algorithm for solving this class of problems was developed. Scientific novelty. Conducted transformation of the problem of conveyor machines system allows solving all problems of this type by methods of convex optimization and dichotomy, rather than developing algorithms for separate classes of scheduling theory problems. It is shown that the system the multiextremal convex optimization problem can be reduced to a one-extremal one using a linear coordinate shift. Practical significance. The developed methodology for solving the problems of scheduling theory for conveyor machines system allow obtaining optimal schedules for processing of the tasks. This technique allows to minimize processing time of operations in technological processes.