Задача оптимизации потока

[Алекс77]

Добрый день!

Есть следующая задача.

Имеется $N=100$ конвейеров, каждый из которых имеет $T=21$ рабочую секцию.

Имеется поток работ, который распределяется между конвейерами. Каждая работа $J$ имеет собственный срок завершения - дата $D$, собственную длину занимаемых на конвейере секций $L$.

Каждая i-я из $L$ секций данной работы имеет собственный срок выполнения в днях - $J_i$. К концу этого срока данная секция работы ДОЛЖНА быть выгружена с конвейера, срок пребывания секции на конвейере не должен ни превышать, ни быть меньше $J_i$.

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

Цель оптимизации:
Основная: Увеличить количество выполняемых работ.
Вторичная: Минимизировать количество работ, распределяемых между разными конвейерами. Иными словами, предпочтительнее всю работу выполнять на одном и том же конвейере.

Ограничения:
1. Секции должны быть на конвейере на весь срок своего исполнения.
2. Секции не могут обгонять друг друга на конвейере.
3. Работы должны быть выполнены в срок, не ранее, не позднее.

Выходные данные:
1. График загрузки и выгрузки конвейеров. (Порядок загрузки и выгрузки работ, количество и даты на каждом из конвейеров.)
2. Сколько дополнительных и/или каких секций может быть вдобавок обработано в каждый день, чтобы не мешать основной цели оптимизации?

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

[пианист]

Правила не очень понятны. Вот, на берегу:
Уточните, плз, графики функционирования Ваших объектов: должны ли в начальный момент секции быть запущены, должны ли в начальный момент все работы быть начаты etc.
Верно ли, что моменты окончания работ абсолютно фиксированы, а не отсчитываются от начала?
По каким правилам переставляются работы? можно ли переставить назад на том же конвейере или просто вернуть к началу?
Верно ли, что как только самая правая секция достигает конца конвейера, мы должны убрать/переставить работу (а остальные секции, соответственно, будут оставаться до конца на ковейере вхолостую)?
Если оптимизируется не один параметр, требуется какое-то правило сопоставления (т.е. сведения, все-таки. к одному).

[Алекс77]

пианист в сообщении #1189047 писал(а):

Уточните, плз, графики функционирования Ваших объектов: должны ли в начальный момент секции быть запущены, должны ли в начальный момент все работы быть начаты etc.
Верно ли, что моменты окончания работ абсолютно фиксированы, а не отсчитываются от начала?
По каким правилам переставляются работы? можно ли переставить назад на том же конвейере или просто вернуть к началу?
Верно ли, что как только самая правая секция достигает конца конвейера, мы должны убрать/переставить работу (а остальные секции, соответственно, будут оставаться до конца на ковейере вхолостую)?

Моделируется поток производства продуктов по конвейерной схеме.
Ежедневно лента конвейера смещается вправо там, где это нужно. Секции работы загружаются слева и выгружаются справа конвейерной ленты. Если позволяют сроки и загруженные на ленту конвейера секции работы, то сдвиг не происходит.
Соответственно, для ясности, можете предполагать, что в конце рабочего дня крайние правые отработанные секции с истекшим сроком выполнения снимаются с конвейеров, производится сдвиг на необходимое количество свободных секций вправо, после чего на освободившиеся секции слева в начале следующего рабочего дня загружаются новые.
Работа состоит из нескольких секций, имеет входной параметр - дата окончания срока работы. Как один из контрольных случаев следует рассматривать такой, при котором для соблюдения сроков все секции данной работы распределяются по разным конвейерам, чтобы максимально сократить срок выполнения. Для простоты/удобства, можете считать, что в момент поступления задачи фиксируется не дата исполнения, а количество оставшихся до реализации дней.
Работы и секции уже находящиеся на конвейерах НЕ переставляются, не могут быть выгружены в середине, пока с ленты данного конвейера не вышли все остальные загрузки справа.

По поводу сведения к одному:
Цель оптимизации:
Основная: Увеличить количество выполняемых работ.

Надеюсь, что это объяснение прояснило Ваше представление о задаче. Буду благодарен за содействие!

[пианист]

Если я правильно уловил Вашу постановку задачи, речь идет о составлении расписания параллельных процессов.
Более-менее этой темой занимаются т.н. темпоральные логики (структуры Крипке etc).
Глянуть можно, например, в книжке Ю.Г. Карпов "Верификация параллельных и распределенных программных систем", легко найдете.
Еще, возможно, есть смысл обратиться к В.Н.Лебедеву (ВолГУ), он к примерно тем же задачам применяет теоретико-игровые методы (возможно, успешно ;).