Some Bounds for the Сompletion Time of Competing Jobs in Batch Planning

Vagina Mariya PhD in Physics and Mathematics associate professor at South Ural State Humanitarian Pedagogical University 454080, Russia, Chelyabinsk Region, Chelyabinsk, Lenin's str., 69 vaginamu@cspu.ru

Nigmatulin Ravil PhD in Physics and Mathematics associate professor at South Ural State Humanitarian Pedagogical University 454080, Russia, Chelyabinsk Region, Chelyabinsk, Lenin's str., 69 ravil@cspu.ru

Введение

В настоящее время теория графов является достаточно мощным средством решения многих задач, относящихся к обширному кругу проблем в информатике, технике и управлении. Многочисленные практические задачи, связанные с распределением оборудования, составлением расписания, планированием маршрутов перевозок, могут быть решены средствами теории графов ^{[1, 2, 4, 10, 11]}.

Раскраска графов на данный момент является одной из самых популярных и интенсивно изучаемых тем в теории графов. Проблема нахождения хроматического числа и построения минимальной раскраски графа является в общем случае нерешенной. Но большие возможности применения раскраски графов для решения самых различных практических задач привлекают к этой проблеме исследователей из различных областей науки ^{[3, 5-9, 12]}. Достаточно большая вычислительная сложность в решении задач, возникающая при использовании раскраски графов, приводит к активному поиску и разработке более эффективных алгоритмов и в настоящее время ^{[8, 9]}.

Постановка начальной задачи

Приведем формулировку задачи о составлении расписания выполнения конкурирующих работ. Эта задача рассматривалась в ^{[1, 2, 12]}.

Имеется задание, состоящее из `n` работ `a_(1), a_(2), ... a_(n)` , в котором одни работы могут выполняться параллельно (совместно) друг с другом, а другие конкурируют между собой за какие-либо ресурсы (например, используется общий механизм, который не может быть использован для выполнения хотя бы двух работ). Все работы в задании выполняются за одно и то же время `t_(0)` . Требуется определить минимальное время выполнения всех работ и составить расписание выполнения работ.

Наличие конкуренции между работами приводит к необходимости распределения работ по группам (в которых конкуренция между работами отсутствует) – пакетам. Составление расписания в таком случае принято называть пакетным планированием.

Сформулируем поставленную задачу на языке теории графов. Построим граф `G` , в котором вершины будут соответствовать работам `a_(1), a_(2), ... a_(n)` (граф конфликтов). Две вершины этого графа соединим ребром тогда и только тогда, когда соответствующие им работы конкурируют за механизмы. Любая правильная раскраска графа `G` определяет допустимое распределение работ – вершины одного цвета соответствуют работам, которые не конкурируют за механизмы и могут выполняться одновременно. И наоборот, любое распределение работ определяет правильную раскраску графа `G` . Если для раскраски `n` вершин использовались цвета `1, 2, ... , k` , то вершины, раскрашенные в цвет `i` , дают список работ, которые можно выполнять одновременно на `i` -ом временном интервале продолжительностью `t_(0)` . Минимальная раскраска графа конфликтов дает распределение работ с минимальным временем выполнения `T_(min)=chi(G) t_(0)` , где `chi(G)` - это хроматическое число графа `G` . Таким образом, для того, чтобы определить минимальное время выполнения всех работ, требуется определить хроматическое число графа конфликтов. А для того, чтобы составить расписание выполнения пакетов работ, нужно найти минимальную раскраску графа конфликтов `G` .

Обобщенная задача

Рассмотренная в предыдущем пункте задача может быть обобщена на случай конкурирующих работ, время выполнения которых различно (все работы можно разбить на группы в соответствии с временем их выполнения). Такой вариант обобщения исследован недостаточно ^{[5, 7, 12]}. Случай, когда работы могут быть разбиты на две группы (условно их можно назвать длительными и быстрыми работами) был рассмотрен в ^[3].

Имеется задание, состоящее из `n` работ `a_(1), a_(2), ... a_(n)` , в котором одни работы могут выполняться параллельно (совместно) друг с другом, а другие конкурируют между собой за какие-либо ресурсы. Для выполнения этих работ необходимо несколько различных механизмов. Никакой из механизмов не может быть занят одновременно хотя бы на двух работах. Работы разделены на `k` групп с определенным временем завершения `t_(i)gt0` `(i=1, 2, ..., k)` , причем `t_(1)gtt_(2)gt ... gtt_(k)` . Требуется оценить или определить минимальное время завершения всех работ и составить расписание выполнения работ.

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

Оценки минимального времени в обобщенной задаче

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

1. Пусть построен граф конфликтов, найдено его хроматическое число. Хроматическое число `chi` графа конфликтов определяет количество промежутков времени, необходимых для выполнения всех работ. Длина каждого промежутка времени не более чем `t_(1)` – времени выполнения самого длительной группы работ. Поэтому минимальное время выполнения всех работ не больше чем произведение хроматического числа графа конфликтов на время выполнения длительной группы работ: `chi t_(1)` .

С другой стороны, существует как минимум один промежуток длиной ` t_(1)` , а остальные не меньше чем `t_(k)` (время выполнения группы самых коротких работ). Поэтому снизу минимальное время ограничено суммой `t_(1)+( chi-1) t_(k)` . Таким образом, границы для минимального времени выполнения работ могут быть установлены на основе максимального и минимального промежутков времени выполнения работ:

`t_(1)+(chi-1) t_(k) lt= T_(min) lt= chi t_(1)` (1)

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

Рис. 1. Примеры графов, для которых достигается верхняя оценка (1): дерево (слева) и четный цикл (справа). Длительные работы соответствуют вершинам `a_(1)` и ` a_(2)` (время выполнения `t_(1)` ). В обоих случаях минимальное время `2 t_(1)` .

Нижняя оценка достигается, например, когда быстрые работы попарно конкурируют между собой (соответствующие вершины графа конфликтов порождают полный подграф), а остальные работы не конкурируют между собой, но конкурируют с быстрыми работами. Проиллюстрируем эту ситуацию следующим примером.

Пример 1. Пусть найдена минимальная раскраска графа конфликтов (см. рис. 2). Очевидно, `chi = 4` . Быстрые работы соответствуют вершинам ` a_(2), a_(3), a_(4), a_(7), a_(8)` , время выполнения каждой из них обозначим `t_(3)` . Длительная работа `a_(1)` имеет время выполнения `t_(1)`. Остальные работы выполняются за время `t_(2)` `(t_(1)gtt_(2)gtt_(3))` и могут быть выполнены параллельно с `a_(1)` в одном пакете, поэтому минимальное время равно `t_(1)+3t_(3)` .

Рис. 2. Пример графа, для которого достигается нижняя оценка (1) (см. пример 1).

2. Рассмотрим подграфы `G_(i)` `(i=1, 2, ... , k)` , порожденные множеством вершин `V_(i)`, соответствующих работам в группе `i` . Граф `G_i` содержит все ребра графа конфликтов, концы которых принадлежат множеству `V_(i)` .

Пусть в графе конфликтов подграф `G_(i)` `(i=1, 2, ... , k)` содержит наибольшую клику порядка `r_(i)` . Очевидно, что количество цветов необходимых для минимальной раскраски подграфа `G_(i)` , не меньше чем `r_(i)` . Заметим, что при сравнении `G_(1)` и `G_(2)` количество цветов, необходимых для минимальной раскраски, будет увеличиваться только при `r_(2)gtr_(1)` , причем начальное время `r_(1) t_(1)` увеличится на величину `(r_(2)-r_(1))t_(2)` . Далее будем последовательно сравнивать порядок `r_(i)` с порядками `r_(1),r_(2), ... ,r_(i-1)` наибольших клик в `G_(i)` и аналогично определять величину, на которую увеличится уже найденное время. Тогда справедлива следующая оценка минимального времени завершения всех работ:

`r_(1) t_(1) + max(0, r_(2)-r_(1)) t_(2) + max(0, r_(3)-max(r_(1),r_(2)) ) t_(3) +`

`+ max(0,r_(4)-max(r_(1),r_(2),r_(3)))t_(4)+ ...`

`... + max(0, chi - max(r_(1), r_(2), ... ,r_(k-1)) ) t_(k) le T_(min)` (2)

Проиллюстрируем достижимость оценки (2) на следующем примере.

Пример 2. Пусть найдена минимальная раскраска графа конфликтов (см. рис. 3). Очевидно, `chi ``= 5` . Время выполнения каждой из работ `a_(6), a_(7), a_(9), a_(10)` (множество `V_(3)` ) равно `t_(3)=3` , для работ `a_(2), a_(4), a_(8)` (множество `V_(2)` ) время `t_(2)=4` , для работ `a_(1), a_(3), a_(5)` (множество `V_(1)` ) время `t_(1)=5` . Минимальное время завершения всех работ равно `3 t_(1)+0 t_(2)+2 t_(3)=21` и оценка (2) достигнута.

Рис. 3. Пример графа, для которого достигается верхняя оценка (2) (см. пример 2).

3. Пусть множество вершин, соответствующих пакету работ с самым большим временем завершения (длительные работы), графа конфликтов при построении минимальной раскраски было покрашено в `s` цветов. В этом случае имеем не более чем `s` промежутков c временем выполнения `t_(1)` и не более чем `(chi - s)` промежутков с временем выполнения не более чем `t_(2)` .Тогда справедлива оценка:

`T_(min) lt= s t_(1) + (chi - s) t_(2)` . (3)

Равенство в оценке (3) достигается только для некоторой минимальной раскраски (в отличии, например, от деревьев) графа конфликтов. При этом для различных минимальных раскрасок оценки сверху минимального времени могут значительно отличаться. Рассмотрим пример.

Пример 3. Пусть построены две различные минимальные раскраски графа конфликтов (см. рис. 4). Время выполнения каждой из работ `a_(2), a_(4), a_(9), a_(10)` обозначим `t_(1)` , для работ `a_(1), a_(3), a_(5)` обозначим время `t_(2)` , для работ `a_(6), a_(7), a_(8)` – время `t_(3)` . Очевидно, для раскраски на рис. 4 слева в формуле (3) получаем равенство и минимальное время равно `2 t_(1) + 3 t_(2)` . А для раскраски на рис. 4 справа формула (3) дает величину `4 t_(1) + t_(2)` , что больше предыдущего значения.

Рис. 4. Примеры двух различных минимальных раскрасок графа конфликтов. Для первой раскраски (слева) оценка (3) достижима (см. пример 3).

Заключение

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