4501
правка
Минимальное время завершения для взвешенной системы: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальное время завершения для взвешенной системы (посмотреть исходный код)
Версия от 22:05, 19 сентября 2016
, 19 сентября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
Задача Время выполнения схем PTAS | Задача Время выполнения схем PTAS | ||
Mn\T,wjq 0(2Р°М?)п+п|одп) | Mn\T,wjq 0(2Р°М?)п+п|одп) | ||
PjrjjPwjCj O((m + 1 У0'* е >n + n log n) | PjrjjPwjCj O((m + 1 У0'* е >n + n log n) | ||
| Строка 31: | Строка 32: | ||
Таблица 1. Основные результаты Афрати и др. [ ] | Таблица 1. Основные результаты Афрати и др. [ ] | ||
Вторым этапом преобразования на входе является растягивание по времени, во время которого к плану на всем его протяжении добавляются небольшие объемы времени простоя. Этот этап также увеличивает время завершения не более чем на 1 + O(e), однако он полезен для лучшей организации процесса планирования. В частности, если задание слишком велико (т.е. занимает большую часть интервала, в котором оно выполняется), его можно переместить во время простоя более позднего интервала, в котором оно будет занимать небольшую часть времени. Это гарантирует, что большинство заданий будут иметь небольшой размер по сравнению с продолжительностью интервала, в котором они выполняются, что значительно упрощает составление плана. Следующим этапом будет перемещение заданий. Рассмотрим разбиение временного интервала [0, 1) на интервалы формы Ix = [(1 + e)x,(l + e)x+1) для целочисленных значений x. Этап перемещения заданий гарантирует, что существует практически субоптимальный план, в котором каждое задание j выполняется в пределах O(log1+e(l + j-)) интервалов после rj. Он имеет следующее интересное свойство: если мы рассмотрим блоки интервалов B0, B1, ..., где каждый блок Bi содержит O(log1+e(l + i)) последовательных интервалов, то задание j, начинающееся в блоке Bi, завершается в пределах следующего блока. Последующие этапы на фазе перемещения заданий гарантируют, что останется не слишком много больших заданий, распространяющихся на следующий блок; это обеспечивает эффективное осуществление динамического программирования. | |||
Точное содержание этапов алгоритмов и их анализ довольно сложны; здесь приводится только их упрощенное схематическое представление. Подробнее об этом – в [1] и [3]. | |||
== Применение == | |||