Hardprob/Minimum Two-Processor Flow Shop Scheduling With Batch Set-Up Times — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \ge на ≥) |
||
Строка 6: | Строка 6: | ||
** каждый компилятор <em>c∈C</em> имеет пару времен прогрева-настройки <m>s_i(c)\in Z^+</m> | ** каждый компилятор <em>c∈C</em> имеет пару времен прогрева-настройки <m>s_i(c)\in 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') | + | такой, что для если две операции <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>. |
* Минимизировать время выполнения расписания, т.е. | * Минимизировать время выполнения расписания, т.е. |
Версия 11:30, 17 апреля 2023
- Набор компиляторов C, набор работ J, каждая работа ,
- требует определенного компилятора ,
- состоит из двух операций , i=1,2, каждая из которых
- имеет длину
- каждый компилятор c∈C имеет пару времен прогрева-настройки
- Найти двухпроцессорное расписание поточной линии для J (см. Hardprob/Minimum Flow-Shop Scheduling),
такой, что для если две операции и , с распланированы последовательно (т.е. нет другой операции , для которой ), и требуют разных компиляторов (т.е. ), то .
- Минимизировать время выполнения расписания, т.е.
.
Задача в лаб22 (рид-онли просмотр)