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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * <m>m\in Z^+</m> процессоров, множество <m>J</m> работ, каждый…»)
 
(Массовая правка: замена \ge на ≥)
Строка 3: Строка 3:
 
** <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}\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>.
  
 
* Минимизировать время выполнения расписания, т.е.
 
* Минимизировать время выполнения расписания, т.е.

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

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


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

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