Статья 'Некоторые оценки времени выполнения конкурирующих работ при пакетном планировании' - журнал 'Программные системы и вычислительные методы' - NotaBene.ru
по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > Требования к статьям > Политика издания > Редакция > Порядок рецензирования статей > Редакционный совет > Ретракция статей > Этические принципы > О журнале > Политика открытого доступа > Оплата за публикации в открытом доступе > Online First Pre-Publication > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала
ГЛАВНАЯ > Вернуться к содержанию
Программные системы и вычислительные методы
Правильная ссылка на статью:

Некоторые оценки времени выполнения конкурирующих работ при пакетном планировании

Вагина Мария Юрьевна

кандидат физико-математических наук

доцент, Южно-Уральский государственный гуманитарно-педагогический университет

454080, Россия, Челябинская область, г. Челябинск, ул. Ленина, 69

Vagina Mariia

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
Нигматулин Равиль Михайлович

кандидат физико-математических наук

доцент, Южно-Уральский государственный гуманитарно-педагогический университет

454080, Россия, Челябинская область, г. Челябинск, ул. Ленина, 69

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

Дата направления статьи в редакцию:

07-09-2017


Дата публикации:

06-10-2017


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


Ключевые слова:

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

Работа подготовлена при финансовой поддержке ФГБОУ ВО «ШГПУ» по договору на выполнение НИР от 27.04.2017 г. № 16-518 по теме: «Построение и исследование математических моделей некоторых оптимизационных задач, сводящихся к раскраске графов».

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].

Библиография
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
Ссылка на эту статью

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


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.