Задача оптимальной загрузки оборудования.

Есть 2 станка (СТ1 и СТ2). Каждый из станков может выполнять 2 технологических операции (О1 и О2).

Предприятие выпускает 2 изделия (И1 и И2). Для каждого изделия есть технология изготовления.

Технология изготовления изделия А:

Шаг A1. Операция O1. Выполняется на станке СТ1 (время обработки С1) или СТ2 (время обработки С2).
Шаг A2. Операция О2. Выполняется на станке СТ1 (время обработки С3).
Технология изготовления изделия Б:
Шаг Б1. Операция O1. Выполняется на станке СТ1 (время обработки С4) или СТ2 (время обработки С5).
Шаг Б2. Операция О2. Выполняется на станке СТ1 (время обработки С6) или СТ2 (время обработки С7).

Последовательность шагов внутри технологии имеет принципиальное значение. То есть, нельзя сначала выполнить шаг А2, а затем А1. Ни один из шагов не может быть пропущен.

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

Кроме того, могут присутствовать ограничения, связанные с перерывами в работе станков. Это может быть связано:
- с графиком работы предприятия в целом (одна смена, две смены, три смены);
- с плановыми ремонтами, “привязанными” к конкретному станку. То есть, данный станок каждый понедельник, с 8 до 10 часов “недоступен”.
- с поломкой станка;
- с ремонтами и профилактиками, связанными с фактической загрузкой оборудования. Например, данный станок должен быть выключен на 1 час после изготовления 1000 изделий. Или после каждых N часов работы.
В конкретном случае, который мы рассматриваем, идет речь о 3-х сменной работе предприятия, но присутствуют плановые профилактики, зависящие (по-моему) от выработки. Ну и какие-то глобальные профилактические работы (раз в год…). И, конечно, станок может сломаться.

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

Результат должен быть представлен в виде сменного графика,
т. е. таблицы со следующими столбцами:

- Дата/время начала операции
- Станок
- Изделие
- Операция
- Кол-во единиц
- Длительность


Обращаем внимание на следующие моменты:
- Длительность шага является производной от времени начала, технологии и количества единиц (известно время обработки одной единицы данного изделия на данном станке для данной операции);
- Объем (кол-во единиц) может дробиться. Например, план производства данного изделия составляет 90 тыс. единиц. Сменный график может содержать 30 заданий по 3 тыс. единиц (по 3 тыс. в день) и “перемежаться” изготовлением других изделий. Однако может существовать ограничение на минимальное количество единиц в задании. Понятно, что в графике не может стоять изготовление одного изделия И1 за 1 минуту, затем 1000 изделий И2 за 5 часов, а затем еще раз одного изделия И1. Это ограничение связано, в частности, с необходимостью перенастройки станков при переключениях с изделия на изделие. В принципе интересно было бы узнать, какой математический аппарат должен использоваться при ограничениях дискретности. Однако в данной конкретной ситуации можно этим пренебречь и оперировать понятием партии. Например, если в приведенном выше примере минимальный объем задания – 3 тыс, то мы планируем выпуск не 90 тыс изделий, а 30 партий.
- приведенный выше сменный график является исчерпывающе информативным. По нему можно узнать, какую операцию должен выполнять данный станок в данную единицу времени. На его основе можно реализовать любую необходимую визуализацию.
- Время нужно рассчитывать до минут.

Подскажите, какой метод оптимизации применим для решения данной задачи?

авторвсе методы эвристические - есть литература по расчету расписаний (см. MES).

Что такое MES? Автор, метод расчета, книга?

Нашел такие подходы:
1) целочисленное линейное программирование
Позволяет найти точный оптимум. Минус - квадратичная зависимость
от числа станков/деталей/операций тех. процесса
на средней по объему задаче - 50 станков, 400 деталей, 30 операций -
размерность матрицы и число переменных порядка сотен тысяч

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

3) стохастические и комбинаторный подходы - похоже,
применять бессмысленно или неалгоритмизуемо.

В общем, ищем эвристические методы решений задач
теории расписаний...

Кто подскажет правильную книгу? ;-)