МАТЕМАТИКА
519.854.2
ПРЕОБРАЗОВАНИЕ СЕТЕВОГО ГРАФИКА ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ С ОГРАНИЧЕНИЯМИ ПРЕДШЕСТВОВАНИЯ
© 2009 г. А. А. Лазарев, Е. Р. Гафаров
Представлено академиком С.Н. Васильевым 19.03.2008 г. Поступило 19.03.2008 г.
ДОКЛАДЫ АКАДЕМИИ НАУК, 2009, том 424, № 1, с. 7-9
УДК
Для задач на графах построен алгоритм трудоемкости O(n5), преобразующий непланарный граф в планарный (n - количество вершин в графе). В результате получается граф, у которого сумма количества вершин и ребер не больше, чем у исходного графа.
Дано множество требований N = {1, 2, ..., n} и Kвозобновляемых ресурсов к = 1, 2, ..., K. В каждый момент времени t доступно Qk единиц ресурса к. Заданы продолжительности обслуживания pi е Z+ для каждого требования i = 1, 2, ..., n. Во время обслуживания требования i требуется qk < Qk единиц ресурса к = 1, 2, ..., K. После завершения обслуживания требования освобожденные ресурсы в полном объеме могут быть мгновенно назначены на обслуживание других требований.
Между некоторыми парами требований заданы ограничения предшествования: i ^ j означает, что обслуживание требования j начинается не раньше окончания обслуживания требования i. Ресурсы доступны для использования с момента времени t = 0. Прерывание при обслуживании требований запрещено.
Необходимо определить моменты начала обслуживания требований Si, i = 1, 2, ..., n, так, чтобы минимизировать время выполнения всего проекта Cmax = max { C }, где Ci = Si + pi. При этом долж-
i = 1, 2,..., n
ны быть соблюдены следующие ограничения:
1) в каждый момент времени t е [0, Cmax) выпол-
n
няются ограничения по ресурсам ^ qik ф() < Qk, к =
i = i
= 1, 2, ..., K, где 9i(t) = 1, если требование i обслуживается в момент времени t, и 9i(t) = 0 в противном случае. Все требования в процессе своего обслуживания должны быть полностью обеспечены ресурсами;
Институт проблем управления им. В.А. Трапезникова Российской Академии наук, Москва
2) не нарушаются отношения предшествования, т.е. Si + pi < Sj, если i ^ j, i, j е N.
Данную задачу будем называть задачей построения расписания проекта с учетом ограничений на ресурсы и обозначать RCPSP (Resources Constrained Project Scheduling Problem, как принято в англоязычной литературе). Данная задача может быть сведена за полиномиальное время к NP-трудной задаче о многомерном ранце [2].
Будем представлять структуру проекта как требования в вершинах ориентированного ацикличного графа G = (V, E), где каждой вершине из V = {1, 2, ..., n} соответствует некоторое требование из множества N = {1, 2, ..., n}, а множество дуг E = {(i, j)| i, j е V; i ^ j} соответствует ограничениям предшествования. Очевидно, что допустимое решение существует, только когда граф предшествования ацикличный. Такой ориентированный граф называют сетевым графиком.
ПЛАНАРНОСТЬ СЕТЕВОГО ГРАФИКА ДЛЯ ЗАДАЧИ RCPSP И ЕЕ ЧАСТНЫХ СЛУЧАЕВ
Два примера задачи RCPSP будем называть аналогичными, если первый пример сводится ко второму введением "пустых" требований (с нулевой продолжительностью) и удалением "лишних" связей, так что если между вершинами i и j был хотя бы один путь, то путь между ними останется. Если пути между вершинами не было, то он и не появится. Очевидно, что оптимальные значения целевой функции для аналогичных примеров равны.
Лемма 1. Пример, у которого в графе отношений предшествования G(V, E) встречается подграф K3, 3, может быть преобразован в аналогичный пример с графом G'(V, E') без подграфа K3, 3 при помощи удаления "лишних" дуг и добавления "пустых" вершин так, что n + e > n' + e'.
Лемма 2. Пример, у которого в графе отношений предшествования G(V, E) встречается подграф K5, может быть преобразован в аналогичный пример с графом G'(V, E') без подграфа K5 при помощи удаления "лишних" дуг.
8
ЛАЗАРЕВ, ГАФАРОВ
(a)
i10--о:
(б)
Г Q г2 ©
®
J®
©
с^©
(в)
©
(г)
©
©
Рис. 1. Укладка сетевого графика на плоскости.
Теорема 1. Пример задачи ЯСР8Р с графом Э(У, Е) можно преобразовать в аналогичный пример за 0(п5) операций, его граф отношений предшествования С(У, Е') будет планарным и п + е > П + е'.
АЛГОРИТМ УКЛАДКИ СЕТЕВОГО ГРАФИКА НА ПЛОСКОСТИ
При размещении элементов на электронной плате существенным является условие, чтобы соответствующий граф был планарным, связи между элементами не пересекались. Кроме того, на практике существует потребность представить сетевой график по ранее введенному проекту в наиболее удобном для пользователя виде. В наиболее популярных программах (MS Project, Spyder) сетевые графики представляются неудобно: дуги пересекаются или сливаются. В данном разделе представлен алгоритм укладки планарного сетевого графика на плоскости без пересечения дуг.
В работе [1] представлен известный алгоритм укладки на плоскости планарного графа. Важное отличие сетевого графика от ориентированного графа заключается в том, что вершины сетевого графика расположены вдоль некоторой виртуальной временной оси (обычно горизонтальной). Требование-предшественник изображается всегда левее своих последователей.
Кратко опишем алгоритм укладки планарного графа на плоскости и покажем, как его можно преобразовать для укладки планарного сетевого графика.
Алгоритм у [1] укладки графа Э представляет собой процесс последовательного присоединения к некоторому уложенному подграфу & графа Э новой цепи, оба конца которой принадлежат С. Тем самым эта цепь разбивает одну из граней графа & на две. В качестве начального плоского графа & выбирается любой простой цикл графа Э. Процесс продолжается до тех пор, пока не будет
S
2
S
ДОКЛАДЫ АКАДЕМИИ НАУК том 424 < 1 2009
ПРЕОБРАЗОВАНИЕ СЕТЕВОГО ГРАФИКА
9
построен плоский граф, изоморфный графу Э, или присоединение некоторой цепи окажется невозможным. В последнем случае граф Э не является планарным.
Введем ряд определений. Пусть построена некоторая укладка подграфа О графа Э. Сегментом 5 относительно С (или просто сегментом) будем называть подграф графа Э одного из следующих двух видов:
1) ребро е = uv е ЕЭ такое, что е £ ЕС, и, V е е УЭ', где ЕЭ - множество ребер графа Э, УЭ -множество вершин графа Э, аналогично, ЕЭ' -множество ребер подграфа С, УЭ' - множество вершин подграфа С;
2) связную компоненту графа Э-С, дополненную всеми ребрами графа Э, инцидентными вершинам взятой компоненты и концам этих ребер.
Вершину V сегмента 5 будем называть контактной, если V е УС.
Допустимой гранью для сегмента 5 называется грань Г графа С, содержащая все контактные вершины сегмента
Г(5) - множество допустимых граней для Простую цепь сегмента соединяющую две различные контактные вершины и не содержащую других контактных вершин, назовем а-ц е пью.
Два сегмента 52 и 52 относительно С назовем конфликтующими, если:
1) Г(51) п Г(52) ф 0;
2) существуют две а-цепи Ь1 е 52 и Ь2 е 52, которые без пересечений нельзя уложить одновременно ни в какую грань.
В работе [1] показано, что для продолжения алгоритма у можно выбирать любую а-цепь в любом сегменте и помещать ее в любую допустимую грань.
На рис. 1,а представлен сетевой граф с пересечением дуг. На рис. 1,6 изображена начальная цепь (граф С), его грани и сегменты 52, 52. Сегменты конфликтующие.
В алгоритме укладки сетевого графика выбор грани для очередной а-цепи необходимо производить согласно правилу: предшественник должен
находится левее последователя. Таким образом, при укладке а-цепи, соответствующей сегменту S2, выбрана грань Гх, а для укладки 5\ - оставшаяся грань Г2.
Укладка соответствующего графа представлена на рис. 1,в.
Заметим, что при такой укладке вершина-последователь 1 (номер в кружке) находится левее вершины-предшественника 11, что противоречит правилам представления сетевого графика. Полученную укладку можно растянуть, как представлено на рис. 1,г. Ребро (1, 2) станет дугообразным.
Зачастую полученное представление без пересечений лучше преобразовать, допустив пересечения. Такие преобразования лучше производить над полученной плоской укладкой, чтобы минимизировать количество пересечений.
Итак, при составлении проектов можно построить сетевой график проекта планарным. Действительно, в этом случае размерность задачи n + e не увеличивается. Согласно теореме Эйлера, количество ребер в планарном графе не превышает 3n - 6, что можно учитывать при оценке трудоемкости алгоритмов.
Любой непланарный граф G можно преобразовать в аналогичный планарный граф G' за O(n5) операций. При этом сумма количества вершин и ребер не увеличивается и путь из вершины i в вершину j сохранится, только в пути могут быть добавлены "пустые" вершины. Более того, планарный сетевой график можно удобно представить на плоскости, что полезно на практике.
Работа выполнена в рамках научной школы академика Ю.И. Журавлёва (грант НШ-5833. 2006.1) и частично поддержана Deutsche Akademische Austauschdienst (DAAD, грант A0206237/Ref. 325).
СПИСОК ЛИТЕРАТУРЫ
1. Емеличев В.А., Мельников О.И, Сарванов В.И, Тышкевич Р.И. Лекции по теории графов. / М.: Наука, 1990. 384 с.
2. Brucker P., Knust S. Complex Scheduling. B.: Springer, 2006. 284 p.
ДОКЛАДЫ АКАДЕМИИ НАУК том 424 < 1 2009
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.