А.В. Катаев Т.М. Катаева
Управление проектами на базе динамической сети партнеров. Монография.

Предыдущая

Оглавление

Следующая

3.5. Модель построения оптимального расписания работ проекта

Одной из основных и наиболее сложных задач оптимизации проекта различными исследователями рассматривается задача RCPSP (Resource-Constrained Project Scheduling Problem)  – построение оптимального расписания выполнения работ проекта с учетом отношений предшествования между работами и с учетом необходимых и (или) доступных ресурсов, при котором будет оптимизирована некоторая целевая функция (например, минимизирование длительности выполнения проекта). Задача RCPSP является экстремально NP-трудной[1].
По задаче RCPSP регулярно публикуются интегрированные обзоры наиболее значимых результатов[2]. Для тестирования и сравнения многочисленных алгоритмов решения задачи RCPSP создана библиотека тестовых примеров PSPLIB[3]. Наиболее быстрым на данный момент точным алгоритмом признан алгоритм ветвей и границ Брукера[4]. Среди метаэвристических алгоритмов стоит выделить алгоритм муравьиной колонии для решения задачи RCPSP[5].
Алгоритмы решения этой задачи используются в известных программных продуктах Spyder Project, Primavera, Microsoft Project, 1С: Управление Строительной Организацией и т.д.
Постановка задачи RCPSP выглядит следующим образом:
Дано множество работ N = {1, . . ., n} и K возобновляемых ресурсов k = 1,…,K. В каждый момент времени t доступно Qk единиц ресурса k. Заданы длительности выполнения pi ≥ 0 для каждой работы i = 1,…, n. Во время выполнения работы i требуется qik ≤ Qk единиц ресурса k. После завершения работы, освобожденные ресурсы в полном объеме могут быть мгновенно назначены на другие работы.
Между некоторыми парами работ заданы ограничения предшествования: i → j означает, что работа j может начаться  не раньше окончания выполнения работы i.
Проект начинается в момент времени t = 0. Прерывание выполнения работ запрещены, т.е. нельзя остановить выполнение любой работы и продолжить через определенное время.
Требуется определить моменты времени начала выполнения работ Si, i = 1,…, n, так, чтобы минимизировать время выполнения всего проекта, т.е. минимизировать значение

2) не нарушаются отношения предшествования между работами, т.е. Si + pi ≤ Sj , если i → j для i, j ∈ N.
В англоязычной литературе Cmax называется makespan.
Необходимо заметить, что существует класс задач RCPSP с невозобновимыми ресурсами, например финансовые средства, сырье и т.п.
Решение задачи RCPSP представляется в виде набора моментов времени, с которых  начинаются выполнения работ S = (S1, . . . , Sn). Допустимым является решение, при котором удовлетворяются все ресурсные ограничения и ограничения предшествования.
Структуру проекта, его работы и взаимосвязь между ними можно представить в виде сетевого графика, в котором в вершинах располагаются работы. Тогда сетевой график представляет собой ориентированный графа G = (V,E), где каждой вершине из V = {1,…. n} соответствует некоторая работа множества N = {1,…. n}, а множество дуг E = {(i, j)|i, j ∈V ; i → j} соответствует ограничениям предшествования.
Как правило, в модель включают две фиктивные работы 0 и n + 1 c длительностями выполнения  p0 = pn+1 = 0 и отношениями предшествования 0 → j → n + 1, j = 1, . . ., n, q0k = qn+1k= 0, k = 1,…, K.
Особенности и расширения задачи RCPSP
На практике задача RCPSP обладает рядом отличий от математической модели. Далее приведены некоторые возможные отличия на примере практической задачи RPCPS, возникающей в строительстве[6].
• Основные типы работ:
– работа с фиксированной продолжительностью, т.е. классический тип работы, важнейшей характеристикой которой является продолжительность ее выполнения;
– контрольное событие, т.е. работа с нулевой продолжительностью, представляющая, например, результат предыдущих работ;
– гамак, т.е. работа, не имеющая фиксированную продолжительность и выполняющаяся между моментами времени окончания работ-предшественников и началом работ-последователей;
• Продолжительность. Задается в днях или часах. На практике редко планирование ведется в меньших единицах времени. Очевидно, что продолжительность может зависеть от интенсивности работы (т.е. от количества и качества привлеченных ресурсов);
• Невозобновимые ресурсы. Некоторые ограничения на допустимые расписания могут задавать невозобновимые ресурсы, которые необходимы для выполнения работ. Например, материалы, топливо и т.п.;
• Возобновимые ресурсы. Техника, персонал. Ресурсы могут объединяться в группы, которые выступают неделимым ресурсом. Зачастую у разных ресурсов, задействованных на работе, бывает разный график доступности. Это необходимо учитывать при составлении календарного плана проекта;
• График работы. Разные работы могут выполняться с разным графиком (по времени суток, дням недели и т.п.).
• Ограничение на время выполнения. Параметр принимает значения «Как можно раньше», «Как можно позже», «Фиксированная дата», «Начало не позже», «Начало не раньше».
Характеристики взаимосвязей между работами также могут отличаться. Обычной является взаимосвязь типа «Окончание-Начало», то есть работа-последователь может начаться не раньше, чем закончится работа-предшественник. Часто на практике требуется учесть связи «Начало-Начало» (когда работа-последователь не может начаться раньше, чем начнется работа-предшественник), «Окончание-Окончание», «Начало-Окончание». Более того, по технологии между окончанием работы-предшественника и началом работы-последователя может быть задана задержка по времени.
Некоторые из перечисленных особенностей могут быть включены в математическую модель RCPSP в качестве дополнительных условий. В этом случае говорят о задаче RCPSP в расширенной постановке.
В тех случаях, когда количество возобновимого ресурса k зависит от времени, вместо константы Qk вводится функция от времени Qk(t). Значения такой функции могут задаваться в табличном виде. Например, с 1-го по 10-е марта доступно 3 программиста. С 11-го по 15-е – 2 программиста и т.п.;
Продолжительность работы может зависеть от количества занятых на ней ресурсов. Очевидно, что если на выполнение работы назначить больше исполнителей, то работа может быть выполнена быстрее. Для каждой работы могут быть заданы фиксированные варианты выполнения. Например, «Вариант 1: продолжительность = 4 дня, необходимо 2 автомобиля и 3 промоутера», «Вариант 2: продолжительность = 7 дней, необходимо 0 автомобилей и 6 промоутеров» и т.д. Задачу RPCSP в такой постановке называют мультимодальной и обозначают MRCPSP. В такой постановке сначала требуется определить вариант, по которому будет выполняться работа, и уже затем определять время ее начала с учетом наличия ресурсов.

Алгоритм диспетчеризации для задачи RCPSP
Ниже приведен известный алгоритм List Scheduling (LS), предназначенный для нахождения допустимого расписания выполнения работ проекта:
1: EL – список всех работ без предшественников. Полагаем Qk(τ) =Qk, ∀τ, k = 1,… ,K.
2: Цикл, пока EL не пустое.
3: Выбор работы j ∈ EL.
4: Если для работы j предшественники не определены, тогда t = 0, в противном случае t= max {Si+ pi}  (максимальный из всех входящих путей).
5: Цикл, пока существует такой ресурс k, что qjk > Qk(τ ) для некоторого τ ∈[t, t+pj).
6: Вычисляем такое минимальное значение tk> t, что работа j может быть начата и выполнена в интервале [tk, tk+pj), если рассматривается только ресурс k.
7: t = tk.
8: Конец цикла 5.
9: Назначаем выполнение работы j на интервал [Sj, Sj + pj) = [t, t + pj).
10: Резервируем ресурсы на выполнение работы j:
Qk(τ) = Qk(τ ) − qjk, k =1,… , K, τ ∈[t, t + pj).
11: Исключаем работуjиз спискаEL.
12: Добавляем в EL последователей работы j, для которых все предшественники поставлены в расписание.
13: Конец цикла 2.

Полученное расписание зависит от выбора работы j на шаге 3 алгоритма LS. Идея данного алгоритма заключается в том, что работа j ставится в расписание с наиболее раннего момента времени, при котором не нарушаются ресурсные ограничения и ограничения предшествования. Трудоемкость алгоритма O(n2K) операций.
Алгоритмом LS строятся только активные расписания, причем оптимальное расписание следует искать среди множества активных. Активным же называют такое допустимое решение S = (S1, …, Sn), для которого не существует другого допустимого расписания S’ = (S’1,… , S’n) такого, что S’j≤ Sj, ∀j ∈ N, и хотя бы одно из неравенств строгое.
При поочередной перестановке выбираемых работ на шаге 3 алгоритма LS возможно получить оптимальное расписание. Подобные алгоритмы зачастую называют «конкурсами» по той причине, что работа на шаге 3 может выбираться согласно некоторому «приоритету», конкурсу.
Ключевой составляющей алгоритма LS является правило предпочтения, с помощью которого выбирается требование  j ∈ ELдля постановки в расписание на шаге 3 алгоритма. Существует ряд элементарных эвристических правил предпочтения (правил диспетчеризации), которые основываются на следующей информации:
-  длительность работ (например, «выбрать работу с наименьшей длительностью выполнения»);
- отношения предшествования (например, «выбрать работу с наибольшим количеством непосредственных последователей»);
- необходимые ресурсы (например, «выбрать работу с наибольшей потребностью в ресурсах»).
Подбор правил предпочтения в алгоритме LS может помочь найти близкое к оптимальному решение, но не гарантирует этого. На основании данного алгоритма диспетчеризации можно построить точный алгоритм «ветвей и границ». Однако лучший из известных точных алгоритмов Брукера[7] за приемлемое время может решать задачи размерности не больше n = 60. Более того, даже для частного случая с одним невозобновимым ресурсом K = 1 неизвестны полиномиальные алгоритмы решения с относительной погрешностью, гарантированно не превосходящей некоторой константы[8].
Выводы
Коллективом авторов был разработан комплекс моделей и методов формирования партнерской сети как единой проектной команды. Среди наиболее значимых научных результатов проведенного исследования в данной работе нашли подробное описание следующие из них:
1. Разработана оптимизационная модель формирования ядра (группы постоянных участников) динамической партнерской сети, позволяющая минимизировать количество партнеров, входящих в состав предприятия на регулярной основе, а также учесть ряд дополнительных ограничение, таких как:

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

Практический пример использования данной модели, который наглядно демонстрирует возможность ее эффективного использования, в том числе при автоматизации процедур поддержки принятия управленческих  решений по формированию долгосрочных виртуальных предприятий для реализации проектов различной направленности и уровня сложности. Следует также обратить внимание, что использование предложенного инструментария требует первоначальной тщательной проработки бизнес-модели виртуального предприятия особенно в части детализации требуемых ключевых компетенций, а также выявлении тех компетенций, которые уже имеются у потенциальных участников динамической партнерской сети. Возможность описания в математической модели взаимосвязей партнеров друг с другом позволяет при формировании ядра учесть предыдущий положительный и отрицательный опыт взаимодействия агентов, что способствует осуществлению на практике быстрого перехода от этапа формирования сети к ее эффективному функционированию и снижению вероятности возникновения конфликтных ситуаций.
2. Проведен аналитический обзор наиболее распространенных и проработанных в теории исследования операций и дискретной математики задач оптимального выбора и назначения исполнителей на выполнения основных работ по проекту, а также методы их решения.
3. Разработана оптимизационная модель целочисленного математического программирования, постановка которой особенно актуальна в условиях необходимости снижения операционных и транзакционных издержек и может быть обусловлена потребностью упростить контроль и повысить управляемость выполнением проекта. Нелинейность целевой функции в данной модели не позволяет найти оптимальное решение точными методами линейного программирования, включая симплекс-метод. В связи с чем авторами данного исследования был разработан пошаговый эвристический алгоритм поиска оптимального решения и численный пример его реализации, что позволяет на практике за приемлемое время найти близкое к оптимальному решение без применения специализированного программного обеспечения.
4. Приведена базовая постановка задачи оптимального выбора и назначения основных исполнителей на выполнение работ по проекту, позволяющая учесть взаимосвязь работ во времени, где в качестве критерия оптимизации выступает стоимость основных работ по проекту. Приведены также другие возможные критерии оптимизации.
Рассмотрены также другие постановки задач с различными целевыми функциями и рядом существенных ограничивающих условий, среди которых подробное содержательное и формальное описание получили следующие:
1) доступный период времени, когда исполнитель готов выполнить работу;
2) запреты назначения того или иного исполнителя на конкретную работу, выдвигаемые со стороны менеджера проекта;
3) предпочтение выбора определенного исполнителя для выполнения конкретных работ;
4) «связка» работ при назначении, когда требуется отдать несколько определенных работ «в одни руки»;
5) невозможность параллельного выполнения работ исполнителем;
6) ограничения по компетенции и надежности исполнителей;
7) учет конфликтов между потенциальными партнерами;
8) учет прежнего опыта сотрудничества партнеров друг с другом.
5. Приведена математическая постановка задачи, заключающейся в построении оптимального расписания выполнения работ проекта с учетом отношений предшествования между работами и с учетом необходимых и (или) доступных ресурсов. Дан обзор точных и приближенных методов решения данной задачи, включая алгоритм List Scheduling и др.

 

Предыдущая

Оглавление

Следующая