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

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

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

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.).