Планирование производственных операций

В данном разделе рассматривается классическая задача составления оптимального расписания выполнения производственных работ на станках (Job Shop Scheduling Problem). Эта задача широко встречается в производственном планировании, где необходимо эффективно распределить ресурсы и минимизировать общее время производства.

Каждая производственная работа представляет собой последовательность технологических операций, которые должны выполняться в строго определённом порядке. Для выполнения каждой операции требуется конкретный станок и известное время обработки. Например, изготовление детали может включать последовательные этапы: токарная обработка на станке 1, фрезеровка на станке 2, шлифовка на станке 3.

Ключевая сложность задачи заключается в том, что станки являются общими ресурсами — на одном станке могут выполняться операции из разных работ, но не одновременно. Необходимо так распределить операции по времени, чтобы:

• Соблюдалась технологическая последовательность операций внутри каждой работы
• На каждом станке операции не пересекались во времени
• Общее время завершения всех работ было минимальным

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

Постановка задачи

Имеется три работы, каждая из которых состоит из нескольких операций. Для каждой операции известен станок, на котором она выполняется, и её длительность:

• Работа 0: Операция 0 (станок 0, 3 ед. времени) → Операция 1 (станок 1, 2 ед.) → Операция 2 (станок 2, 2 ед.);
• Работа 1: Операция 0 (станок 0, 2 ед. времени) → Операция 1 (станок 2, 1 ед.) → Операция 2 (станок 1, 4 ед.);
• Работа 2: Операция 0 (станок 1, 4 ед. времени) → Операция 1 (станок 2, 3 ед.);
• Операции в рамках одной работы должны выполняться последовательно в заданном порядке;
• На одном станке операции не могут выполняться одновременно;
• Требуется минимизировать общее время завершения всех работ (makespan).

Решение задачи

1. Выбор модели

Для решения задачи планирования производства (Job Shop Scheduling Problem) используется модель ограничений. Эта модель естественным образом работает с интервалами времени и логическими ограничениями на последовательность и непересечение операций. Модель ограничений позволяет описать технологические зависимости и найти оптимальное расписание.

2. Создание модели

Создадим объект модели, в котором будем описывать переменные, ограничения и целевую функцию.

// Создание модели ограничений
Модель = О2
    .Модели()
    .МодельОграничений()
    .СоздатьМодель();

3. Ввод данных

Описываются все работы и их операции. Для каждой операции задаётся структура с указанием номера станка и длительности выполнения.

// Входные данные по работам и операциям
ДанныеРабот = Новый Массив;

// Работа 0
Работа0 = Новый Массив;
Работа0.Добавить(Новый Структура("Станок, Длительность", 0, 3)); // Операция 0
Работа0.Добавить(Новый Структура("Станок, Длительность", 1, 2)); // Операция 1
Работа0.Добавить(Новый Структура("Станок, Длительность", 2, 2)); // Операция 2
ДанныеРабот.Добавить(Работа0);

// Работа 1
Работа1 = Новый Массив;
Работа1.Добавить(Новый Структура("Станок, Длительность", 0, 2));
Работа1.Добавить(Новый Структура("Станок, Длительность", 2, 1));
Работа1.Добавить(Новый Структура("Станок, Длительность", 1, 4));
ДанныеРабот.Добавить(Работа1);

// Работа 2
Работа2 = Новый Массив;
Работа2.Добавить(Новый Структура("Станок, Длительность", 1, 4));
Работа2.Добавить(Новый Структура("Станок, Длительность", 2, 3));
ДанныеРабот.Добавить(Работа2);   

Также определяется количество станков и вычисляется горизонт планирования — верхняя граница времени, равная сумме длительностей всех операций:

// Определяем количество станков
НомерПоследнегоСтанка = 0;
Для Каждого Работа Из ДанныеРабот Цикл
    Для Каждого Операция Из Работа Цикл
        Если Операция.Станок > НомерПоследнегоСтанка Тогда
            НомерПоследнегоСтанка = Операция.Станок;
        КонецЕсли;
    КонецЦикла;
КонецЦикла;
КоличествоСтанков = НомерПоследнегоСтанка + 1;

ВсеСтанки = Новый Массив;
Для К = 0 По КоличествоСтанков - 1 Цикл
    ВсеСтанки.Добавить(К);
КонецЦикла;

// Вычисляем горизонт планирования
ГоризонтПланирования = 0;
Для Каждого Работа Из ДанныеРабот Цикл
    Для Каждого Операция Из Работа Цикл
        ГоризонтПланирования = ГоризонтПланирования + Операция.Длительность;
    КонецЦикла;
КонецЦикла;

4. Регистрация переменных

Для каждой операции создаются переменные времени начала и окончания, а также формируется интервал — специальная конструкция модели ограничений, связывающая начало, длительность и окончание операции. Интервалы группируются по станкам для последующего наложения ограничений на непересечение.

// Регистрируем переменные
ВсеЗадачи          = Новый Массив(ДанныеРабот.Количество());
ИнтервалыПоСтанкам = Новый Соответствие;

Для Каждого Станок Из ВсеСтанки Цикл
    ИнтервалыПоСтанкам.Вставить(Станок, Новый Массив);
КонецЦикла;

Для НомерРаботы = 0 По ДанныеРабот.Количество() - 1 Цикл
    Работа                 = ДанныеРабот[НомерРаботы];
    ВсеЗадачи[НомерРаботы] = Новый Массив(Работа.Количество());
    
    Для НомерОперации = 0 По Работа.Количество() - 1 Цикл
        Операция             = Работа[НомерОперации];
        Станок               = Операция.Станок;
        ДлительностьОперации = Операция.Длительность;
        
        Начало   = Модель.ПеременнаяДиапазона(0, ГоризонтПланирования);
        Конец    = Модель.ПеременнаяДиапазона(0, ГоризонтПланирования);
        Интервал = Модель.Ограничения().Интервал(Начало, ДлительностьОперации, Конец);
        
        ВсеЗадачи[НомерРаботы][НомерОперации] = Новый Структура("Начало,Конец,Интервал", Начало, Конец, Интервал);
        
        МассивИнтервалов = ИнтервалыПоСтанкам.Получить(Станок);
        МассивИнтервалов.Добавить(Интервал);
    КонецЦикла;
КонецЦикла;

5. Описание ограничений

Запрет перекрытий на станках. Операции, выполняемые на одном станке, не могут пересекаться во времени. Используется специальное ограничение ЗапретПерекрытий, которое автоматически обеспечивает непересечение всех интервалов.

// Ограничение: операции на одном станке не пересекаются
Для Каждого Станок Из ВсеСтанки Цикл
    ИнтервалыНаСтанке = ИнтервалыПоСтанкам.Получить(Станок);
    Модель.Ограничения().ЗапретПерекрытий(ИнтервалыНаСтанке);
КонецЦикла;

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

// Ограничение: операции в рамках одной работы выполняются последовательно
Для НомерРаботы = 0 По ДанныеРабот.Количество() - 1 Цикл
    Работа = ДанныеРабот[НомерРаботы];
    
    Для НомерОперации = 0 По Работа.Количество() - 2 Цикл
        Текущая   = ВсеЗадачи[НомерРаботы][НомерОперации];
        Следующая = ВсеЗадачи[НомерРаботы][НомерОперации + 1];
        
        Модель.Ограничения().ЗначениеМеньшеИлиРавно(Текущая.Конец, Следующая.Начало);
    КонецЦикла;
КонецЦикла;

6. Описание целевой функции

Целевая функция — минимизация времени завершения всех работ (makespan). Вводится переменная МаксимальноеВремя, которая должна быть не меньше времени окончания любой работы. Минимизируя эту переменную, решатель находит наиболее компактное расписание.

// Целевая функция: минимизируем время завершения всех работ
МаксимальноеВремя = Модель.ПеременнаяДиапазона(0, ГоризонтПланирования, "МаксимальноеВремя");

Для НомерРаботы = 0 По ДанныеРабот.Количество() - 1 Цикл
    Работа                 = ДанныеРабот[НомерРаботы];
    НомерПоследнейОперации = Работа.Количество() - 1;
    
    ДанныеПоследнейОперации = ВсеЗадачи[НомерРаботы][НомерПоследнейОперации];
    КонецПоследнейОперации  = ДанныеПоследнейОперации.Конец;
    
    Модель.Ограничения().ЗначениеБольшеИлиРавно(МаксимальноеВремя, КонецПоследнейОперации);
КонецЦикла;

Модель.Минимизировать(МаксимальноеВремя);

7. Решение модели

Запускаем процесс оптимизации методом Решить.

// Решение модели
Решение = Модель.Решить();

8. Вывод результатов

Результаты извлекаются из решения, сортируются по станкам и времени начала, затем выводится детальное расписание с указанием времени начала и окончания каждой операции на каждом станке.

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    НазначенныеЗадачи = Новый Соответствие;
    Для Каждого Станок Из ВсеСтанки Цикл
        НазначенныеЗадачи.Вставить(Станок, Новый Массив);
    КонецЦикла;
    
    Для НомерРаботы = 0 По ДанныеРабот.Количество() - 1 Цикл
        Работа = ДанныеРабот[НомерРаботы];
        
        Для НомерОперации = 0 По Работа.Количество() - 1 Цикл
            Операция             = Работа[НомерОперации];
            Станок               = Операция.Станок;
            ДлительностьОперации = Операция.Длительность;
            
            ДанныеОперации = ВсеЗадачи[НомерРаботы][НомерОперации];
            Начало         = Решение.ЗначениеПеременной(ДанныеОперации.Начало);
            
            Задача = Новый Структура(
                "Начало, Работа, Операция, Длительность", 
                Начало, НомерРаботы, НомерОперации, ДлительностьОперации);
            
            МассивЗадач = НазначенныеЗадачи.Получить(Станок);
            МассивЗадач.Добавить(Задача);
        КонецЦикла;
    КонецЦикла;
    
    // Сортировка задач по времени начала
    Для Каждого Станок Из ВсеСтанки Цикл
        МассивЗадач = НазначенныеЗадачи.Получить(Станок);
        
        Для i = 0 По МассивЗадач.Количество() - 2 Цикл
            Для j = i + 1 По МассивЗадач.Количество() - 1 Цикл
                Если МассивЗадач[i].Начало > МассивЗадач[j].Начало Тогда
                    ВременнаяЗадача = МассивЗадач[i];
                    МассивЗадач[i]  = МассивЗадач[j];
                    МассивЗадач[j]  = ВременнаяЗадача;
                КонецЕсли;
            КонецЦикла;
        КонецЦикла;
    КонецЦикла;
    
    ОбщееВремя = Решение.ЗначениеПеременной(МаксимальноеВремя);
    
    Сообщение = "Оптимальное расписание работ" + Символы.ПС + Символы.ПС;
    Сообщение = Сообщение + "Общее время выполнения: " + ОбщееВремя + Символы.ПС + Символы.ПС;
    
    Для Каждого Станок Из ВсеСтанки Цикл
        МассивЗадач = НазначенныеЗадачи.Получить(Станок);
        
        Сообщение = Сообщение + "Станок " + Станок + ":" + Символы.ПС;
        
        Для Каждого Задача Из МассивЗадач Цикл
            ВремяНачала    = Задача.Начало;
            ВремяОкончания = ВремяНачала + Задача.Длительность;
            
            Сообщение = Сообщение + СтрШаблон(
                "  Работа %1, Операция %2: начало %3, окончание %4 (длительность: %5)%6",
                Задача.Работа,
                Задача.Операция,
                ВремяНачала,
                ВремяОкончания,
                Задача.Длительность,
                Символы.ПС
            );
        КонецЦикла;
        
        Сообщение = Сообщение + Символы.ПС;
    КонецЦикла;
    
    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено!");
КонецЕсли;

Полный код решения задачи

Ниже представлен полный код решения. Вы также можете скачать пример в виде готовой обработки.

// Создание модели ограничений
Модель = О2
    .Модели()
    .МодельОграничений()
    .СоздатьМодель();

// Входные данные по работам и операциям
ДанныеРабот = Новый Массив;

// Работа 0
Работа0 = Новый Массив;
Работа0.Добавить(Новый Структура("Станок, Длительность", 0, 3)); // Операция 0
Работа0.Добавить(Новый Структура("Станок, Длительность", 1, 2)); // Операция 1
Работа0.Добавить(Новый Структура("Станок, Длительность", 2, 2)); // Операция 2
ДанныеРабот.Добавить(Работа0);

// Работа 1
Работа1 = Новый Массив;
Работа1.Добавить(Новый Структура("Станок, Длительность", 0, 2));
Работа1.Добавить(Новый Структура("Станок, Длительность", 2, 1));
Работа1.Добавить(Новый Структура("Станок, Длительность", 1, 4));
ДанныеРабот.Добавить(Работа1);

// Работа 2
Работа2 = Новый Массив;
Работа2.Добавить(Новый Структура("Станок, Длительность", 1, 4));
Работа2.Добавить(Новый Структура("Станок, Длительность", 2, 3));
ДанныеРабот.Добавить(Работа2);   

// Определяем количество станков
НомерПоследнегоСтанка = 0;
Для Каждого Работа Из ДанныеРабот Цикл
    Для Каждого Операция Из Работа Цикл
        Если Операция.Станок > НомерПоследнегоСтанка Тогда
            НомерПоследнегоСтанка = Операция.Станок;
        КонецЕсли;
    КонецЦикла;
КонецЦикла;
КоличествоСтанков = НомерПоследнегоСтанка + 1;

ВсеСтанки = Новый Массив;
Для К = 0 По КоличествоСтанков - 1 Цикл
    ВсеСтанки.Добавить(К);
КонецЦикла;

// Вычисляем горизонт планирования
ГоризонтПланирования = 0;
Для Каждого Работа Из ДанныеРабот Цикл
    Для Каждого Операция Из Работа Цикл
        ГоризонтПланирования = ГоризонтПланирования + Операция.Длительность;
    КонецЦикла;
КонецЦикла;

// Регистрируем переменные
ВсеЗадачи          = Новый Массив(ДанныеРабот.Количество());
ИнтервалыПоСтанкам = Новый Соответствие;

Для Каждого Станок Из ВсеСтанки Цикл
    ИнтервалыПоСтанкам.Вставить(Станок, Новый Массив);
КонецЦикла;

Для НомерРаботы = 0 По ДанныеРабот.Количество() - 1 Цикл
    Работа                 = ДанныеРабот[НомерРаботы];
    ВсеЗадачи[НомерРаботы] = Новый Массив(Работа.Количество());
    
    Для НомерОперации = 0 По Работа.Количество() - 1 Цикл
        Операция             = Работа[НомерОперации];
        Станок               = Операция.Станок;
        ДлительностьОперации = Операция.Длительность;
        
        Начало   = Модель.ПеременнаяДиапазона(0, ГоризонтПланирования);
        Конец    = Модель.ПеременнаяДиапазона(0, ГоризонтПланирования);
        Интервал = Модель.Ограничения().Интервал(Начало, ДлительностьОперации, Конец);
        
        ВсеЗадачи[НомерРаботы][НомерОперации] = Новый Структура("Начало,Конец,Интервал", Начало, Конец, Интервал);
        
        МассивИнтервалов = ИнтервалыПоСтанкам.Получить(Станок);
        МассивИнтервалов.Добавить(Интервал);
    КонецЦикла;
КонецЦикла;

// Ограничение: операции на одном станке не пересекаются
Для Каждого Станок Из ВсеСтанки Цикл
    ИнтервалыНаСтанке = ИнтервалыПоСтанкам.Получить(Станок);
    Модель.Ограничения().ЗапретПерекрытий(ИнтервалыНаСтанке);
КонецЦикла;

// Ограничение: операции в рамках одной работы выполняются последовательно
Для НомерРаботы = 0 По ДанныеРабот.Количество() - 1 Цикл
    Работа = ДанныеРабот[НомерРаботы];
    
    Для НомерОперации = 0 По Работа.Количество() - 2 Цикл
        Текущая   = ВсеЗадачи[НомерРаботы][НомерОперации];
        Следующая = ВсеЗадачи[НомерРаботы][НомерОперации + 1];
        
        Модель.Ограничения().ЗначениеМеньшеИлиРавно(Текущая.Конец, Следующая.Начало);
    КонецЦикла;
КонецЦикла;

// Целевая функция: минимизируем время завершения всех работ
МаксимальноеВремя = Модель.ПеременнаяДиапазона(0, ГоризонтПланирования, "МаксимальноеВремя");

Для НомерРаботы = 0 По ДанныеРабот.Количество() - 1 Цикл
    Работа                 = ДанныеРабот[НомерРаботы];
    НомерПоследнейОперации = Работа.Количество() - 1;
    
    ДанныеПоследнейОперации = ВсеЗадачи[НомерРаботы][НомерПоследнейОперации];
    КонецПоследнейОперации  = ДанныеПоследнейОперации.Конец;
    
    Модель.Ограничения().ЗначениеБольшеИлиРавно(МаксимальноеВремя, КонецПоследнейОперации);
КонецЦикла;

Модель.Минимизировать(МаксимальноеВремя);

// Решение модели
Решение = Модель.Решить();

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    НазначенныеЗадачи = Новый Соответствие;
    Для Каждого Станок Из ВсеСтанки Цикл
        НазначенныеЗадачи.Вставить(Станок, Новый Массив);
    КонецЦикла;
    
    Для НомерРаботы = 0 По ДанныеРабот.Количество() - 1 Цикл
        Работа = ДанныеРабот[НомерРаботы];
        
        Для НомерОперации = 0 По Работа.Количество() - 1 Цикл
            Операция             = Работа[НомерОперации];
            Станок               = Операция.Станок;
            ДлительностьОперации = Операция.Длительность;
            
            ДанныеОперации = ВсеЗадачи[НомерРаботы][НомерОперации];
            Начало         = Решение.ЗначениеПеременной(ДанныеОперации.Начало);
            
            Задача = Новый Структура(
                "Начало, Работа, Операция, Длительность", 
                Начало, НомерРаботы, НомерОперации, ДлительностьОперации);
            
            МассивЗадач = НазначенныеЗадачи.Получить(Станок);
            МассивЗадач.Добавить(Задача);
        КонецЦикла;
    КонецЦикла;
    
    // Сортировка задач по времени начала
    Для Каждого Станок Из ВсеСтанки Цикл
        МассивЗадач = НазначенныеЗадачи.Получить(Станок);
        
        Для i = 0 По МассивЗадач.Количество() - 2 Цикл
            Для j = i + 1 По МассивЗадач.Количество() - 1 Цикл
                Если МассивЗадач[i].Начало > МассивЗадач[j].Начало Тогда
                    ВременнаяЗадача = МассивЗадач[i];
                    МассивЗадач[i]  = МассивЗадач[j];
                    МассивЗадач[j]  = ВременнаяЗадача;
                КонецЕсли;
            КонецЦикла;
        КонецЦикла;
    КонецЦикла;
    
    ОбщееВремя = Решение.ЗначениеПеременной(МаксимальноеВремя);
    
    Сообщение = "Оптимальное расписание работ" + Символы.ПС + Символы.ПС;
    Сообщение = Сообщение + "Общее время выполнения: " + ОбщееВремя + Символы.ПС + Символы.ПС;
    
    Для Каждого Станок Из ВсеСтанки Цикл
        МассивЗадач = НазначенныеЗадачи.Получить(Станок);
        
        Сообщение = Сообщение + "Станок " + Станок + ":" + Символы.ПС;
        
        Для Каждого Задача Из МассивЗадач Цикл
            ВремяНачала    = Задача.Начало;
            ВремяОкончания = ВремяНачала + Задача.Длительность;
            
            Сообщение = Сообщение + СтрШаблон(
                "  Работа %1, Операция %2: начало %3, окончание %4 (длительность: %5)%6",
                Задача.Работа,
                Задача.Операция,
                ВремяНачала,
                ВремяОкончания,
                Задача.Длительность,
                Символы.ПС
            );
        КонецЦикла;
        
        Сообщение = Сообщение + Символы.ПС;
    КонецЦикла;
    
    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено!");
КонецЕсли;

  Скачать пример