Интервальное планирование

Интервальное планирование — это класс задач в информатике , особенно в области разработки алгоритмов . Проблемы рассматривают совокупность задач. Каждая задача представлена ​​интервалом, описывающим время, в течение которого она должна быть обработана некоторой машиной (или, что то же самое, запланировано на каком-то ресурсе). Например, задача A может выполняться с 14:00 до 5:00, задача B — с 4:00 до 10:00, а задача C — с 9:00 до 11:00. Подмножество интервалов является совместимым , если никакие два интервала не перекрываются на машине/ресурсе. Например, подмножество {A,C} совместимо, как и подмножество {B}; но ни {A,B}, ни {B,C} не являются совместимыми подмножествами, поскольку соответствующие интервалы внутри каждого подмножества перекрываются.

Задача максимизации планирования интервалов (ISMP) заключается в нахождении наибольшего совместимого набора, т. е. набора непересекающихся интервалов максимального размера. Цель здесь — выполнить как можно больше задач, то есть максимизировать пропускную способность . Это эквивалентно поиску максимального независимого множества в графе интервалов .

Обобщение проблемы рассматривает $k>1$ машины/ресурсы. Здесь цель найти $k$ совместимые подмножества, объединение которых является наибольшим.

В обновленной версии задачи интервалы разбиты на группы. Подмножество интервалов является совместимым, если никакие два интервала не перекрываются и, более того, никакие два интервала не принадлежат одной группе (т. е. подмножество содержит не более одного представителя каждой группы). Каждая группа интервалов соответствует одной задаче и представляет собой несколько альтернативных интервалов, в которых она может быть выполнена.

Проблема принятия решения о планировании групповых интервалов (GISDP) заключается в том, чтобы решить, существует ли совместимый набор, в котором представлены все группы. Целью здесь является выполнение одной репрезентативной задачи из каждой группы. GISDPk — это ограниченная версия GISDP, в которой количество интервалов в каждой группе не превышает k .

Задача максимизации планирования групповых интервалов (GISMP) заключается в поиске наибольшего совместимого набора — набора непересекающихся представителей максимального размера. Целью здесь является выполнение репрезентативной задачи из как можно большего числа групп. GISMPk — это ограниченная версия GISMP, в которой количество интервалов в каждой группе не превышает k . Эту проблему часто называют JISPk, где J означает Job .

GISMP — самая общая проблема; две другие проблемы можно рассматривать как частные случаи:

• ISMP — это особый случай, в котором каждая задача принадлежит своей группе (т. е. она равна GISMP1).
• GISDP — это проблема определения того, равен ли максимум количеству групп.

Все эти проблемы можно обобщить, добавив вес для каждого интервала, представляющий прибыль от выполнения задачи в этом интервале. Затем цель состоит в том, чтобы максимизировать общий вес.

Все эти проблемы являются частными случаями одномашинного планирования , поскольку они предполагают, что все задачи должны выполняться на одном процессоре. Планирование одной машины — это особый случай оптимального планирования заданий .

Максимизация одноинтервального планирования

Одноинтервальное планирование означает создание интервального расписания, в котором интервалы не перекрываются.

Невзвешенный

Некоторые алгоритмы, которые на первый взгляд могут показаться многообещающими, на самом деле не находят оптимального решения:

• Выбор интервалов, которые начинаются раньше всех, не является оптимальным решением, поскольку, если самый ранний интервал окажется очень длинным, его принятие заставит нас отклонить многие другие более короткие запросы.
• Выбор самых коротких интервалов или интервалов с наименьшим количеством конфликтов также не является оптимальным.

Следующий жадный алгоритм , называемый «Планирование с первым крайним сроком» , действительно находит оптимальное решение для невзвешенного одноинтервального планирования:

1. Выберите интервал x с самым ранним временем окончания .
2. Удалите x и все интервалы, пересекающие x , из набора интервалов-кандидатов.
3. Повторяйте до тех пор, пока набор интервалов-кандидатов не станет пустым.

Всякий раз, когда мы выбираем интервал на шаге 1, нам, возможно, придется удалить много интервалов на шаге 2. Однако все эти интервалы обязательно пересекают время окончания x , и, следовательно, все они пересекают друг друга. Следовательно, не более 1 из этих интервалов может находиться в оптимальном решении. Следовательно, для каждого интервала оптимального решения существует интервал жадного решения. Это доказывает, что жадный алгоритм действительно находит оптимальное решение.

Более формальное объяснение даёт аргумент Charging .

Жадный алгоритм может быть выполнен за время O( n log n ), где n — количество задач, с использованием этапа предварительной обработки, на котором задачи сортируются по времени их завершения.

Взвешенный

Проблемы, связанные с планированием взвешенных интервалов, эквивалентны поиску независимого множества с максимальным весом в интервальном графе . Такие задачи можно решить за полиномиальное время.

Предполагая, что векторы отсортированы от самого раннего до самого позднего времени окончания, следующий псевдокод определяет максимальный вес одноинтервального расписания за время Θ(n):

// The vectors are already sorted from earliest to latest finish time.
int v[numOfVectors + 1]; // list of interval vectors
int w[numOfVectors + 1]; // w[j] is the weight for v[j].
int p[numOfVectors + 1]; // p[j] is the # of vectors that end before v[j] begins.
int M[numOfVectors + 1]; 
int finalSchedule[];

// v[0] does not exist, and the first interval vector is assigned to v[1].
w[0] = 0; p[0] = 0; M[0] = 0;

// The following code determines the value of M for each vector.
// The maximum weight of the schedule is equal to M[numOfVectors].
for (int i = 1; i < numOfVectors + 1; i++) {
    M[i] = max(w[i] + M[p[i]], M[i - 1]);
}

// Function to construct the optimal schedule
schedule (j) {
    if (j == 0) { return; }
    else if (w[j] + M[p[j]] >= M[j - 1]){
        prepend(v[j], finalSchedule); // prepends v[j] to schedule.
        schedule(p[j]);
    } else { schedule(j - 1); }
}

Пример

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

Здесь мы вводим наш окончательный вектор (где j=9 в этом примере) в нашу функцию расписания из приведенного выше блока кода. Мы выполняем действия, указанные в таблице ниже, до тех пор, пока j не станет равным 0, после чего мы включаем в наш окончательный график только те интервалы, которые соответствуют заданному значению. ${\textstyle w[j]+M[p[j]]\geq M[j-1]}$ требование. Это окончательное расписание представляет собой расписание с максимальным весом.

дж	Расчет	${\textstyle w[j]+M[p[j]]\geq M[j-1]}$ (т.е. этот вектор включен в окончательный график)	Установите j на
9	${\begin{aligned}&w[j]+M[p[j]]=w[9]+M[p[9]]=5+M[6]=5+16=21\\&M[j-1]=M[9-1]=M[8]=20\end{aligned}}$	Истинный	j=p[j]=p[9]=6
6	${\begin{aligned}&w[j]+M[p[j]]=w[6]+M[p[6]]=5+M[4]=5+11=16\\&M[j-1]=M[6-1]=M[5]=11\end{aligned}}$	Истинный	j=p[j]=p[6]=4
4	${\begin{aligned}&w[j]+M[p[j]]=w[4]+M[p[4]]=3+M[1]=3+5=8\\&M[j-1]=M[4-1]=M[3]=11\\\end{aligned}}$	ЛОЖЬ	д=д-1=4-1=3
3	${\begin{aligned}&w[j]+M[p[j]]=w[3]+M[p[3]]=6+M[1]=6+5=11\\&M[j-1]=M[3-1]=M[2]=5\end{aligned}}$	Истинный	j=p[j]=p[3]=1
1	${\begin{aligned}&w[j]+M[p[j]]=w[1]+M[p[1]]=5+M[0]=5+0=5\\&M[j-1]=M[1-1]=M[0]=0\end{aligned}}$	Истинный	j=p[j]=p[1]=0

Решение о групповом интервальном планировании

NP-полные, если некоторые группы содержат 3 и более интервалов.

GISDPk является NP-полным, если $k\geq 3$, даже если все интервалы имеют одинаковую длину. Это можно показать путем сокращения следующей версии проблемы булевой выполнимости , которая была показана быть NP-полной , как и неограниченная версия.

Позволять $X=\{x_{1},x_{2},\dots ,x_{p}\}$ быть набором логических переменных. Позволять $C=\{c_{1},c_{2},\dots ,c_{q}\}$ быть набором предложений над X таким образом, что (1) каждое предложение в C имеет не более трех литералов и (2) каждая переменная ограничена тем, что может появляться один или два раза в положительном и один раз отрицательном значении в C . Решите, существует ли присвоение переменным X такое, что каждое предложение в C имеет хотя бы один истинный литерал.

Учитывая пример этой проблемы выполнимости, постройте следующий экземпляр GISDP. Все интервалы имеют длину 3, поэтому достаточно представить каждый интервал по времени его начала:

• Для каждой переменной $x_{i}$ (для i = 1,..., p ), создайте группу с двумя интервалами: один начинается с $50i-10$ (представляющее задание $x_{i}=\mathrm {false}$) и еще один, начиная с $50i+10$ (представляющее задание $x_{i}=\mathrm {true}$).
• Для каждого пункта $c_{j}$ (для j = 1,..., q ) создайте группу со следующими интервалами:
  • Для каждой переменной $x_{i}$ появляется положительно который впервые в C - интервал, начинающийся с $50i-12$.
  • Для каждой переменной $x_{i}$ который появляется положительно во второй раз в C - интервал, начинающийся с $50i-8$. Заметим, что оба этих интервала пересекают интервал $50i-10$, связанный с $x_{i}=\mathrm {false}$.
  • Для каждой переменной $x_{i}$ что выглядит отрицательно - интервал, начинающийся с $50i+8$. Этот интервал пересекает интервал $50i+10$ связанный с $x_{i}={\text{true}}$.

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

Построенный GISDP имеет допустимое решение (т.е. планирование, в котором представлена ​​каждая группа), тогда и только тогда, когда данный набор логических предложений имеет удовлетворяющее назначение. Следовательно, GISDP3 является NP-полным, как и GISDPk для каждого $k\geq 3$.

Полиномиальный, когда все группы содержат не более 2 интервалов

GISDP2 можно решить за полиномиальное время путем следующего сведения к проблеме 2-выполнимости :

• Для каждой группы я создаю две переменные, представляющие два ее интервала: $x_{i}$ и $y_{i}$.
• Для каждой группы i создайте предложения: $x_{i}\cup y_{i}$ и $\neg {x_{i}}\cup \neg {y_{i}}$, которые представляют собой утверждение, что следует выбрать ровно один из этих двух интервалов.
• Для каждых двух пересекающихся интервалов (т.е. $x_{i}$ и $y_{j}$) создайте предложение: $\neg {x_{i}}\cup \neg {y_{j}}$, которые представляют собой утверждение, что следует выбрать не более одного из этих двух интервалов.

Эта конструкция содержит не более O( n ² ) предложений (по одному на каждое пересечение интервалов плюс два на каждую группу). Каждое предложение содержит 2 литерала. Выполнимость таких формул можно определить за время, линейное по количеству предложений (см. 2-SAT ). Следовательно, GISDP2 можно решить за полиномиальное время.

Максимизация группового интервального планирования

MaxSNP-полный, если некоторые группы содержат 2 и более интервалов.

GISMPk является NP-полным, даже если $k\geq 2$.

Более того, GISMPk является MaxSNP -полным, т.е. у него нет PTAS, если только P=NP. Это можно доказать, продемонстрировав сохраняющее приближение сокращение от MAX 3-SAT-3 до GISMP2.

Полиномиальное 2-приближение

Следующий жадный алгоритм находит решение, содержащее не менее 1/2 оптимального количества интервалов:

1. Выберите интервал x с самым ранним временем окончания .
2. Удалите x и все интервалы, пересекающие x , и все интервалы в той же группе x из набора интервалов-кандидатов.
3. Продолжайте до тех пор, пока набор интервалов-кандидатов не станет пустым.

Формальное объяснение дается аргументом Charging .

Коэффициент аппроксимации 2 является точным. Например, в следующем экземпляре GISMP2:

• Группа №1: {[0..2], [4..6]}
• Группа №2: {[1..3]}

Жадный алгоритм выбирает только 1 интервал [0..2] из группы №1, тогда как оптимальное планирование состоит в выборе [1..3] из группы №2, а затем [4..6] из группы №1.

Более общий алгоритм аппроксимации обеспечивает двухфакторную аппроксимацию для взвешенного случая.

Алгоритмы аппроксимации на основе ЛП

Используя технику релаксации линейного программирования , можно аппроксимировать оптимальное планирование с немного лучшими коэффициентами аппроксимации. Коэффициент аппроксимации первого такого алгоритма асимптотически равен 2, когда k велико, но когда k = 2, алгоритм достигает коэффициента аппроксимации 5/3. Коэффициент аппроксимации для произвольного k позже был улучшен до 1,582.

Связанные проблемы

Задачу интервального планирования можно описать графом пересечений , где каждая вершина является интервалом, а между двумя вершинами существует ребро тогда и только тогда, когда их интервалы перекрываются. В этом представлении проблема интервального планирования эквивалентна поиску максимального независимого множества в этом графе пересечений. Найти максимальное независимое множество NP-трудно в общих графах, но в частном случае графов пересечений (ISMP) это можно сделать за полиномиальное время.

Задача группового интервального планирования (GISMPk) может быть описана аналогичным графом пересечения интервалов с дополнительными ребрами между каждыми двумя интервалами одной и той же группы, т. е. это объединение ребер графа интервалов и графа, состоящего из n непересекающихся клики размера k .

Вариации

Важным классом алгоритмов планирования является класс алгоритмов динамического приоритета. Когда ни один из интервалов не перекрывается, оптимальное решение тривиально. Оптимум для невзвешенной версии можно найти при первом планировании самого раннего срока . Планирование с взвешенными интервалами — это обобщение, при котором каждой выполняемой задаче присваивается значение, а цель — максимизировать общую ценность. Решение не обязательно должно быть уникальным.

Проблема интервального планирования является одномерной – имеет значение только временное измерение. Проблема максимального непересекающегося множества представляет собой обобщение на два или более измерений. Это обобщение также является NP-полным.

Другим вариантом является распределение ресурсов, при котором набор интервалов s планируется с использованием ресурсов k так, что k минимизируется. То есть все интервалы должны быть запланированы, но цель — минимизировать использование ресурсов.

имеется m Другой вариант — когда вместо одного процессора процессоров. Т.е. m разных задач могут выполняться параллельно. См. Планирование идентичных машин .

Планирование одной машины также представляет собой очень похожую проблему.