Hardprob/Minimum Preemptive Scheduling With Set-Up Times
Материал из DISCOPAL
Версия от 16:34, 12 апреля 2023; StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор компиляторов <em>C</em>, набор задач <em>T</em>, <em>m</em>…»)
- Набор компиляторов C, набор задач T, m процессоров, длительности задач , нужный для задачи компилятор , время запуска-настройки для каждого компилятора .
- Найти m-процессорное вытесняюще расписание T, т.е. для каждой для каждой задачи , разбиение t на какое-то количество подзадач , такое что
- и есть некоторое назначение , которое назначает каждой подзадаче пару неотрицательных целых , таких, что
- Это расписание должно удовлетворять дополнительному ограничению:
- Если два подзадачи от t и от t', у которых запланированы последовательно на одном процессоре (т.е. , и нет другой подзадачи , у которой и , то
- — если у них один и тот же компилятор (c(t) = c(t'))
- — если эти компиляторы разные.
- Если два подзадачи от t и от t', у которых запланированы последовательно на одном процессоре (т.е. , и нет другой подзадачи , у которой и , то
- Минимизировать общее время выполнения, т.е. максимум по всем подзадачам
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SS6, SS12»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.