Оптимизация расписания типа Job Shop

Sturmer · 05/10/17 9

svv в сообщении #1254364 писал(а):

Dmitriy40 в сообщении #1254363 писал(а):

А смысл вообще иметь 3-ю колонку

Так а я о чём? :-)

Dmitriy40 в сообщении #1254363 писал(а):

общее время (сумма второй колонки) не меняется и оптимизировать нечего

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

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

-- 09.10.2017, 23:44 --

Dmitriy40 в сообщении #1254348 писал(а):

Sturmer в сообщении #1254345 писал(а):

А не моли бы вы написать полный набор неравенств для случая из 3-х заданий? А то я что-то, не пойму и туплю.

Ну ... А я туплю с заданием перестановок заданий и запретом одновременного выполнения ... Условия же на зависимость заданий несложно. Предположим что 2-е задание зависит от 1-го, третье - тоже только от первого. Обозначим время начала задания как $t_i$ , длительность задания как $\Delta_i$ . $\left\{ \begin{array}{rcl} t_1 &\ge& 0 \\ t_2 &\ge& t_1+\Delta_1 \\ t_3 &\ge& t_1+\Delta_1 \\ \end{array} \right.$

Здесь задана жесткая последовательность выполнения. Мы не можем Т3 поставить раньше Т1, а это, например, может быть оптимальным решением.

-- 09.10.2017, 23:50 --

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

mserg · 17/10/08 ∞ 1313

В виде уравнений записать непересекаемость задач на одной машине можно с помощью псевдобулевых переменных. Это нужно сделать для каждой пары задач.
Для любой пары задач должно выполняться одно из условий:
$t_i \ge t_j+d_j$ или
$t_j \ge t_i+d_i$
Пусть $b_ij$ - переменная, которая принимает значение 0 при выполнении первого неравенства, и 1 - при выполнении второго. Тогда
$t_i \ge t_j+d_j - b_{ij}M$ и
$t_j \ge t_i+d_i - (1-b_{ij})M$
Где $M$ - достаточно большое число.

Это приводит к частично-целочисленным задачам. Решаются пакетами (линейного программирования) очень плохо.
Гораздо лучше результаты по технике а-ля "программирование в ограничениях"

Sturmer · 05/10/17 9

mserg в сообщении #1254542 писал(а):

В виде уравнений записать непересекаемость задач на одной машине можно с помощью псевдобулевых переменных. Это нужно сделать для каждой пары задач.
Для любой пары задач должно выполняться одно из условий:
$t_i \ge t_j+d_j$ или
$t_j \ge t_i+d_i$
Пусть $b_ij$ - переменная, которая принимает значение 0 при выполнении первого неравенства, и 1 - при выполнении второго. Тогда
$t_i \ge t_j+d_j - b_{ij}M$ и
$t_j \ge t_i+d_i - (1-b_{ij})M$
Где $M$ - достаточно большое число.

Это приводит к частично-целочисленным задачам. Решаются пакетами (линейного программирования) очень плохо.
Гораздо лучше результаты по технике а-ля "программирование в ограничениях"

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

mserg · 17/10/08 ∞ 1313

Простые методы, к сожалению, не эффективны для качественного решения таких задач.

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

Такого, чтобы прочитать и запрограммировать, - не знаю.
К тому же эффективность сильно зависит от критерия. А если ресурс не бинарный, то все становится еще хуже.

Сложные методы сочетают в себя множество техник
* Эвристический поиск допустимых решений
* Локальная оптимизация
* Поиск а-ля метод "ветвей, границ и отсечений"
* Сжатие интервалов переменных начала/окончания работ
И т.д. и т.п., и все это управляется сложной системой, которая оттачивается на (тестовом) множестве задач (реальных или сгенерированных).

Есть коммерческие пакеты типа ILOG Scheduler, можно поискать руководство по фразе:
ilog scheduler manual
Довольно полезная штука в плане понимания техники описания подобных задач и терминологии.
Может быть есть возможность бесплатного использования для учебных заведений, но раньше даже за это просили деньги.

В свое время игрался с ILOG Scheduler. Задачи с критерием минимума окончания последней задачи решались довольно быстро. Но стоило задать кумулятивный критерий, как "решатель" завис.

Sturmer · 05/10/17 9

mserg в сообщении #1255017 писал(а):

Есть коммерческие пакеты типа ILOG Scheduler, можно поискать руководство по фразе:

ILOG Scheduler больше не существует, теперь он называется IBM Decision Optimization Center и стоит сумасшедших денег, а самое -
неприятное, что его нельзя попробовать не купив.
Хочется найти ему альтернативу. Задачи бывают разные по размеру. Нередко в бизнесе встречаются довольно небольшие задачи, хочется попробовать решить их с помощью например SolverStudiо + cолвер в зависимости от размера задачи и бюджета.
Возможности SolverStudiо по переменным и ограничениям более или менее понятны, хочется определиться с алгоритмами, т.к. от них напрямую зависит возможность решения, а также производительность.

mserg · 17/10/08 ∞ 1313

Как и предполагалось, попробовать/скачать встречным/поперечным ILOG Scheduler, которого теперь "больше не существует", нельзя. Припоминаю, это случилось после покупки ILOG компанией IBM.

А вот в компании, в которой я работаю, почему-то можно :-)

. По-крайней мере, CPLEX я скачивал и пробовал 1-2 года назад. Цена меня, конечно, потрясла...

В общем-то, я зачем давал ссылку... Описываются такие задачи с помощью специального языка, который включает в себя Работы, Отношения между ними, Ресурсы, Резервуары и т.д. Где-то была у этих "врагов" ссылка со сборником алгоритмов по scheduling ... но это было лет 5-10 назад... имеет смысл еще поискать.
В SolverStudiо, кстати, не заметил поддержку некоммерческих продуктов с scheduling - может невнимательно смотрел.

Припоминаю, я находил статьи тут:
http://citeseerx.ist.psu.edu
Что-нибудь типа jobshop, scheduling и т.п. Неплохо бы знать "основы" "Constraint Programming"...

При чтении статей "моск" может сломаться - будьте осторожнее. Сейчас вспомнил, что один француз в статье написал, что у другого француза в алгоритме ошибка (в научной статье!). И точно ведь, ошибка была - потратив часов 5 на изучение алгоритма в 20-30 строк, понял где эта ошибка была.

Запрограммировать общий алгоритм - это несколько лет жизни ...
Вас, как я понимаю, это не остановит.

Sturmer · 05/10/17 9