Задача теории расписаний

Общая задача теории расписаний. В отечественной литературе эту задачу обычно называют задачей календарного планирования. Общую ее схему можно описать следующим образом. Имеется m станков и n деталей, каждая из которых должна пройти обработку на всех станках в определенном порядке. Этот порядок может быть одинаковым для всех деталей либо различным для разных их групп. При этом производственные операции считаются неделимыми (начав обработку детали на станке , мы должны довести эту обработку до конца, не имея права прервать ее).

Задана матрица , где — время, необходимое для обработки -й детали на -м станке для тех деталей , которые не требуют обработки на станке ). Требуется указать такой порядок запуска деталей в обработку, который минимизировал бы общее время выполнения всех работ (длину производственного цикла).

Непосредственному решению (путем перебора всех вариантов) эта задача не поддается, так как при этом уже в простейшем случае одинакового порядка прохождения деталей пришлось бы выбирать наименьшую из величин. При больших это практически неосуществимо даже с использованием быстродействующих электронных машин. Несмотря на огромное прикладное значение этой задачи (описанная модель или ее варианты являются схемами основной массы задач по организации производства), пока удалось получить ее решение только для случая двух машин (алгоритм Джонсона, лекция №17) . Вместе с тем случай до сих пор доставлял весьма серьезные теоретические и вычислительные затруднения. Постановка задач этого класса в виде целочисленных задач линейного программирования является одним из перспективных путей продвижения в этом направлении.

Известно несколько формулировок задачи теории расписаний в виде целочисленных задач линейного программирования. Опишем одну из возможных постановок для которой является идея А. С. Мэн (Мэн А.С. Задача календарного планирования для предприятий единичного и мелкосерийного производства. Сб. "Календарное планирование", М., "Прогресс", 1966, гл.12.).