Hardprob/Minimum Preemptive Scheduling With Set-Up Times — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w)_(\w),\s*…\s*,\s*(\w)_(\w)<\/m> на <em>\1<sub>\2</sub>, …, \3<sub>\4</sub></em>) |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 7: | Строка 7: | ||
*** <m>σ_2(t_{i+1}) ≥ σ_2(t_i) + l(t_i), \ \ 1 ≤i < k</m> | *** <m>σ_2(t_{i+1}) ≥ σ_2(t_i) + l(t_i), \ \ 1 ≤i < k</m> | ||
** Это расписание должно удовлетворять дополнительному ограничению: | ** Это расписание должно удовлетворять дополнительному ограничению: | ||
| − | *** Если два подзадачи <em>t<sub>i</sub></em> от <em>t</em> и < | + | *** Если два подзадачи <em>t<sub>i</sub></em> от <em>t</em> и <em>t<sub>j</sub>'</em> от <em>t'</em>, у которых <m>σ_2(t_i) < σ_2(t_j')</m> запланированы последовательно на одном процессоре (т.е. <m>σ_1(t_i) = σ_1(t_j')</m>, и нет другой подзадачи <m>t_k"</m>, у которой <m>σ_1(t_k") = σ_1(t_i)</m> и <m>σ_2(t_i) < σ_2(t_k") < σ_2(t_j')</m>, то |
**** <m>σ_2(t_j') ≥ σ_2(t_i) + l(t_i) + s(c(t'))</m> — если у них один и тот же компилятор (<em>c(t) = c(t')</em>) | **** <m>σ_2(t_j') ≥ σ_2(t_i) + l(t_i) + s(c(t'))</m> — если у них один и тот же компилятор (<em>c(t) = c(t')</em>) | ||
**** <m>σ_2(t_j') ≥ σ_2(t_i) + l(t_i) + s(c(t'))</m> — если эти компиляторы разные. | **** <m>σ_2(t_j') ≥ σ_2(t_i) + l(t_i) + s(c(t'))</m> — если эти компиляторы разные. | ||
| Строка 22: | Строка 22: | ||
{{ViggoCode|node184}} | {{ViggoCode|node184}} | ||
| − | {{GDCode|SS6 | + | {{GDCode|SS6}} |
| + | {{GDCode|SS12}} | ||
<!-- * [ Задача в википедии] --> | <!-- * [ Задача в википедии] --> | ||
</small> | </small> | ||
Текущая версия на 16:58, 20 апреля 2023
- Набор компиляторов C, набор задач T, m процессоров, длительности задач , нужный для задачи компилятор , время запуска-настройки для каждого компилятора .
- Найти m-процессорное вытесняющее расписание T, т.е. для каждой для каждой задачи t ∈ T, разбиение t на какое-то количество подзадач t1, …, tk, такое что
- и есть некоторое назначение , которое назначает каждой подзадаче ti пару неотрицательных целых , таких, что
- Это расписание должно удовлетворять дополнительному ограничению:
- Если два подзадачи ti от t и tj' от t', у которых запланированы последовательно на одном процессоре (т.е. , и нет другой подзадачи , у которой и , то
- — если у них один и тот же компилятор (c(t) = c(t'))
- — если эти компиляторы разные.
- Если два подзадачи ti от t и tj' от t', у которых запланированы последовательно на одном процессоре (т.е. , и нет другой подзадачи , у которой и , то
- Минимизировать общее время выполнения, т.е. максимум по всем подзадачам
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SS6»
- Код задачи в книге «ГД» → «SS12»