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

[Sturmer]

Подскажите, пожалуйста, как в Excel можно описать задачу оптимизации расписания.
В этой задачи есть 2 типа переменных:
1. время выполнения каждого задания на машине;
2. последовательность выполнения заданий,т.к. от последовательности зависят потери, влияющие на целевую функцию.
Если с первым типом нет проблем, то как реализовать второй тип в Excel никак не пойму. Как последовательность описать через систему уравнений? Задавать как переменные время начала или окончания каждой задачи? Как? Этих времен понятное число комбинаций, нужно выбрать нужную, но как ее прописать в системе уравнений?

Интересует принцип, не с т.з. практического применения, а с целью поиграться, поискать закономерности, поразбираться с подходами.

Заранее спасибо за помощь!

[Dmitriy40]

Может неравенствами, время начала зависимого задания не меньше времени окончания предыдущего?

[svv]

Для каждого задания надо задать целое число — номер этого задания в последовательности заданий.

[Sturmer]

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

Может неравенствами, время начала зависимого задания не меньше времени окончания предыдущего?

Последовательность заданий и есть цель оптимизации, мы не можем jодновременно написать А>B и B>A

-- 09.10.2017, 20:46 --

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

Для каждого задания надо задать целое число — номер этого задания в последовательности заданий.

Я и пошел таким путем, сделав индекс последовательности переменной, вроде получилось. Но почитал теорию, решил попробовать, как рекомендуют через время начала или окончания задания, и зашел в тупик...

[Dmitriy40]

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

мы не можем jодновременно написать А>B и B>A

И не нужно, задания не могут зависеть друг от друга, значит одно из неравенств лишнее. Другое дело что задание может зависеть от нескольких, но это тоже выражается несложно: $t_a>t_b+\Delta_b,\;t_a>t_c+\Delta_c,\;t_a>t_d+\Delta_d,\;...$.

[svv]

По-моему, хранить целую переменную «номер задания в последовательности» гораздо удобнее, чем время начала.
Допустим, нужно задания переставить. В первом случае Вы просто переставляете значения их номеров. Во втором — требуется пересчитывать время начала для каждого задания, и это совсем не сводится к перестановке, потому что у них длительности выполнения разные.

[Dmitriy40]

С целыми конечно удобнее, кто ж спорит.
Вот только для одного потока вся задача смысла не имеет, суммарное время выполнения в любом порядке будет одним и тем же.
В многопоточном варианте при любой перестановке придётся проверять допустимость перестановки, чтобы заданию не улететь раньше его зависимостей. И тут уж без разницы сравнивать целые числа номеров или времена (которые тоже можно привести к целым, хоть в фемтосекундах). И от длительности заданий тоже не уйти. Единственное что можно хранить времена окончания заданий, а не начала, тогда проверки чуть проще. В общем не вижу кардинального преимущества номеров перед временами.

[Sturmer]

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

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

мы не можем jодновременно написать А>B и B>A

И не нужно, задания не могут зависеть друг от друга, значит одно из неравенств лишнее. Другое дело что задание может зависеть от нескольких, но это тоже выражается несложно: $t_a>t_b+\Delta_b,\;t_a>t_c+\Delta_c,\;t_a>t_d+\Delta_d,\;...$.

Не пойму только как это в Excel реализовать. Можете помочь подсказать?

[Dmitriy40]

Вот как раз про Excel и не подскажу (потому даже сомневался стоит ли упоминать). Но вроде бы он позволяет решать не только уравнения, но и неравенства.

[Sturmer]

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

Вот как раз про Excel и не подскажу (потому даже сомневался стоит ли упоминать). Но вроде бы он позволяет решать не только уравнения, но и неравенства.

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

[Dmitriy40]

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.$$

[svv]

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

В общем не вижу кардинального преимущества номеров перед временами.

Ну как же ж? Дело не в типе, пускай время — тоже целая переменная. Допустим, у нас есть 10 заданий с номерами $k$ от $1$ до $10$ (мы их не храним). Время начала первого задания $0$. В табличке хранится длительность $d_k$ и время окончания $f_k$ каждого задания:
$\begin{array}{ccc}k&d_k&f_k\\1&10&10\\2&5&15\\3&7&22\\4&5&27\\5&3&30\\6&4&34\\7&7&41\\8&5&46\\9&7&53\\10&2&55\end{array}$
Теперь я хочу только поменять местами первое и последнее задание. Результат: приходится пересчитывать весь правый столбец $f_k$. Там появляются числа, которых раньше не было в помине:
$\begin{array}{ccc}k&d_k&f_k\\1&2&2\\2&5&7\\3&7&14\\4&5&19\\5&3&22\\6&4&26\\7&7&33\\8&5&38\\9&7&45\\10&10&55\end{array}$
Вопрос: зачем это нужно?

[Dmitriy40]

А смысл вообще иметь 3-ю колонку если при любых перестановках общее время (сумма второй колонки) не меняется и оптимизировать нечего? Или в задаче есть ещё какие-то не обозначенные условия, влияющие на время выполнения заданий. Без них случай с одним потоком выполнения заданий тривиален и не интересен: выполняй любое готовое к выполнению (т.е. уже выполнены все задания, от которых зависит это) задание, да и всё, автоматом получишь оптимальное решение.

Вот когда потоков выполнения больше одного и есть зависимости между заданиями, вот тогда и становится интересно. Пример (указаны длительности заданий):
Поток $1: 3, 6, 7, 5$.
Поток $2: 4, 2, 1, 8$.
Если зависимости заданы как $3 \to 2, 2 \to 1, 1 \wedge 6 \to 7$, то я посмотрю как Вы попытаетесь переставить задания $6 \leftrightarrow 3$. И что при этом придётся вычислять и проверять.

[svv]

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

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

Так а я о чём?

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

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

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

[Dmitriy40]

Ок. Меня сбило слово "расписания" в топике и тексте. Если задания можно переставлять без ограничений, то действительно с номерами удобнее.