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

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

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

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

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

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

Не умаляя общности, можно считать целыми числами. Составление графика обработки деталей будем связывать с "календарем", "дни" которого занумерованы целыми числами , где настолько велико, чтобы заведомо обеспечить возможность обработки всей партии.

Введем неотрицательные целочисленные переменные , принимающие значения . Здесь указывает "дату" начала обработки -м станком -й детали. Рассмотрим условия, которым должны удовлетворять .

1. Прежде всего нужно наложить ограничение, не допускающее одновременной обработки на одном станке двух деталей. Для этого моменты начала обработки любых двух деталей должны отстоять по "календарю" не менее чем на длительность обработки той из них, которая запускается первой, то есть

   (7.25)

2. В обычную задачу линейного программирования альтернативное условие типа (7.25.) ввести нельзя. Определим целочисленные переменные , принимающие значения 0 или 1. Тогда (7.25.) можно переписать в виде

(7.26)

(7.27)

3. Отметим очевидное неравенство , вытекающее из определения . Ясно, что случай невозможен, то есть обработка двух разных деталей не может начаться на одном станке одновременно, ибо в этом случае неравенства (7.26.) удовлетворялись бы только при , а неравенства (7.27.) – только при . Если , то в (7.26.) может быть равен нулю или единице, а в (7.27 ) – только нулю, так что единственным возможным значением здесь будет . Если же , то в (7.26.) может быть равен только единице, а в (7.27.) и нулю и единице, так что в этом случае возможно лишь .

4. Отсюда ясно, что , если на -м станке обработка -й детали предшествует обработке -й детали, и в противном случае.

5. Теперь следует отразить условия на заданный технологический порядок прохождения деталями обработки на станках. В данной формулировке в принципе безразлично, является ли этот порядок одинаковым для всех деталей или нет. Именно, если деталь должна быть обработана сначала на станке , затем на станке , то мы должны иметь

   (7.28)

6. Отсюда ясно, что случай , то есть одновременное начало обработки одной детали на двух станках, возможен лишь при , то есть тогда, когда данная деталь на одном из этих станков вообще не должна обрабатываться.

7. Для некоторых деталей условие упорядочения может налагаться лишь в следующей ослабленной форме: деталь должна пройти обработку на станках и , в любом порядке, затем на станке . Тогда условие (7.29.) заменится следующими двумя условиями:

   (7.29)

8. Можно дать еще вариант условий этого типа, считая что деталь между обработкой на станках и должна пролежать время (целое число) . В этом случае

   (7.30)

9. Могут быть наложены дополнительные условия "на отправку" (то есть на сроки окончания отдельных работ). Так, если обработка детали на станке должна быть закончена к сроку , то

   (7.31)

10. В качестве критерия оптимальности принимается минимизация общего времени обработки партии. Пусть — дата полного завершения работ. Нужно минимизировать при условиях

    (7.32)

11. и при условиях (7.26.), (7.27.), (7.28.) или его вариантах и, возможно, еще при условиях (7.31.).

Всего в этой модели приходится вводить переменных (не считая и свободных переменных). Эти переменные, кроме того, должны быть целочисленными. Для реальных задач даже самых скромных размеров это приводит к весьма громоздким моделям (так, при

и мы получаем ).

Однако описанная модель, по-видимому, является одной из наиболее экономных в смысле размеров получающейся целочисленной задачи. Интересующийся теорией расписаний может посмотреть книгу Шурба В.В., Подчасова Т.П., Пшичук А.Н., Тур Л.П. , Задачи календарного планирования и методы их решения. (Киев, "Наукова думка", 1966.).