Hardprob/Minimum Flow-Shop Scheduling - История изменений

StasFomin: Массовая правка: замена PCRE (\w)\s∈\s(\w) на \1 ∈ \2

2023-04-17T22:05:30Z

Массовая правка: замена PCRE <m>(\w)\s*∈\s*(\w)</m> на \1 ∈ \2

StasFomin: Массовая правка: замена PCRE \\le\s на ≤

2023-04-17T21:28:10Z

Массовая правка: замена PCRE \\le\s на ≤

StasFomin: Массовая правка: замена \leq на ≤

2023-04-17T21:26:13Z

Массовая правка: замена \leq на ≤

StasFomin: Массовая правка: замена \in на ∈

2023-04-17T18:00:53Z

Массовая правка: замена \in на ∈

StasFomin: Массовая правка: замена \ge на ≥

2023-04-17T11:30:19Z

Массовая правка: замена \ge на ≥

StasFomin: Новая страница: « * m\in Z^+ процессоров, множество J работ, каждый…»

2023-04-12T21:36:50Z

Новая страница: « * <m>m\in Z^+</m> процессоров, множество <m>J</m> работ, каждый…»

Новая страница

* <m>m\in Z^+</m> процессоров, множество <m>J</m> работ, каждый <m>j\in J</m> состоит
** m операций <m>o_{i,j}, 1 \leq i \leq m</m> (<m>o_{i,j}</m> должна выполняться на процессоре i)
** для каждой такой операции есть длительность <m>l_{i,j}\in N</m>.
* Найти «[https://en.wikipedia.org/wiki/Open-shop_scheduling расписание работы цеха]» для J (см. [[Hardprob/Minimum_Open-Shop_Scheduling]]), такая что, для каждого <m>j\in J</m>, и <m>1\le i<m</m>, <m>f_{i+1}(j)\ge f_i(j)+l_{i,j}</m>.

* Минимизировать время выполнения расписания, т.е.
<m>\max\limits_{j\in J} f_m(j)+l_{m,j} → \min</m>

----
{{hard-problem-on-lab17|{{PAGENAME}}}}




----

{{ViggoCode|node191}}
{{GDCode|SS15}}




[[Категория:ClassicHardProblems]]

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* <m>m∈  Z^+</m> процессоров, множество <m>J</m> работ, каждый <m>j∈  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>)
 ** для каждой такой операции есть длительность <m>l_{i,j}∈  N</m>.
-* Найти «[https://en.wikipedia.org/wiki/Open-shop_scheduling расписание работы цеха]» для <em>J</em> (см. [[Hardprob/Minimum_Open-Shop_Scheduling]]), такая что, для каждого <m>j∈  J</m>, и <m>1≤i<m</m>, <m>f_{i+1}(j)≥  f_i(j)+l_{i,j}</m>.
+* Найти «[https://en.wikipedia.org/wiki/Open-shop_scheduling расписание работы цеха]» для <em>J</em> (см. [[Hardprob/Minimum_Open-Shop_Scheduling]]), такая что, для каждого <em>j ∈ J</em>, и <m>1≤i<m</m>, <m>f_{i+1}(j)≥  f_i(j)+l_{i,j}</m>.
 * Минимизировать время выполнения расписания, т.е.

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

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * <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 ≤ i ≤ m</m> (<m>o_{i,j}</m> должна выполняться на процессоре <em>i</em>)
 ** для каждой такой операции есть длительность <m>l_{i,j}∈  N</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>.

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* <m>m\in Z^+</m> процессоров, множество <m>J</m> работ, каждый <m>j\in J</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>)
-** для каждой такой операции есть длительность <m>l_{i,j}\in N</m>.
+** для каждой такой операции есть длительность <m>l_{i,j}∈  N</m>.
-* Найти «[https://en.wikipedia.org/wiki/Open-shop_scheduling расписание работы цеха]» для <em>J</em> (см. [[Hardprob/Minimum_Open-Shop_Scheduling]]), такая что, для каждого <m>j\in J</m>, и <m>1\le i<m</m>, <m>f_{i+1}(j)≥  f_i(j)+l_{i,j}</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_{j\in J} f_m(j)+l_{m,j} → \min</m>
+  <m>\max\limits_{j∈  J} f_m(j)+l_{m,j} → \min</m>

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