Hardprob/Minimum Two-Processor Flow Shop Scheduling With Batch Set-Up Times — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена \ge на ≥) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \in на ∈) |
||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * Набор компиляторов <em>C</em>, набор работ <em>J</em>, каждая работа <m>∀j | + | * Набор компиляторов <em>C</em>, набор работ <em>J</em>, каждая работа <m>∀j ∈ J</m>, |
| − | ** требует определенного компилятора <m>k(j) | + | ** требует определенного компилятора <m>k(j) ∈ C</m>, |
** состоит из двух операций <m>o_{i,j}</m>, <em>i=1,2</em>, каждая из которых | ** состоит из двух операций <m>o_{i,j}</m>, <em>i=1,2</em>, каждая из которых | ||
| − | *** имеет длину <m>l_{i,j} | + | *** имеет длину <m>l_{i,j}∈ N</m> |
| − | ** каждый компилятор <em>c∈C</em> имеет пару времен прогрева-настройки <m>s_i(c) | + | ** каждый компилятор <em>c∈C</em> имеет пару времен прогрева-настройки <m>s_i(c)∈ Z^+</m> |
* Найти [https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BF%D0%BB%D0%B0%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D0%B9_%D0%BB%D0%B8%D0%BD%D0%B8%D0%B8 двухпроцессорное расписание поточной линии] для <em>J</em> (см. [[Hardprob/Minimum Flow-Shop Scheduling]]), | * Найти [https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BF%D0%BB%D0%B0%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D0%B9_%D0%BB%D0%B8%D0%BD%D0%B8%D0%B8 двухпроцессорное расписание поточной линии] для <em>J</em> (см. [[Hardprob/Minimum Flow-Shop Scheduling]]), | ||
такой, что для если две операции <m>o_{i,j}</m> и <m>o_{i,j'}</m>, с <m>f_i(j) < f_i(j')</m> распланированы последовательно (т.е. нет другой операции <m>o_{i,j"}</m>, для которой <m>f_i(j) < f_i(j") < f_i(j')</m>), и требуют разных компиляторов (т.е. <m>k(j)\neq k(j')</m>), то <m>f_i(j') ≥ f_i(j) + l_{i,j} + s_i(k(j'))</m>. | такой, что для если две операции <m>o_{i,j}</m> и <m>o_{i,j'}</m>, с <m>f_i(j) < f_i(j')</m> распланированы последовательно (т.е. нет другой операции <m>o_{i,j"}</m>, для которой <m>f_i(j) < f_i(j") < f_i(j')</m>), и требуют разных компиляторов (т.е. <m>k(j)\neq k(j')</m>), то <m>f_i(j') ≥ f_i(j) + l_{i,j} + s_i(k(j'))</m>. | ||
* Минимизировать время выполнения расписания, т.е. | * Минимизировать время выполнения расписания, т.е. | ||
| − | <m>\max\limits_{ | + | <m>\max\limits_{j∈ J} f_2(j)+l_{2,j} → \min</m>. |
---- | ---- | ||
Текущая версия на 18:01, 17 апреля 2023
- Набор компиляторов C, набор работ J, каждая работа ,
- требует определенного компилятора ,
- состоит из двух операций , i=1,2, каждая из которых
- имеет длину
- каждый компилятор c∈C имеет пару времен прогрева-настройки
- Найти двухпроцессорное расписание поточной линии для J (см. Hardprob/Minimum Flow-Shop Scheduling),
такой, что для если две операции и , с распланированы последовательно (т.е. нет другой операции , для которой ), и требуют разных компиляторов (т.е. ), то .
- Минимизировать время выполнения расписания, т.е.
.
Задача в лаб22 (рид-онли просмотр)