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