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

Класс задач по информатике

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Взвешенный

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

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

// Векторы уже отсортированы от самого раннего до самого позднего времени окончания.int v [ numOfVectors + 1 ]; // список интервальных векторов    int w [ numOfVectors + 1 ]; // w[j] — вес для v[j].    int p [ numOfVectors + 1 ]; // p[j] — это количество векторов, которые заканчиваются до начала v[j].    int M [ numOfVectors + 1 ];    int finalSchedule []; // v[0] не существует, и первый интервальный вектор присваивается v[1].ш [ 0 ] = 0 ; р [ 0 ] = 0 ; М [ 0 ] = 0 ;        // Следующий код определяет значение M для каждого вектора.// Максимальный вес расписания равен M[numOfVectors].для ( int i = 1 ; i < numOfVectors + 1 ; i ++ ) {            М [ я ] = макс ( w [ я ] + М [ р [ я ]], М [ я - 1 ]);       }// Функция построения оптимального расписаниярасписание ( j ) {   если ( j == 0 ) { возврат ; }       иначе если ( w [ j ] + M [ p [ j ]] >= M [ j - 1 ]){         добавить ( v [ j ], FinalSchedule ); // добавляет v[j] к расписанию.   расписание ( p [ j ]); } иначе { расписание ( j - 1 ); }      }

^[4]

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

GISMPk является NP-полной, даже когда . ^[8] ${\displaystyle k\geq 2}$

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

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

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

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

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

Фактор аппроксимации 2 является узким. Например, в следующем примере GISMP2:

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

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

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

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

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

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

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

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

Вариации

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

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

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

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

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

Источники

1. Колен, А. (2007). «Интервальное планирование: обзор». Naval Research Logistics . 54 (5): 530–543. doi : 10.1002/nav.20231 . S2CID  15288326.
2. Кляйнберг, Джон; Тардос, Ева (2006). Алгоритм проектирования . Пирсон/Аддисон-Уэсли. ISBN 978-0-321-29535-4.
3. Бар-Ной, Амоц; Бар-Йехуда, Реувен; Фройнд, Ари; (Сеффи) Наор, Джозеф; Шибер, Барух (2001-09-01). "Унифицированный подход к аппроксимации распределения ресурсов и планирования". Журнал ACM . 48 (5): 1069–1090. doi :10.1145/502102.502107. ISSN  0004-5411. S2CID  12329294.
4. Кляйнберг, Джон; Тардос, Ева (2006). Разработка алгоритмов (1-е изд.). Пирсон. п. 254. ИСБН 9780321295354.
5. Накадзима, К.; Хакими, С.Л. (1982). «Результаты сложности планирования задач с дискретным временем начала». Журнал алгоритмов . 3 (4): 344. doi :10.1016/0196-6774(82)90030-X.
6. Mark Keil, J. (1992). «О сложности планирования задач с дискретным временем начала». Operations Research Letters . 12 (5): 293–295. doi :10.1016/0167-6377(92)90087-j.
7. Пападимитриу, Христос Х.; Стейглиц, Кеннет (июль 1998 г.). Комбинаторная оптимизация: алгоритмы и сложность . Дувр. ISBN 978-0-486-40258-1.
8. Spieksma, FCR (1999). «Об аппроксимируемости задачи интервального планирования». Journal of Scheduling . 2 (5): 215–227. CiteSeerX 10.1.1.603.5538 . doi :10.1002/(sici)1099-1425(199909/10)2:5<215::aid-jos27>3.0.co;2-y. со ссылкой на Колена в личном общении
9. Чужой, Юлия ; Островский, Рафаил ; Рабани, Ювал (2006). «Алгоритмы аппроксимации для задачи выбора интервала работы и связанных с ней задач планирования». Математика исследования операций . 31 (4): 730–738. CiteSeerX 10.1.1.105.2578 . doi :10.1287/moor.1060.0218.