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

Вторым этапом преобразования на входе является растягивание по времени, во время которого к плану на всем его протяжении добавляются небольшие объемы времени простоя. Этот этап также увеличивает время завершения не более чем на <math>1 + O (\epsilon) \;</math>, однако он полезен для лучшей организации процесса планирования. В частности, если задание слишком велико (т. е. занимает большую часть интервала, в котором оно выполняется), его можно переместить во время простоя более позднего интервала, в котором оно будет занимать небольшую часть времени. Это гарантирует, что большинство заданий будут иметь небольшой размер по сравнению с продолжительностью интервала, в котором они выполняются, что значительно упрощает составление плана. Следующим этапом будет перемещение заданий. Рассмотрим разбиение временного интервала <math>[ 0, \infty ) \;</math> на интервалы формы <math>I_x = [(1 + \epsilon)^x,(l + \epsilon)^{x + 1}) \;</math> для целочисленных значений x. Этап перемещения заданий гарантирует, что существует почти субоптимальный план, в котором каждое задание j выполняется в пределах <math>O(log_{1 + \epsilon} (1 + \frac{1}{\epsilon})) \;</math> интервалов после rj. Он имеет следующее интересное свойство: если мы рассмотрим блоки интервалов B0, B1, ..., где каждый блок Bi содержит O(log1+ \epsilon (l + i)) последовательных интервалов, то задание j, начинающееся в блоке Bi, завершается в пределах следующего блока. Последующие этапы на фазе перемещения заданий гарантируют, что останется не слишком много больших заданий, распространяющихся на следующий блок; это обеспечивает эффективное осуществление динамического программирования.