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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена \rightarrow на →)
(Массовая правка: замена \in на ∈)
Строка 1: Строка 1:
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 
<!-- 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>)
 
** <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>, т.е. коллекцию однопроцессных расписаний <m>f_i: J→  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> не пересекаются.
+
** таких, что из <m>f_i(j) > f_i(j')</m> следует <m>f_i(j) ≥  f_i(j') + l_{i,j'}</m>, т.е. для каждого <m>j∈  J</m>, интервалы <m>[f_i(j),f_i(j)+l_{i,j})</m> не пересекаются.
 
* Минимизировать время выполнения расписания, т.е.
 
* Минимизировать время выполнения расписания, т.е.
−
  <m>\max\limits_{1\le i\le m, j\in J} f_i(j)+l_{i,j} → \min</m>
+
  <m>\max\limits_{1\le i\le m, j∈  J} f_i(j)+l_{i,j} → \min</m>
  
 
----
 
----

Версия 18:01, 17 апреля 2023

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

Задача в лаб22 (рид-онли просмотр)

Источник — «https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Open-Shop_Scheduling&oldid=25020»