Hardprob/Minimum Preemptive Scheduling With Set-Up Times — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена <m>t\in T</m> на <em>t ∈ T</em>) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \ge на ≥) |
||
| Строка 5: | Строка 5: | ||
** и есть некоторое назначение <m>\sigma = (\sigma_1, \sigma_2)</m>, которое назначает каждой подзадаче <m>t_i</m> пару неотрицательных целых <m>(\sigma_1(t_i), \sigma_2(t_i))</m>, таких, что | ** и есть некоторое назначение <m>\sigma = (\sigma_1, \sigma_2)</m>, которое назначает каждой подзадаче <m>t_i</m> пару неотрицательных целых <m>(\sigma_1(t_i), \sigma_2(t_i))</m>, таких, что | ||
*** <m>1 \le \sigma_1(t_i) \le m</m> | *** <m>1 \le \sigma_1(t_i) \le m</m> | ||
| − | *** <m>\sigma_2(t_{i+1}) | + | *** <m>\sigma_2(t_{i+1}) ≥ \sigma_2(t_i) + l(t_i), \ \ 1 \le i < k</m> |
** Это расписание должно удовлетворять дополнительному ограничению: | ** Это расписание должно удовлетворять дополнительному ограничению: | ||
*** Если два подзадачи <m>t_i</m> от <em>t</em> и <m>t_j'</m> от <em>t'</em>, у которых <m>\sigma_2(t_i) < \sigma_2(t_j')</m> запланированы последовательно на одном процессоре (т.е. <m>\sigma_1(t_i) = \sigma_1(t_j')</m>, и нет другой подзадачи <m>t_k"</m>, у которой <m>\sigma_1(t_k") = \sigma_1(t_i)</m> и <m>\sigma_2(t_i) < \sigma_2(t_k") < \sigma_2(t_j')</m>, то | *** Если два подзадачи <m>t_i</m> от <em>t</em> и <m>t_j'</m> от <em>t'</em>, у которых <m>\sigma_2(t_i) < \sigma_2(t_j')</m> запланированы последовательно на одном процессоре (т.е. <m>\sigma_1(t_i) = \sigma_1(t_j')</m>, и нет другой подзадачи <m>t_k"</m>, у которой <m>\sigma_1(t_k") = \sigma_1(t_i)</m> и <m>\sigma_2(t_i) < \sigma_2(t_k") < \sigma_2(t_j')</m>, то | ||
| − | **** <m>\sigma_2(t_j') | + | **** <m>\sigma_2(t_j') ≥ \sigma_2(t_i) + l(t_i) + s(c(t'))</m> — если у них один и тот же компилятор (<em>c(t) = c(t')</em>) |
| − | **** <m>\sigma_2(t_j') | + | **** <m>\sigma_2(t_j') ≥ \sigma_2(t_i) + l(t_i) + s(c(t'))</m> — если эти компиляторы разные. |
* Минимизировать общее время выполнения, т.е. максимум по всем подзадачам <m>\sigma_2(t_i)+l(t_i)</m> | * Минимизировать общее время выполнения, т.е. максимум по всем подзадачам <m>\sigma_2(t_i)+l(t_i)</m> | ||
Версия 11:30, 17 апреля 2023
- Набор компиляторов C, набор задач T, m процессоров, длительности задач , нужный для задачи компилятор , время запуска-настройки для каждого компилятора .
- Найти m-процессорное вытесняющее расписание T, т.е. для каждой для каждой задачи t ∈ T, разбиение t на какое-то количество подзадач , такое что
- и есть некоторое назначение , которое назначает каждой подзадаче пару неотрицательных целых , таких, что
- Это расписание должно удовлетворять дополнительному ограничению:
- Если два подзадачи от t и от t', у которых запланированы последовательно на одном процессоре (т.е. , и нет другой подзадачи , у которой и , то
- — если у них один и тот же компилятор (c(t) = c(t'))
- — если эти компиляторы разные.
- Если два подзадачи от t и от t', у которых запланированы последовательно на одном процессоре (т.е. , и нет другой подзадачи , у которой и , то
- Минимизировать общее время выполнения, т.е. максимум по всем подзадачам
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SS6, SS12»