Минимальное время завершения для взвешенной системы: различия между версиями

Афрати и др. [1] первыми разработали PTAS-алгоритмы для задач поиска минимального времени завершения для взвешенной системы с указанием дат запуска. В таблице 1 приведено время выполнения этих PTAS-алгоритмов.

Первым этапом преобразования на входе является геометрическое округление, при помощи которого длительность обработки и дата запуска преобразуются в степени значения <math>1 + \epsilon \;</math>, в результате чего общая эффективность снижается не более чем на <math>1 + \epsilon \;</math>. Что еще более важно, этот этап: (1) гарантирует небольшое количество различных значений длительности обработки и даты запуска; (2) позволяет разбивать время на геометрически возрастающие интервалы; и (3) выравнивает даты запуска относительно временных границ начала и конца интервалов. Все этим полезные свойства могут использоваться алгоритмом динамического программирования.

Вторым этапом преобразования на входе является растягивание по времени, во время которого к плану на всем его протяжении добавляются небольшие объемы времени простоя. Этот этап также увеличивает время завершения не более чем на <math>1 + O (\epsilon) \;</math>, однако он полезен для лучшей организации процесса планирования. В частности, если задание слишком велико (т.е. занимает большую часть интервала, в котором оно выполняется), его можно переместить во время простоя более позднего интервала, в котором оно будет занимать небольшую часть времени. Это гарантирует, что большинство заданий будут иметь небольшой размер по сравнению с продолжительностью интервала, в котором они выполняются, что значительно упрощает составление плана. Следующим этапом будет перемещение заданий. Рассмотрим разбиение временного интервала [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, завершается в пределах следующего блока. Последующие этапы на фазе перемещения заданий гарантируют, что останется не слишком много больших заданий, распространяющихся на следующий блок; это обеспечивает эффективное осуществление динамического программирования.