Hardprob/Minimum Open-Shop Scheduling — различия между версиями

Версия 11:34, 17 апреля 2023

процессоров, множество работ, каждый состоит
- m операций ( должна выполняться на процессоре i)
- для каждой такой операции есть длительность .
Найти «расписание работы цеха» для J, т.е. коллекцию однопроцессных расписаний ,
- таких, что из следует , т.е. для каждого , интервалы не пересекаются.
Минимизировать время выполнения расписания, т.е.

@@ Строка 3: / Строка 3: @@
 ** <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}\in N</m>.
-* Найти «[https://en.wikipedia.org/wiki/Open-shop_scheduling расписание работы цеха]» для <em>J</em>, т.е. коллекцию однопроцессных расписаний <m>f_i: J\rightarrow N,  \ \ 1\le i\le m</m>,
+* Найти «[https://en.wikipedia.org/wiki/Open-shop_scheduling расписание работы цеха]» для <em>J</em>, т.е. коллекцию однопроцессных расписаний <m>f_i: J→  N,  \ \ 1\le i\le m</m>,
 ** таких, что из <m>f_i(j) > f_i(j')</m> следует <m>f_i(j) ≥  f_i(j') + l_{i,j'}</m>, т.е. для каждого <m>j\in J</m>, интервалы <m>[f_i(j),f_i(j)+l_{i,j})</m> не пересекаются.
 * Минимизировать время выполнения расписания, т.е.