Перейти к основному содержимому

Интервалы и ресурсы

Семейство ограничений предназначено для расписаний (планирование во времени) и упаковки (размещение в пространстве). Эти задачи лежат в основе модулей APS (Advanced Planning and Scheduling), MES (Manufacturing Execution System) и алгоритмов раскладки в WMS (Warehouse Management System): графики оперативного производства, диспетчеризация цеха, планирование загрузки оборудования, складская топология.

Все ограничения семейства построены вокруг одного объекта — интервала. Из интервалов формируются прямоугольники для упаковки 2D, потребности для совместного использования ресурсов, события накопления для динамических резервуаров.

Интервал​

Интервал описывается тремя связанными переменными:

  • Начало — момент времени, в который интервал начинается;
  • Размер — длительность (всегда неотрицательная);
  • Конец — момент времени, в который интервал заканчивается.

Между переменными автоматически удерживается равенство Начало + Размер = Конец. Решатель определяет значения переменных так, чтобы это равенство выполнялось совместно с остальными ограничениями модели.

Интервал создаётся методом Интервал менеджера ограничений. Интервал бывает обязательным или опциональным — в зависимости от того, передана ли булева переменная-условие существования:

  • обязательный интервал — учитывается в расписании всегда;
  • опциональный интервал — учитывается только при истинности связанной булевой переменной; при её ложности интервал исключается из проверок других ограничений.

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

Виды интервалов​

В большинстве задач достаточно двух видов интервалов:

  • Полный интервал (Интервал) — все три переменные подбираются решателем. Применяется, когда длительность работы является решением (например, выбирается между «быстро и дорого» или «медленно и дёшево»).
  • Фиксированный интервал (ФиксированныйИнтервал) — длительность задана целочисленным числом, переменной является только начало. Применяется в большинстве задач планирования: длительность операции на станке известна заранее.

Оба вида интервалов могут быть как обязательными, так и опциональными.

Запрет перекрытий​

Ограничение ЗапретПерекрытий запрещает пересечение каких-либо двух интервалов из заданного массива:

ИнтервалыСтанка = О2.Утилиты().Массив(
    Операция1НаСтанке,
    Операция2НаСтанке,
    Операция3НаСтанке
);

Модель.Ограничения().ЗапретПерекрытий(ИнтервалыСтанка);

Это типовое ограничение «один ресурс — одна задача в момент времени» в задачах планирования. На каждый ресурс (станок, оператор, помещение) накладывается отдельный вызов ЗапретПерекрытий со своим массивом интервалов. Если в массиве присутствуют опциональные интервалы, ограничение применяется с учётом их условий существования: интервалы с ложным условием в проверке не участвуют.

Потребности и конкурентное использование​

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

  • ПотребностьИнтервала — объект, привязывающий интервал к ресурсу с указанием количества единиц ресурса, занимаемых интервалом (один оператор на работу в обычном режиме, два оператора при настройке станка).
  • КонкурентноеИспользование — ограничение, гарантирующее, что суммарная потребность пересекающихся во времени интервалов не превышает заданной ёмкости ресурса.
ВсегоОператоров = 5;

Потребности = Новый Массив();

Для Каждого Работа Из СписокРабот Цикл

    ИнтервалРаботы = Модель.Ограничения().Интервал(
        Работа.Начало,
        Работа.Длительность,
        Работа.Конец
    );

    Потребности.Добавить(
        Модель.Ограничения().ПотребностьИнтервала(
            ИнтервалРаботы,
            Работа.ТребуемоеЧислоОператоров
        )
    );

КонецЦикла;

// В каждый момент времени суммарное число занятых операторов <= 5
Модель.Ограничения().КонкурентноеИспользование(ВсегоОператоров, Потребности);

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

Прямоугольники и упаковка 2D​

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

Над прямоугольниками применяется ограничение ЗапретПерекрытий2D: набор прямоугольников не должен пересекаться по площади.

ИнтервалX = Модель.Ограничения().Интервал(НачалоX, ШиринаКоробки, КонецX);
ИнтервалY = Модель.Ограничения().Интервал(НачалоY, ВысотаКоробки, КонецY);

Прямоугольник = Модель.Ограничения().Прямоугольник(ИнтервалX, ИнтервалY);

// ... другие прямоугольники регистрируются аналогично ...

Модель.Ограничения().ЗапретПерекрытий2D(ВсеПрямоугольники);

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

Резервуары​

Когда ресурс представляет собой накапливающуюся величину, изменяющуюся во времени за счёт приходов и расходов (складской запас, заряд аккумулятора, наличность в кассе, остаток воды в системе), применяется ограничение Резервуар. Ограничение требует, чтобы остаток оставался в заданном диапазоне [МинЗначение, МаксЗначение] в каждый момент времени.

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

СобытияНакопления = Новый Массив();

// Приход 25 единиц на склад в момент, определяемый решателем
СобытияНакопления.Добавить(
    Модель.Ограничения().СобытиеНакопления(
        Модель.Переменные().ДобавитьИзДиапазона(0, 100),  // момент времени
        25                                    // приход
    )
);

// Отгрузка 10 единиц в другой момент
СобытияНакопления.Добавить(
    Модель.Ограничения().СобытиеНакопления(
        Модель.Переменные().ДобавитьИзДиапазона(0, 100),
        -10                                   // расход
    )
);

// ... остальные события прихода и расхода ...

// Остаток на складе в каждый момент времени принадлежит [0, 200]
Модель.Ограничения().Резервуар(0, 200, СобытияНакопления);

Прикладные сценарии — управление складскими запасами в системах класса ERP/MRP, планирование зарядки и разрядки аккумуляторов, инвентаризация оборотных средств в кассе или на счёте, диспетчеризация складских операций в WMS.

Иллюстрация: ограничения для jobshop​

В задаче оперативного производственного планирования (jobshop) присутствуют несколько работ, каждая из которых состоит из последовательных операций; каждая операция выполняется на конкретном станке; на одном станке в момент времени выполняется не более одной операции; внутри работы порядок операций фиксирован. Базовые конструкции формулировки приведены ниже.

Создание интервала операции​

НачалоОперации = Модель.Переменные().ДобавитьИзДиапазона(0, ГоризонтПланирования);

ИнтервалОперации = Модель.Ограничения().ФиксированныйИнтервал(
    НачалоОперации,
    Операция.Длительность
);

Запрет перекрытий по станку​

// Все интервалы операций, выполняемых на конкретном станке
Модель.Ограничения().ЗапретПерекрытий(ИнтервалыСтанка);

Порядок операций внутри работы​

// Следующая операция той же работы не начинается раньше окончания предыдущей
Модель.Ограничения().ЗначениеБольшеИлиРавно(
    СледующаяОперация.Начало,
    ПредыдущаяОперация.Конец
);

Из этих конструкций и целевой функции «минимизировать время окончания последней работы» формируется задача jobshop. Полные рабочие примеры приведены в разделе примеров:

Полный перечень методов​

Полный набор методов работы с интервалами, ресурсами и резервуарами приведён в разделах Программный интерфейс — Интервалы и Программный интерфейс — Резервуары.