СЕТЕВОЕ  ПЛАНИРОВАНИЕ  НА  ОСНОВЕ  МОДЕЛЕЙ  И  МЕТОДОВ  ИДЕМПОТЕНТНОЙ  АЛГЕБРЫ

Пузиков  Александр  Юрьевич

магистр,  кафедра  системного  программирования,  математико-механический  факультет  Санкт-Петербургский  государственный  университет,  РФ,  г.  Санкт-Петербург

E-mail:   gooogleshandi@gmail.com

1     Введение

Задачи  из  области  планирования  проектов  обычно  представляются  в  виде  задач  оптимизации.  Такие  проблемы,  например,  возникают  на  производстве  при  попытках  создать  план  проекта,  который  минимизирует  максимальное  отклонение  между  временем  завершения  всех  задач  в  проекте,  при  различных  условиях,  которые  накладываются  на  порядок  выполнения  задач.  Рассмотрим  проект,  состоящий  из  n  операций,  которые  выполняются  при  ограничениях  типа  «старт-финиш»  и  «старт-старт».  Ограничение  «старт-финиш»  устанавливает  границу  для  минимального  времени  задержки  между  началом  одной  задачи  и  окончанием  другой.  Предположим,  что  каждая  задача  немедленно  заканчивается,  как  только  указанные  ограничения  оказываются  выполненными.  Ограничение  «старт-старт»  определяет  минимальную  задержку  между  началом  двух  операций.  Одной  из  задач  является  нахождение  такого  плана  проекта,  который  обеспечивает  одно  общее  время  завершения  для  всех  операций,  не  нарушая  условий  на  порядок  их  выполнения.

Для  каждой  задачи  в  проекте  i  =  1,…,n,  обозначим  через  x_i  —  время  начала,  y_i  —  время  завершения.  Пусть  a_ij  —  будет  минимально  возможная  задержка  между  началом  задач  j  =  1,…,n  и  завершением  i.  Ограничения  типа  «старт-финиш»  записываются  в  виде  неравенств:

при  этом  хотя  бы  одно  неравенство  должно  выполняться  как  равенство.  Заметим,  что  мы  подразумеваем    для  любого  i.  Если  для  некоторого  j  значение  c_ij  не  задано,  то  полагаем  .  Теперь  мы  объединим  все  эти  отношения  в  одно  равенство  вида

Кроме  того,  пусть  c_ij  будет  минимально  возможной  задержкой  между  началом  задач  j  и  i.  Будем  снова  считать,  что  ,  если  не  определена  задержка  между  j  и  i.  Запись  ограничения  «старт-старт»  выглядит  так

Далее  можно  переписать  как  одно  неравенство

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

Теперь  мы  можем  сформулировать  задачу  оптимизации,  в  следующем  виде

Далее  будет  показано,  как  задача    (6)  может  быть  представлена  в  терминах  тропической  (идемпотентной)  математики  и  полностью  решена  в  компактной  векторной  форме.

2     Принятые  обозначения  и  определения 

2.1                 Идемпотентное  полуполе 

Пусть    —  множество,  замкнутое  относительно  двух  ассоциативных  и  коммутативных  операций:  сложения    и  умножения  ,  с  нейтральными  элементами:  нулем    и  единицей  .  Сложение  идемпотентно,  что  означает    для  любого  .  Умножение  дистрибутивно  относительно  сложения  и  обратимо,  то  есть,  для  любого  ,  где  есть  обратное  число    ,  которое  удовлетворяет  равенству  .  Таким  образом    образует  группу  по  умножению,  и  структура  (;  ;  ;  ;)  является  идемпотентным  полуполем.

Возведение  в  целую  степень  определяется  как  обычно.  Для  любого  и  целого  p  >  0,  можно  записать  x⁰  =  ;    ^p  =  ;  =    ,  и    =  ()^p  .

Далее  для  краткости  не  будем  указывать  знак  умножения  ,  как  и  в  обычной  математике.

Отметим,  что  идемпотентное  сложение  порождает  частичный  порядок  ≤,  такой,  что    только  в  том  случае,  если  .  Предполагается,  что  этот  частичный  порядок  можно  расширить  до  полного  порядка  на  всем  .  Далее  символы  отношений  и  формулировки  задач  оптимизации  рассматриваются  в  контексте  этого  порядка.

Например,  полуполе  R_maz;+  имеет  =  max  и    =  +,  а  так  же  нуль    =  1  и  единицу    =  0.  Для  любого    существует  обратный  элемент    ,  который  в  обычных  обозначениях  совпадает  с  .  Для  любого  ,  ,  степень    соответствует  арифметическому  произведению  .  Порядок,  порожденный  идемпотентным  сложением,  соответствует  естественному  линейному  порядку  на  R.

2.2                 Алгебра  матриц 

Теперь  рассмотрим  матрицы  над    и  обозначим  множество  матриц  с  m  строками  и  n  столбцами,  как    .  Матрица,  в  которой  все  элементы  равны  ,  называется  нулевой.  Матрица  регулярна  по  строкам  (столбцам),  если  она  не  имеет  нулевых  строк  (столбцов).  Матрица  регулярна,  если  она  регулярна  и  по  строкам  и  по  столбцам.

Для  любых  матриц  подходящего  размераи  скаляра  x,  матричное  сложение  и  умножение,  а  также  умножение  на  скаляр  определяется  как

Для  любой  матрицы  ,  её  транспонированная  обозначается  ^T.  Для  любой  ненулевой  матрицы    =  (,  введем  мультипликативно-сопряженную  (или  просто  сопряженную)  матрицу    с  элементами    если  ,  и    в  противном  случае,  для  любого    и  .

Рассмотрим  множество  квадратных  матриц    .  Матрица,  которая  на  диагонали  имеет    и  вне  диагонали  —  ,  называется  единичной  и  обозначается  I.

Как  обычно,  матрица,  которая  состоит  их  одной  строки  (столбца)  называется  строчным  (столбцевым)  вектором.  Обозначим  множество  столбцевых  векторов  порядка  n  как  .

Вектор,  у  которого  все  компоненты  равны  ,  называется  нулевым.  Вектор  считается  регулярным,  если  у  него  нет  нулевых  элементов.

Пусть  x  —  регулярный  вектор-столбец  и    —  матрица.  Не  трудно  заметить,  что  вектор    регулярен  только  тогда,  когда  матрица    регулярна  по  строкам.  Точно  так  же  вектор-строка  ^T    регулярен  только  тогда,  когда  матрица    регулярна  по  столбцам.

Как  обычно  вектор    линейно  зависим  от  векторов  ,  если  найдутся  скаляры    такие,  что    .  Вектор  y  коллинеарен  вектору  x,  если  y  =  cx  для  какого-нибудь  скаляра  c.

Для  любого  ненулевого  вектора,  его  мультипликативно-сопряженный  вектор  —  это  строчный  вектор  ,  где    если    и    в  противном  случае.  Нетрудно  проверить  следующие  свойства  мультипликативно-сопряженных  векторов.

Для  любых  двух  регулярных  векторов    и    одинакового  размера,  покомпонентное  неравенство    подразумевает    и  наоборот.

Для  любого  ненулевого  вектора  выполняется  .  Кроме  того,  если  вектор  регулярен,  то  .

3     Представление  задачи  планирования  в  терминах  тропической  математики 

3.1                 Минимальное  общее  время  (makespan) 

Минимальное  общее  время  выполнения  проекта  [1]  вычисляется  как  разность  между  временем  начала  самой  ранней  операции  проекта  и  временем  завершения  самой  поздней  операции.  Если  рассматривать  множество  работ  на  множестве  машин  для  выполнения  (при  условии,  что  каждая  машина  может  выполнять  только  одну  операцию  в  данный  момент  времени),  то  задача  представляет  собой  задачу  динамического  программирования.  При  отстранении  от  условий  связанных  с  ресурсами  можно  получить  описание  задачи  в  терминах  тропической  алгебры:

После  подстановки    из  (2)  проблему  можно  сформулировать

В  терминах  полуполя  R_max;+  задача  принимает  такой  вид:

Теперь,  введем  матрицу    =  ()  и  вектор    =  ().  В  этой  нотации,  задача  в  векторной  форме  выглядит  как:

Эта  проблема  рассматривается  в  [4]  в  теоремах  3  и  4.  Как  следствие  этих  двух  теорем  имеем  дальнейший  результат.

Теорема  1 .  Пусть  C  —  регулярная  по  строкам  матрица,  и

Тогда,  минимум  в  задаче    (10)  равен  и  достигается  при

или,  что  эквивалентно,  если

3.2                 Минимальное  отклонение  от  директивных  сроков 

Пусть  для  всех  работ  заданы  директивные  сроки  завершения  их  выполнения.  Найдем  сроки  начала  работ,  при  которых  время  завершения  совпадает  с  директивными  сроками.  Если  такие  сроки  начала  работ  определить  невозможно,  то  следует  найти  приближенные  решения  задачи,  которые  являются  оптимальными  с  точки  зрения  минимального  нарушения  директивных  сроков.  Обозначим  через  вектор  директивных  сроков  завершения  работ.  Тогда  рассматриваемая  задача  планирования  сводится  к  исследованию  в  полукольце  R_max;+  уравнения:

Наилучшее  приближение  к  решению  уравнения  находится  как  решение  задачи

Обозначив  через  ,  рассмотрим  случай  равенства  .  Если  равенство  выполняется,  решение  уравнения  существует  [5].  Решение  имеет  вид    и  задает  время  начала  работ,  которое  обеспечивает  выполнение  директивных  сроков  завершения  работ.

Если  же    то  решением  будет

приближенные  сроки  вычисляются  по  формуле

отклонение  в  этом  случае  от  директивных  сроков  запишется  в  виде

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

Список  литературы:

1.Demeulemeester  E.L.  and  W.S.  Herroelen,  “Project  Scheduling:  A  Research  Handbook",  Springer,  Berlin,  2002. 

2.Krivulin  N.K.,  “Explicit  solution  of  a  tropical  optimization  problem  with  application  to  project  scheduling  in  Mathematical  Methods  and  Optimization  Techniques  in  Engineering,”  WSEAS  Press,  arXiv:1303.5457  [math.OC],  2013.

3.Krivulin  N.K.,“A  maximization  problem  in  tropical  mathematics:  A  complete  solution  and  application  examples",arXiv:1304.7461  [math.OC],  2013.

4.Krivulin  N.K.,  “A  Tropical  Optimization  Problem  with  Application  to  Project  Scheduling  with  Minimum  Makespan”,  WSEAS  Press.  arXiv:1403.0268  [math.OC],  2013. 

5.Krivulin  N.K.,  “Methods  of  Idempotent  Algebra  in  Problems  of  Complex  Systems  Modeling  and  Analysis.”  St.  Petersburg:  St.  Petersburg  University  Press,  2009.  (in  Russian) 

6.Krivulin  N.,  “A  solution  of  a  tropical  linear  vector  equation,”  in  Advances  in  Computer  Science:  Proc.  6th  WSEAS  European  Computing  Conf.,  WSEAS  Press,  2012,  —  pp.  244—249. 

7.Nikhil  Bansal,  “Algorithms  for  Flow  Time  Scheduling",  Carnegie  Mellon  University  Pittsburgh,  2003.

8.T’kindt  V.  and  J.-C.  Billaut,  “Multicriteria  Scheduling:  Theory,  Models  and  Algorithms,”  Springer,  Berlin,  2006.