Маршрутизация пакетов: различия между версиями

Рассмотрим задачу планирования для заданий j1, ..., jr и машин m1, ..., ms, в которой каждое задание должно выполняться на заданной последовательности машин (в заданном порядке). Предположим, что каждое задание тратит единицу времени на каждой машине и что ни одна машина не должна выполнять какое-либо задание более одного раза (на языке составления расписаний имеет место ациклическая задача планирования с единичными заданиями без вытеснения). Существует отображение последовательностей машин на пути и заданий на пакеты, представляющее собой иную формулировку основной задачи маршрутизации пакетов, в которой c теперь обозначает максимальное количество заданий, которые должны выполняться на любой отдельной машине, а d – максимальное количество различных машин, выполняющих любое отдельное задание; для соответствующего экземпляра задачи маршрутизации пакетов O(c) теперь обозначает нагруженность, а O(d) – протяженность. Оффлайновый результат LMR показывает, что существует план, при котором все задания выполняются за O(c + d) шагов и, кроме того, время ожидания между последовательными машинами для каждого задания составляет не более константного количества шагов (к тому же размер очереди заданий, ожидающих некоторую конкретную машину, всегда будет ограничен константой). Техники, аналогичные использованным в статье о LMR, были впоследствии применены к более общим задачам планирования набора заданий; см. работы [4, 11].

В контексте задачи планирования набора заданий неизвестно, можно ли улучшить алгоритм аппроксимации с константным коэффициентом для ациклической задачи планирования набора заданий с единичной длиной без вытеснения, подразумеваемой LMR, до PTAS. Неизвестно также, существует ли алгоритм аппроксимации с константным коэффициентом для заданий произвольной длины.