Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Software systems and computational methods
Reference:

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

DOI:

10.7256/2454-0714.2017.3.24114

Received:

07-09-2017


Published:

06-10-2017


Abstract: The subject of the research is the graphical models for solving the problem of minimizing the completion time of competing jobs in batch planning. Great interest in such problems is explained by numerous applications that arise in the theory of graphs, in the planning of production and transport routes, in the calculation of distribution, etc. In general, there is no effective algorithm for solving these problems. Particular attention is paid to the use of the coloring of the conflict graph, which makes it possible to build estimates of the minimum execution time for all jobs. The main research methods were methods of graph theory and computational experiment. Particular attention was paid to the graph coloring. Based on the coloring of the conflict graph, two-sided estimates of the minimum execution time of competing tasks for batch planning are constructed. All the estimates found are attainable. They are linear combinations of time slots for executing work packets. The coefficients of the linear combination are expressed through the different characteristics of the conflict graph, its subgraphs (for example, the chromatic number, the density of the graph).


Keywords:

competing jobs, batch planning, graph theoretic model, conflict graph, minimal coloring, chromatic number of graph, full subgraph, completion time, minimum time, work schedule


Введение

В настоящее время теория графов является достаточно мощным средством решения многих задач, относящихся к обширному кругу проблем в информатике, технике и управлении. Многочисленные практические задачи, связанные с распределением оборудования, составлением расписания, планированием маршрутов перевозок, могут быть решены средствами теории графов [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].

References
1. Emelichev V.A., Mel'nikov O.I., Sarvanov V.I., Tyshkevich R.I. Lektsii po teorii grafov. M.: Nauka, 1990. 384 s.
2. Kristofides N. Teoriya grafov. Algoritmicheskii podkhod. M.: Mir, 1978. 432 s.
3. Nigmatulin R.M., Vagina M.Yu. Postroenie otsenok vremeni v obobshchennoi zadache optimal'nogo raspredeleniya oborudovaniya // Matematicheskoe i komp'yuternoe modelirovanie: sbornik materialov IV Mezhdunarodnoi nauchnoi konferentsii.-Omsk: Izd-vo Om. gos. un-ta. 2016. S. 60-62.
4. Roberts F.S. Diskretnye matematicheskie modeli s prilozheniyami k sotsial'nym, biologicheskim i ekologicheskim zadacham. M.: Nauka, 1986. 496 s.
5. Al-Anzi F.S., Sotskov Y.N., Allahverdi A., Andreev G. V. Using mixed graph coloring to minimize total completion time in job shop scheduling // Applied Mathematics and Computation. 2006. vol. 182. pp. 1137-1148.
6. Byskov J.M. Enumerating maximal independent sets with applications to graph colouring // Operations Research Letters. Vol. 32 (6). 2004. pp. 547-556.
7. Furini F., Malaguti E. Exact weighted vertex coloring via branch-and-price // Discrete Optimization. 2012. vol. 9. pp. 130-136.
8. Jin Y., Hamiez JP., Hao JK. Algorithms for the minimum sum coloring problem: a review // Artificial Intelligence Review. 2017. vol. 47, no. 3. pp. 367-394.
9. Lewis R., Thompson J. On the application of graph colouring techniques in round-robin sports scheduling // Computers and Operations Research. 2011. vol. 38. no. 1, pp. 190-204.
10. Lewis R. A Guide to Graph Colouring: Algorithms and Applications. N.-Y.: Springer, 2015. 253 p.
11. Marx D. Graph colouring problems and their applications in scheduling // Periodica Polytechnica, Electrical Engineering. 2004. vol. 48. no. 1-2. pp. 11-16.
12. Thomassen S., Erds P., Alavi Y., Malde P., Schwenk A. Tight bounds on the chromatic sum of a connected graph // Graph Theory. 1989. vol. 13. no. 3, pp. 353-357.