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

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

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

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

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

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

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

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

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

^[1]

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

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

Жадное полиномиальное решение [ править ]

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

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

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

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

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

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

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

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

Позвольте быть набор логических переменных. Позвольте быть набором

{\ Displaystyle X = \ {x_ {1}, x_ {2}, ..., x_ {p} \}}

{\ Displaystyle C = \ {c_ {1}, c_ {2}, ..., c_ {q} \}}

положения над X такой , что (1) каждый пункт в C имеет не более трех литералов и (2) каждая переменная ограничена появляются один или два раза положительно и отрицательно один раз в целом C . Решите, есть ли такое присвоение переменным X , чтобы каждое предложение в C имело хотя бы один истинный литерал.

Эта версия была показана ^[4] как NP-полная, как и неограниченная версия.

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

Для каждой переменной (для i = 1, ..., p ) создайте группу с двумя интервалами: один, начинающийся с (представляющий присвоение ), а другой, начинающийся с (представляющий присвоение ). ${\ displaystyle x_ {i}}$ ${\ displaystyle 50i-10}$ ${\ displaystyle x_ {i} = false}$ ${\ displaystyle 50i + 10}$ ${\ displaystyle x_ {i} = 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} = false}$
- Для каждой отрицательной переменной - интервал, начинающийся с . Этот интервал пересекает интервал, связанный с . ${\ displaystyle x_ {i}}$ $50i+8$ $50i+10$ $x_{i}=true$

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

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

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

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

Для каждой группы я создаю две переменные, представляющие ее два интервала: и . $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-complete, когда некоторые группы содержат 2 или более интервалов [ править ]

GISMPk является NP-полным, даже когда . ^[5] $k\geq 2$

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

Полиномиальное 2-приближение [ править ]

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

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

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

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

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

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

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

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

Графические представления [ править ]

Проблема интервального планирования может быть описана графом пересечений , где каждая вершина является интервалом, а между двумя вершинами есть ребро тогда и только тогда, когда их интервалы перекрываются. В этом представлении задача интервального планирования эквивалентна нахождению максимального независимого множества в этом графе пересечений. В обычных графах найти максимальное независимое множество NP-сложно. Поэтому интересно, что в графах пересечений интервалов это можно сделать точно за полиномиальное время. ^{[ необходима цитата ]}

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

Варианты [ править ]

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

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

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

Другой вариант - использование m процессоров вместо одного процессора. Т.е. m разных задач могут выполняться параллельно. ^[2]

См. Также [ править ]

Планирование (вычисления)
Первое планирование на самый ранний срок

Источники [ править ]

^ Клейнберг, Джон; Тардос, Ива (2006). Разработка алгоритмов . ISBN 978-0-321-29535-4.
^ a b Накадзима, К .; Хакими, SL (1982). «Результаты сложности для планирования задач с дискретным временем начала». Журнал алгоритмов . 3 (4): 344. DOI : 10.1016 / 0196-6774 (82) 90030-X .
^ a b Марк Кейл, Дж. (1992). «О сложности составления расписания задач с дискретным временем запуска». Письма об исследованиях операций . 12 (5): 293–295. DOI : 10.1016 / 0167-6377 (92) 90087-J .
^ Пападимитриу, Христос Х .; Стейглиц, Кеннет (июль 1998 г.). Комбинаторная оптимизация: алгоритмы и сложность . Дувр. ISBN 978-0-486-40258-1.
^ а б в г Spieksma, FCR (1999). «Об аппроксимируемости задачи интервального планирования». Журнал планирования . 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-й год . цитируя Колена в личном общении
^ Чужой, Дж . ; Островский, Р .; Рабани, Ю. (2006). «Алгоритмы приближения для задачи выбора рабочего интервала и связанных задач планирования». Математика исследования операций . 31 (4): 730. CiteSeerX 10.1.1.105.2578 . DOI : 10.1287 / moor.1060.0218 .

[KleinbergTardos-1] Клейнберг, Джон; Тардос, Ива (2006). Разработка алгоритмов . ISBN 978-0-321-29535-4.

[NakajimaHakimi-2] Накадзима, К .; Хакими, SL (1982). «Результаты сложности для планирования задач с дискретным временем начала». Журнал алгоритмов . 3 (4): 344. DOI : 10.1016 / 0196-6774 (82) 90030-X .

[Keil-3] Марк Кейл, Дж. (1992). «О сложности составления расписания задач с дискретным временем запуска». Письма об исследованиях операций . 12 (5): 293–295. DOI : 10.1016 / 0167-6377 (92) 90087-J .

[4] Пападимитриу, Христос Х .; Стейглиц, Кеннет (июль 1998 г.). Комбинаторная оптимизация: алгоритмы и сложность . Дувр. ISBN 978-0-486-40258-1.

[Spieksma-5] а б в г Spieksma, FCR (1999). «Об аппроксимируемости задачи интервального планирования». Журнал планирования . 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-й год . цитируя Колена в личном общении

[ChuzoiEtAl-6] Чужой, Дж . ; Островский, Р .; Рабани, Ю. (2006). «Алгоритмы приближения для задачи выбора рабочего интервала и связанных задач планирования». Математика исследования операций . 31 (4): 730. CiteSeerX 10.1.1.105.2578 . DOI : 10.1287 / moor.1060.0218 .

[1]