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

Селищев Иван Алексеевич аспирант, кафедра Автоматизированных вычислительных систем, Воронежский Государственный Технический Университет 394068, Россия, Воронежская область, г. Воронеж, ул. Московский Проспект, 14 Selishchev Ivan Alekseevich Postgraduate student, the department of Automated Computational Systems, Voronezh State Technical University 394068, Russia, Voronezhskaya oblast', g. Voronezh, ul. Moskovskii Prospekt, 14 selishcheviv@gmail.com Другие публикации этого автора

Олейникова Светлана Александровна доктор технических наук профессор, Воронежский государственный технический университет 394026, Россия, Воронежская область, г. Воронеж, ул. Московский Проспект, 14 Oleinikova Svetlana Aleksandrovna Doctor of Technical Science Professor, Voronezh State Technical University 394026, Russia, Voronezhskaya oblast', g. Voronezh, ul. Moskovskii Prospekt, 14 s.a.oleynikova@gmail.com Другие публикации этого автора

Введение

Одной из важнейших задач, подлежащей решению при управлении многостадийными стохастическими системами является задача определения времени начала выполнения каждой из множества взаимосвязанных работ, а также исполнителей, которые будут выполнять данные работы. Специфика определения сроков выполнения работ широко изучена в методах сетевого планирования и управления и в методах управления проектами ^{[1, 2, 3, 4, 6, 7, 8]}. В частности, существуют алгоритмы, позволяющие определять критический путь проекта, оценивать случайные величины, описывающие длительности отдельных работ, планировать множество работ в соответствии с имеющимися ресурсными ограничениями и т.д.

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

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

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

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

1. Постановка задачи и анализ существующих подходов к ее решению

Рассматривается многостадийная стохастическая система, функционирование которой заключается в выполнении множества взаимно-зависимых работ. Часть работ может выполняться параллельно, между другими существует зависимость типа «финиш»-«старт». Длительность каждой отдельной операции является случайной величиной, которая зависит, кроме различных случайных факторов, также от исполнителя. Кроме того, выполнение работы может потребовать одного или нескольких «типов» ресурсов (специалистов, оборудования и т.д.). В зависимости от выбора ресурса (исполнителя, материалов и т.д.) работа может быть выполнена с разной степенью эффективности и за разное время. Завершение обслуживания заявки приносит определенный объем прибыли, которая зависит от качества выполнения работы, наличия или отсутствия штрафных санкций и т.д. Необходимо для каждой поступающей заявки подобрать такой график обслуживания и такие ресурсы для каждой работы, чтобы итоговая прибыль была бы максимальна.

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

В частности, задача формирования графика обслуживания относится к классу задач управления проектами ^[1]. Подробный анализ существующих подходов и методов в данной области представлен в ^[2]. В основе большинства алгоритмов решения данной задачи лежит метод критического пути, позволяющий сформировать график работ с постоянными длительностями без учета ресурсов ^[6]. В случае, если длительности работ являются случайными величинами, используется метод PERT, позволяющий оценить эти величины на основании наименьшего, наибольшего и наиболее вероятного значений ^{[7, 8]}. Существуют также алгоритмы, позволяющие формировать график в условиях ресурсных ограничений ^[4].

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

Закрепление ресурсов за работами или установка соответствия между исполнителями и работами является предметом задачи о назначениях ^{[5, 9, 10]}. Классическая постановка данной задачи не вызывает сложностей при решении. Она требует определить соответствие между n работами и n исполнителями. В частности, широко известен венгерский метод, который лучше всего подходит для ее решения. Тем не менее, задача о назначениях может быть решена любыми методами, используемыми для поиска решений транспортной задачи, поскольку является ее частным случаем. Более подробно методы ее решения представлены в ^[9]. Обобщение классической задачи о назначениях заключается в отсутствии равенства между числом исполнителей и работ. Если при этом добавляются разного рода ограничения, то задача становится NP-трудной и требует разработки приближенных методов ее решения. В частности, один из таких аппроксимационных алгоритмов, основанный на локальном поиске, представлен в ^[5].

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

2. Математическая модель задачи

Опишем данную задачу математически. Введем следующие обозначения.

Пусть каждая заявка Zi характеризуется:

- прибылью ci, получаемой в случае ее выполнения в срок;

- директивным сроком ее исполнения Ti;

- штрафными санкциями pi(t) в случае ее задержки.

Кроме того, заявка i определяется множеством работ Wi.

(1)

Рассмотрим специфику работы j для заявки i. В дальнейшем опустим индекс, определяющий непосредственно заявку и будем фиксировать лишь ее работы. Каждая работа wj характеризуется:

- временем начала tнач(wj);

- длительностью

- множеством работ, которые непосредственно предшествуют данной работе: Pj=P(wj).

Будем различать ресурсы типа «исполнитель» и другие ресурсы (например, оборудование). Пусть имеется N специализаций исполнителей S1,…, SN и K типов остальных ресурсов: R1, R2,…, RK. Без ограничения общности рассмотрим случай, когда для работы wij нужны лишь специалисты определенной специальности. Предполагается, что для каждой работы wj необходим некоторый исполнитель и массив (resj_1, resj_2,…,resj_K), который описывает потребность в каждом виде ресурсов. Пусть время выполнения tj любой работы wj зависит от исполнителя, который ее выполняет

(2)

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

Как и для постановки классической задачи о назначениях, для определения соответствия исполнителей и работ, введем в рассмотрение матрицу x, каждый элемент xkj которой будет определять выполнение данным исполнителем данной работы. Однако, в отличие от классической задачи, данная матрица будет зависеть от времени. Каждый ее элемент будет определяться следующим образом:

(3)

Опишем также выбор оборудования для выполнения работы следующим образом:

(4)

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

(5)

Выражение (5) показывает невозможность ни одному из исполнителей ни в один из моментов времени t исполнять более одной работы. Ограничение (6) показывает, что работу j должен выполнить ровно один исполнитель.

(6)

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

(7)

Формула (7) справедлива для всех типов оборудования 1,…,K и для всех моментов времени t.

Предполагается, что имеется некоторое расписание занятости каждого из ресурсов Sh_r(t) и исполнителей Sh_s(t), полученное к моменту времени t.

Необходимо для пришедшей заявки:

- определить исполнителей на каждую ее работу: s(wj);

- время начала каждой работы tнач(wj).

Рассмотрим каждый из этих показателей. Необходимо найти следующие

(8)

(9)

Здесь ci – прибыль от выполнения заявки i; ri – штраф за несвоевременное выполнение заявки i; Tfin_i – фактическое время завершения обслуживания заявки i; Ti – директивный срок завершения обслуживания данной заявки.

Определим прибыль за выполнение заявки i как сумму отдельных прибылей за выполнение отдельных работ.

(10)

Здесь cij – это прибыль, полученная от выполнения работы j исполнителем k.

Как было отмечено ранее, задача поиска времени начала работ относится к задачам управления проектами. Для ее решения необходимо рассчитать такие временные характеристики, как раннее, позднее время начала работ и временной резерв. Эти характеристики рассчитываются следующим образом:

(11)

Здесь tj – длительность выполнения работы j, а - время раннего его начала. После нахождения времени начала всех работ можно определить время завершения заявки Tfin. Оно будет рассчитываться следующим образом:

(12)

Отличие от формулы (11) заключается в том, что максимум определяется по всем работам, а не по тем, которые предшествуют данной работе.

Поздние моменты определяются, начиная с финальных работ, заканчивая начальными:

(13)

Ключевым моментом решения задачи поиска времени начала работ с ресурсными ограничениями является приоритизация работ по временном резерву, которые определяется формулой:

(14)

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

Общий подход к решению задачи

Как было отмечено ранее, основной сложностью в данной задаче является то, что резерв в данном случае точно рассчитать невозможно, поскольку все временные характеристики будут зависеть от исполнителей. В связи с этим, основная сложность задачи возникает в определении среди множества работ Wdop(t), которые можно начать в момент времени t, подмножества Wфакт(t), содержащего те работы, у которых время начала равно t. Предположим, что некоторым образом работы приоритизированы, на основании чего определено множество Wфакт(t) тех работ, которые должны начаться в данное время.

После этого для данного множества решить задачу о назначениях, т.е. определить исполнителей на данное множество работ. Общая схема алгоритма представлена на рис.1.

Рис. 1 – Общая схема алгоритма

Таким образом, основная сложность заключается в приоритизации работ и выявлении множества Wфакт(t) из множества работ Wdop(t). Для этого каким-либо образом необходимо оценить временные характеристики работ:

- ее длительность;

- ее резерв.

Ориентировочную длительность работ можно определить, исходя из значений по каждому исполнителю. Пусть работу j могут делать исполнители k1,…, kj. Тогда примерная длительность работы будет определяться формулой:

(15)

Здесь , …, - ориентировочные длительности выполнения работы j исполнителям1,…, kj соответственно; kj – количество исполнителей. Для случайных величин в качестве оценки длительности можно использовать метод PERT. В частности, для оценки времени выполнения специалистом K работы j будем иметь []:

(16)

Здесь ak – оптимистичное время выполнения операции специалистом K; mk – наиболее вероятное время выполнения данным специалистом; bk – пессимистическое время выполнения работы специалистом K ^[7].

Ориентировочные временные характеристики работ будем рассчитывать по формулам (11)-(14), где в качестве длительности изначально используются значения (15).

Эти значения изначально будут весьма грубыми, поэтому, в связи с отсутствием более точной информации, для оценки временных характеристик будем использовать метод набегающей волны ^[4]. Его суть заключается в том, что планирование осуществляется волнами или этапами, и существует возможность детально описать характеристики лишь ближайшего (или нескольких ближайших) этапа, а специфика более поздних этапов будет определена позднее. Это существенно сократит сроки на решение данной NP-трудной задачи.

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

(17)

Здесь tтек – текущий момент времени; Wфакт(t) – множество работ, начало которых запланировано на время t; tj_план – запланированная длительность данных работ в результате решения задачи о назначениях.

К моменту tслед все исполнители работ, принадлежащих множеству Wфакт(t) (кроме самой быстрой с точки зрения исполнения работы) будут заняты. Кроме того, будут заняты соответствующие ресурсы (оборудование, инструменты и т.д.). Следовательно, при планировании на следующем временном интервале на множество ресурсов уже будет наложено ограничение. В связи с этим, к данному этапу можно уточнить множество работ, которые можно выполнить из-за свободности ресурсов, а также длительности этих работ. Для этого будет использована также формула (13), только множество исполнителей уже будет более узким. После этого необходимо уточнить временные характеристики (ориентировочное возможное время начала и резерв) оставшихся работ. После этого можно перейти к следующему этапу планирования.

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

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

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

Выводы

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

1. Математическая модель системы, отличающаяся учетом длительности работ в зависимости от используемых ресурсов

2. Оптимизационная задача, позволяющая определить наилучшее время начала работ и соответствующих исполнителей.

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