Hardprob/Minimum Flow-Shop Scheduling — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена \ge на ≥) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \in на ∈) |
||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * <m> | + | * <m>m∈ Z^+</m> процессоров, множество <m>J</m> работ, каждый <m>j∈ J</m> состоит |
** <em>m</em> операций <m>o_{i,j}, 1 \leq i \leq m</m> (<m>o_{i,j}</m> должна выполняться на процессоре <em>i</em>) | ** <em>m</em> операций <m>o_{i,j}, 1 \leq i \leq m</m> (<m>o_{i,j}</m> должна выполняться на процессоре <em>i</em>) | ||
| − | ** для каждой такой операции есть длительность <m>l_{i,j} | + | ** для каждой такой операции есть длительность <m>l_{i,j}∈ N</m>. |
| − | * Найти «[https://en.wikipedia.org/wiki/Open-shop_scheduling расписание работы цеха]» для <em>J</em> (см. [[Hardprob/Minimum_Open-Shop_Scheduling]]), такая что, для каждого <m> | + | * Найти «[https://en.wikipedia.org/wiki/Open-shop_scheduling расписание работы цеха]» для <em>J</em> (см. [[Hardprob/Minimum_Open-Shop_Scheduling]]), такая что, для каждого <m>j∈ J</m>, и <m>1\le i<m</m>, <m>f_{i+1}(j)≥ f_i(j)+l_{i,j}</m>. |
* Минимизировать время выполнения расписания, т.е. | * Минимизировать время выполнения расписания, т.е. | ||
| − | <m>\max\limits_{ | + | <m>\max\limits_{j∈ J} f_m(j)+l_{m,j} → \min</m> |
Версия 18:00, 17 апреля 2023
- процессоров, множество работ, каждый состоит
- m операций ( должна выполняться на процессоре i)
- для каждой такой операции есть длительность .
- Найти «расписание работы цеха» для J (см. Hardprob/Minimum_Open-Shop_Scheduling), такая что, для каждого , и , .
- Минимизировать время выполнения расписания, т.е.
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SS15»