Задача об оптимальном планировании работы

Задача об оптимальном планировании работы (англ. Optimal job scheduling) — сильно NP-трудная задача комбинаторной оптимизации, заключающаяся в составлении расписаний. Входными данными задачи является список из $n$ задач и их продолжительностей $p_{i}\in \mathbb {N}$ и количество машин $m$, на которых эти задачи могут выполняться. В зависимости от вариации проблемы могут быть добавлены дополнительные ограничения на скорость выполнения машинами задач. В результате алгоритм должен найти такое распределение задач по машинам, что задачи будут выполнены за минимально возможное время. Задачи не предусматривают наличие дедлайнов, поэтому последовательность их обработки может быть любой. NP-полнота задачи доказывается через редукцию к задаче о сумме подмножеств, так как она является частным случаем задачи об оптимальном планировании работы для количества машин $m=2$.

Варианты задачи

Идентичные машины

Классический вариант задачи об оптимальном планировании, принимающий на вход количество машин $m$, количество задач $n$ и целочисленную продолжительность каждой задачи $p_{i}\in \mathbb {N}$. Необходимо найти такое отображение $f\colon {\underline {n}}\to {\underline {m}}$, что $\max _{j\in {\underline {m}}}\sum _{i\in {\underline {n}}\land f(i)=j}p_{i}$ минимально. Настоящий вариант задачи имеет приближенную схему полиномиального времени.

Методы решения

Least Loaded

Эвристика Least Loaded по очереди присваивает все задачи машинам, имеющим наименьшую нагрузку. Очевидно, что оптимальность такого варианта решения проблемы зависит от порядка задач в поданном на вход списке.

1. Выбери машину, имеющую наименьшую нагрузку.
2. Для $k$ от $1$ до $n$:
   1. Выбери $j$ такое, что $\sum _{i\in {\underline {k-1}}\land f(i)=j}p_{i}$ минимально.
   2. Установи $f(k)=j$.

Фактор аппроксимации такой эвристики равен $2-{\frac {1}{m}}$. Перед доказательством определим границу продолжительности для оптимального решения ${\text{OPT}}\geqslant \max _{i\in {\underline {n}}}p_{i}\geqslant {\frac {1}{m}}\cdot \sum _{i\in {\underline {n}}}p_{i}$. Теперь рассмотрим задачу, которая будет выполнена последней и ситуацию, происходящую перед тем, как такая задача будет распределена. Пусть $i'$ — задача, которая будет выполнена последней, а $j'=f(i')$ — машина, которой такая задача будет присвоена. До того, как задача $i'$ была присвоена машине $j'$, нагрузка на машине была минимальной и составляла максимум ${\frac {1}{m}}\cdot \sum _{i\in {\underline {i'-1}}}p_{i}$. таким образом время работы машины $j'$ будет равно $p_{i'}+{\frac {1}{m}}\sum _{i\in {\underline {i'-1}}}p_{i}\leqslant (1-{\frac {1}{m}})\cdot {\text{OPT}}+{\text{OPT}}\leqslant (2-{\frac {1}{m}})\cdot {\text{OPT}}$.

Longest Processing Time

Данная эвристка уже не учитывает порядок задач на входе и располагает их, присваивая самой разгруженной машине самую продолжительную задачу:

1. Выбери для самой продолжительной работы машину, имеющую наименьшую нагрузку.
2. Пусть $p_{1}\geqslant p_{2}\geqslant \dots \geqslant p_{n}$.
3. Для $k$ от $1$ до $n$:
   1. Выбери $j$ такое, что $\sum _{i\in {\underline {k-1}}\land f(i)=j}p_{i}$ минимально.
   2. Установи $f(k)=j$.

Фактор аппроксимации эвристики равен $4/3$, что намного лучше, чем у прошлого метода, так как не зависит от входных данных. Доказательство происходит от противного: Пусть максимальное время работы $\tau$ некоторой машины на некоторых входных данных больше $4/3\cdot {\text{OPT}}$ и задача $n$ имеет минимальную продолжительность, а также $p_{1}\geqslant p_{2}\geqslant \dots \geqslant p_{n}$. Так как $n$ имеет минимальное время выполнения, $n$ — задача, которая будет выполнена последней и будет распределена машине, имеющей наименьшую нагрузку. К этому моменту нагрузка машины равна максимум ${\frac {1}{m}}\cdot \sum _{i=1}^{n-1}p_{i}\leqslant {\text{OPT}}$. Для того, чтобы коэффициент $\tau$ имел значение $4/3$, $p_{n}$ должен быть строго больше $1/3\cdot {\text{OPT}}$. Так как задачи отсортированы, для любой задачи справедливо $p_{i}>{\frac {1}{3}}\cdot {\text{OPT}}$, а значит, каждая машина может обработать не более двух задач и количество задач $n\leqslant 2\cdot m$. Однако при этом оптимальным решением будет распределить задачи с номерами $i\leqslant m$ машинам с номерами $i$, а задачи с номерами $i>m$ машинам с номерами $2\cdot m-i+1$, что и является распределением согласно эвристике Longest Processing Time. Противоречие.

PTAS Алгоритм

Идея алгоритма заключается в скалировании и округлении вверх продолжительности «долгих» задач, что приводит к появлению некоторой погрешности и уменьшению временной сложности.

1. Оракул приводит значение $Z$ — максимальной оптимальной загруженности машин.
2. Фаза 1:
   1. Рассматриваются «долгие задачи» $G=\{i\in {\underline {n}}\mid p_{i}>\varepsilon Z\}$.
   2. Масштабируй продолжительность задач из $G$: $p_{i}'=\lceil {\frac {p_{i}}{\varepsilon ^{2}Z}}\rceil$.
   3. Определи планирование с продолжительностью задач $p_{i}'$ и максимальной загруженностью машин $Z'=\lfloor (1+\varepsilon ){\frac {1}{\varepsilon ^{2}}}\rfloor$
3. Фаза 2:
   1. Рассматриваются «короткие» задачи $K=\{i\in {\underline {n}}\mid p_{i}\leqslant \varepsilon Z\}$.
   2. Распредели задачи согласно эвристике Least Loaded.

Лемма. Относительная погрешность округления ${\frac {p_{i}'-p_{i}''}{p_{i}''}}$ не превосходит $\varepsilon$ для $p_{i}''={\frac {p_{i}}{\varepsilon Z}}$.

Доказательство. Пусть $i\in G$, то есть «большая» задача, а значит $p_{i}\geqslant \varepsilon Z$. Из этого следует, что $p_{i}''\geqslant {\frac {\varepsilon Z}{\varepsilon ^{2}Z}}={\frac {1}{\varepsilon }}$, а учитывая, что $p_{i}'-p_{i}''\leqslant 1$, получим ${\frac {p_{i}'-p_{i}''}{p_{i}''}}\leqslant {\frac {1}{1/\varepsilon }}=\varepsilon$. Доказательство леммы показывает, что при округлении скалированных «больших» задач, они изменяются с фактором не более $1+\varepsilon$.

Первая фаза заканчивается поиском планирования, учитывающего максимальную загруженность машин, что может быть решено методами динамического программирования, схожими с динамическим решением над ценностями предметов задачи о рюкзаке. Как следствие, временная сложность алгоритма с оракулом составляет $O(n^{\lceil 1/\varepsilon ^{2}\rceil })$, а фактор аппроксимации $1+\varepsilon$.

Однако оракул не может существовать. Иначе задача об оптимальном планировании имела бы эффективное решение. Тем не менее так как алгоритм аппроксимирует, нет нужды знать точное значение $Z$, поэтому его можно найти используя алгоритм бинарного поиска, начиная с верхнего порога продолжительности работы машины $S=\sum _{i=1}^{n}p_{i}$. Если длина входных данных в битах равна $N$, то $\log S\leqslant N$, а значит, общее время работы алгоритма равно $O(N\cdot n^{\lceil 1/\varepsilon ^{2}\rceil })$.

Машины с разными скоростями

Следующий вариант задачи принимает на вход число машин $m$, скорость каждой машины $s_{j}\in \mathbb {N}$, количество задач $n$ и продолжительность каждой задачи $p_{i}\in \mathbb {N}$. В отличие от предидущего варианта, необходимо найти такое отображение $f\colon {\underline {n}}\to {\underline {m}}$, что $\max _{j\in {\underline {m}}}\sum _{i\in {\underline {n}}\land f(i)=j}{\frac {p_{i}}{s_{j}}}$ минимально. Решение такого варианта задачи аналогично решению варианта с идентичными машинами.

Машины общего назначения

На вход подается количество задач $n$, количество машин $m$ и целочисленные продолжительности задач $p_{i,j}$, кодирующие продолжительность задачи $i\in {\underline {n}}$ на машине $j\in {\underline {m}}$. Найти требуется такое отображение $f\colon {\underline {n}}\to {\underline {m}}$, что $\max _{j\in {\underline {m}}}\sum _{i\in {\underline {n}}\land f(i)=j}p_{i,j}$ минимально.

Методы решения

Целочисленное линейное программирование

Задачу можно представить как систему уравнений, но так как продолжительности задач целочисленные, мы получим целочисленную линейную программу (ЦЛП) вида:

${\begin{aligned}\min &\;t\\s.t.&\sum _{j\in {\underline {m}}}x_{i,j}\geqslant 1,&\forall i\in {\underline {n}}\\&\sum _{i\in {\underline {n}}}x_{i,j}\cdot p_{i,j}\leqslant t,&\forall j\in {\underline {m}}\\&x_{i,j}\in \{0,1\},&\forall i\in {\underline {n}},\forall j\in {\underline {m}}\end{aligned}}$

Исходя из неравенства классов P и NP, ЦЛП не может быть решена за полиномиальное время. Если же убрать требование целочисленности, то решения при $n=1$ и $p_{1,j}=1$ будут приводить к максимальной загруженности машин $1/m$, что плохо с точки зрения аппроксимации.

Однако если изменить ЦЛП следующим образом:

${\begin{aligned}\min &\;0\\s.t.&\sum _{j\in {\underline {m}}}x_{i,j}\geqslant 1,&\forall i\in {\underline {n}}\\&\sum _{i\in {\underline {n}}}x_{i,j}\cdot p_{i,j}\leqslant Z,&\forall j\in {\underline {m}}\\&x_{i,j}\geqslant 0,&\forall (i,j)\in S_{Z}\end{aligned}}$

и обозначить $S_{Z}=\{(i,j)\in {\underline {n}}\times {\underline {m}}\mid p_{i,j}\leqslant Z\}$, а $Z$ за оптимальную максимальную нагрузку, получаемую у оракула, то можно получить более приемлемую ЛП. Решение ЛП не будет целочисленным, но его можно округлить, используя следующие правила:

• Каждая задача может быть присвоена только одной машине.
• Каждой машине может быть присвоено несколько задач.

Лемма. В решении вышеописанной ЛП максимум $m+n$ переменных $x_{i,j}$ больше нуля.

Доказательство. Пусть $D$ — количество переменных, а $C$ — количество неравенств ЛП. Тогда справедливы выражения $D=|S_{Z}|\leqslant m\cdot n$ и $C=D+m+n$. Базисное решение ЛП точно удовлетворяет максимум $D$ неравенствам, а значит $C-D=n+m$ ограничений вида $x_{i,j}\geqslant 0$ не выполнены минимум $n+m$ переменных равны нулю.

Из полученного решения ЛП можно построить связный граф $G=(J,M,E)$ распределения ресурсов, где $J=\{v_{i}\mid i\in {\underline {n}}\}$, $M=\{w_{j}\mid j\in {\underline {m}}\}$ и $E=\{(v_{i},w_{j})\mid x_{i,j}>0\}$. Такой граф будет иметь $m+n$ вершин, $m+n$ рёбер и максимум один цикл, так как граф связный. Чтобы правильно округлить решение с помощью графа $G$, необходимо сначала удалить из графа все вершины задач, точно распредленных какой-либо машине ($x_{i,j}=1$). В результате в графе не останется листьев из множества $J$ и можно будет найти на нем совершенное паросочетание, по результатам которого и будут распределены задачи.

Такой алгоритм обеспечивает $2$-аппроксимацию для решения проблемы, потому что для нераспределённыx однозначно задач ($0<x_{i,j}<1$) действительно $p_{i,j}\leqslant Z$ и каждая машина получит максимум одну такую нераспределённую задачу. Так каждая машина будет иметь максимальную нагрузку $Z$.