Изменения
Нет описания правки
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.
}}
==Алгоритм== ===Описание алгоритма===
{{Утверждение
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.
|proof=
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i)+1, \ldots, t(i)+k</tex>, где <tex>k<m</tex>, но не делалась в момент времени <tex>t(i)+k+1</tex>. Докажем, что в момент времени <tex>t(i)+k+1</tex>, <tex>k+1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу.
Пусть в момент времени <tex>t(i)+k+1</tex> на <tex>k+1</tex>-м станке делается работа <tex>j</tex>. В <tex>t(i)+k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i)+k+1</tex>-й момент <tex>k+1</tex>-й станок свободен и туда можно поставить <tex>i</tex>-ю работу, устранив разрыв.
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.
}}
В [[Flow shop|flow shop]] показано как можно получить оптимальное расписание сведя задачу <tex> 1 \mid p_{ij} = 1 \mid ? </tex> к <tex>F \mid p_{ij} = 1 \mid ?</tex> , теперь рассмотрим как <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex> сводится к <tex> 1 \mid p_{ij} = 1 \mid w_iu_i</tex>. По этому утверждению, если работу <tex>i</tex> начали делать в <tex>t(i)</tex>, то закончена она будет в <tex>t(i)+m</tex>. Найдем время <tex>d'_i</tex> такое, что начав выполнять в него работу <tex>i</tex>, мы успеем выполнить ее до <tex>d_i</tex>: <tex>d'_i = d_i - m</tex>. Таким образом, вычтя из всех <tex>d_i</tex> число <tex>m</tex>, мы свели задачу к <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>.
Построив оптимальное расписание для <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>, мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.
===Сложность алгоритма===Задача <tex>F \mid p_{iji j} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к [[1pi1sumwu|задаче <tex>1 \mid p_i = 1 \mid \sum w_iu_iw_i u_i</tex>]]. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Значит, итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>.
==См. также.==
==Источники информации==
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.
* Vladimír Modrák, R. Sudhakara Pandian. FLOW SHOP SCHEDULING ALGORITHM TO MINIMIZE COMPLETION TIME FOR -JOBS -MACHINES PROBLEM
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
