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

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

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

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

4.2. Известно несколько формулировок задачи теории расписаний в виде целочисленных задач линейного программирования. Опишем одну из возможных

постановок, основой для которой является идея А. Манна [114]; см. также [98], гл. 12.

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

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

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

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

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

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

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

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

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

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

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

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

и при условиях (4.2), (4.3), (4.4) (или его вариантах) и, возможно, еще при условиях (4.5).

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

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

Читатель, интересующийся теорией расписаний, может получить довольно полное представление о современном состоянии вопроса, ознакомившись со сборником переводов «Календарное планирование» [98]. Отметим также книгу [41].