Математическая модель одного класса задач планирования работы независимых машин

Abstract

Рассмотрен один класс задач теории расписаний. Построена математическая модель задачи планирования работы разнотипных машин с периодами простоя. Сформулирована и доказана теорема о корректности приведения этой задачи к специальной задаче комбинаторной оптимизации. Разработан алгоритм нахождения нижней границы целевой функции возникающей задачи оптимизации.

Розглянуто один клас задач теорії розкладів. Побудована математична модель задачі планування роботи різнотипних машин з періодами простою. Сформульована і доведена теорема про коректність приведення цієї задачі до спеціальної задачі комбінаторної оптимізації. Розроблений алгоритм знаходження нижньої межі цільової функції задачі оптимізації, що виникає.

The paper deals with a class of scheduling problems. Mathematical model for the problem of scheduling on a set of unrelated machines with availability constraints is developed. Representation of this problem as a special combinatorial optimization problem is formulated and its correctness is proved. The algorithm for calculating lower bound of objective function of the problem under consideration is developed.