Hardprob/Minimum Preemptive Scheduling With Set-Up Times — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w)_(\w)</m> на <em>\1<sub>\2</sub></em>) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \ldots на …) |
||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
* Набор компиляторов <em>C</em>, набор задач <em>T</em>, <em>m</em> процессоров, длительности задач <m>l(t)∈ Z^+</m>, нужный для задачи компилятор <m>c(t)∈ C</m>, время запуска-настройки для каждого компилятора <m>s(c)∈ Z^+</m>. | * Набор компиляторов <em>C</em>, набор задач <em>T</em>, <em>m</em> процессоров, длительности задач <m>l(t)∈ Z^+</m>, нужный для задачи компилятор <m>c(t)∈ C</m>, время запуска-настройки для каждого компилятора <m>s(c)∈ Z^+</m>. | ||
| − | * Найти <em>m</em>-процессорное [https://ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%82%D0%B5%D1%81%D0%BD%D1%8F%D1%8E%D1%89%D0%B0%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%BD%D0%BE%D1%81%D1%82%D1%8C вытесняющее расписание] <em>T</em>, т.е. для каждой для каждой задачи <em>t ∈ T</em>, разбиение <em>t</em> на какое-то количество подзадач <m>t_1, | + | * Найти <em>m</em>-процессорное [https://ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%82%D0%B5%D1%81%D0%BD%D1%8F%D1%8E%D1%89%D0%B0%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%BD%D0%BE%D1%81%D1%82%D1%8C вытесняющее расписание] <em>T</em>, т.е. для каждой для каждой задачи <em>t ∈ T</em>, разбиение <em>t</em> на какое-то количество подзадач <m>t_1, …, t_k</m>, такое что |
** <m>\sum_{i=1}^k l(t_i) = l(t)</m> | ** <m>\sum_{i=1}^k l(t_i) = l(t)</m> | ||
** и есть некоторое назначение <m>σ = (σ_1, σ_2)</m>, которое назначает каждой подзадаче <em>t<sub>i</sub></em> пару неотрицательных целых <m>(σ_1(t_i), σ_2(t_i))</m>, таких, что | ** и есть некоторое назначение <m>σ = (σ_1, σ_2)</m>, которое назначает каждой подзадаче <em>t<sub>i</sub></em> пару неотрицательных целых <m>(σ_1(t_i), σ_2(t_i))</m>, таких, что | ||
Версия 22:45, 17 апреля 2023
- Набор компиляторов C, набор задач T, m процессоров, длительности задач , нужный для задачи компилятор , время запуска-настройки для каждого компилятора .
- Найти m-процессорное вытесняющее расписание T, т.е. для каждой для каждой задачи t ∈ T, разбиение t на какое-то количество подзадач , такое что
- и есть некоторое назначение , которое назначает каждой подзадаче ti пару неотрицательных целых , таких, что
- Это расписание должно удовлетворять дополнительному ограничению:
- Если два подзадачи ti от t и от t', у которых запланированы последовательно на одном процессоре (т.е. , и нет другой подзадачи , у которой и , то
- — если у них один и тот же компилятор (c(t) = c(t'))
- — если эти компиляторы разные.
- Если два подзадачи ti от t и от t', у которых запланированы последовательно на одном процессоре (т.е. , и нет другой подзадачи , у которой и , то
- Минимизировать общее время выполнения, т.е. максимум по всем подзадачам
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SS6, SS12»