ФОРМИРОВАНИЕ РАСПИСАНИЙ В СИСТЕМАХ УПРАВЛЕНИЯ МУЛЬТИПРОЕКТНЫМИ РАЗРАБОТКАМИ
Авторы:
1.
Сибирский государственный индустриальный университет
(старший преподаватель кафедры автоматизации и информационных систем )
Россия
Россия
2.
Сибирский государственный индустриальный университет
(д-р техн. наук, профессор; профессор кафедры автоматизации и информационных систем )
3.
Сибирский государственный индустриальный университет
(старший преподаватель кафедры автоматизации и информационных систем; ведущий специалист по информатизации отдела системных и сетевых технологий )
Тип:
Статья
Страницы:
с 105
по 114
Статус:
Опубликован
Получено:
23.07.2021
Одобрено:
07.01.2023
Опубликовано:
26.07.2021
Классификаторы:
УДК 50 Общие вопросы математических и естественных наук
Язык материала:
русский
Ключевые слова:
построение расписаний, мультипроектное планирование, орграф, мультиграф, домен, кластеризация
Аннотация (русский):
Современный математический аппарат, а также достижения в области системного анализа, теории игр, теории графов позволяют алгоритмизировать процесс решения задачи составления расписаний для различных сфер человеческой деятельности. На сегодняшний день проанализированы и определены области эффективного применения многих известных, в том числе современных эвристических и метаэвристических, алгоритмов, показавших неплохие результаты на практике. Однако несмотря на имеющиеся достижения в области дискретной оптимизации, календарного и сетевого планирования, по-прежнему представляют практический интерес новые задачи составления так называемых согласованных расписаний в области мультипроектного планирования, в которых учитываются предпочтения (заявки, пожелания) конкретных исполнителей расписаний. Рассмотрены подходы и основные этапы решения задач построения согласованных расписаний при мультипроектном планировании, что является актуальным для разработки программно-инструментальных средств нового поколения
Современный математический аппарат, а также достижения в области системного анализа, теории игр, теории графов позволяют алгоритмизировать процесс решения задачи составления расписаний для различных сфер человеческой деятельности. На сегодняшний день проанализированы и определены области эффективного применения многих известных, в том числе современных эвристических и метаэвристических, алгоритмов, показавших неплохие результаты на практике. Однако несмотря на имеющиеся достижения в области дискретной оптимизации, календарного и сетевого планирования, по-прежнему представляют практический интерес новые задачи составления так называемых согласованных расписаний в области мультипроектного планирования, в которых учитываются предпочтения (заявки, пожелания) конкретных исполнителей расписаний. Рассмотрены подходы и основные этапы решения задач построения согласованных расписаний при мультипроектном планировании, что является актуальным для разработки программно-инструментальных средств нового поколения
Ключевые слова:
построение расписаний, мультипроектное планирование, орграф, мультиграф, домен, кластеризация
построение расписаний, мультипроектное планирование, орграф, мультиграф, домен, кластеризация
Введение
В статье рассматриваются теоретические и прикладные аспекты управления мультипроектными разработками. Предложенные подходы могут быть использованы для создания инструментальных информационных систем нового поколения, систем управления проектами, которые отличаются более сложными подходами к управлению по сравнению с известными
и широко распространенными WBS (Work Breakdown System) моделями.
Рассматриваемые в статье подходы частично опираются на некоторые методы календарного, сетевого планирования [1, 2], часть из них достаточно хорошо изучены, некоторые используемые на практике алгоритмы имеют доказанную теоретическую эффективность, что позволяет решать реальные практические задачи в автоматическом режиме. Особый интерес представляет создание прикладных инструментальных средств для различных или однотипных проектных групп, работающих одновременно (параллельно) с несколькими проектами. В настоящее время на рынке отсутствуют развитые комплексы построения расписаний для мультипроектного планирования, что связано, во-первых, со сложностью таких систем, во-вторых, с отсутствием целостного представления об их работе.
Обоснование применения модели мультиграфа в задаче мультипроектного календарного планирования
Представленные на рынке современные инструментальные средства поддержки проектной деятельности в значительной степени являются аналогами известной системы MS Project, разработанной компанией Microsoft, и реализуют схожие по своей природе модели, методы
и алгоритмы. Анализируя такие системы, можно сделать ряд интересных выводов. К примеру, некоторые продукты используют иерархические модели укрупненных задач, этапов проекта без учета того, что проекты могут выполняться одновременно или параллельно. Также не учитываются предпочтения (пожелания, заявки) исполнителей, что не позволяет строить согласованные расписания в автоматическом режиме. Подавляющее большинство известных современных инструментальных средств построения расписаний для проектной деятельности использует достаточно распространенные декомпозиционные подходы, очень часто – иерархическую модель WBS (Work Breakdown Structure). Такие инструменты прекрасно совместимы с SADT и IDEF0, однако не учитывают ряд важнейших особенностей.
Представим гипотетически, что процессы или реальные прикладные работы проектной деятельности описываются на языке SADT, что является общепринятой практикой. Тогда прикладная реализация инструментального средства построения расписания на языке программирования высокого уровня может быть основана на идеях рекурсивной иерархической декомпозиции Джона Маккарти, Ричарда Беллмана [3, 4], Джексона [5], Лестера Форда, Флойда и других исследователей. Но в реальности почти всегда все значительно сложнее. Мы не можем гарантировать, что реальная проектная деятельность будет такая же, как в модели SADT. Вынуждены с сожалением констатировать очевидный факт: любые иерархические модели являются слишком ограниченными для использования в задачах сетевого и календарного планирования. Они не адекватны для решения реальных задач.
Рассмотрим сетевой график , в котором множество проектных работ (процессов) ассоциированы с дугами (связями) орграфа и соответствующими событиями , каждое из которых описывает окончание определенного укрупненного этапа проекта x. Очевидное преимущество такой сетевой модели перед вышеназванной иерархической заключается в дополнительной гибкости, поскольку каждый следующий уровень в древовидной иерархии всегда имеет единственный корень. Таким образом, некоторое событие vx может агрегировать конкретные достигнутые результаты, полученные на множествах выполненных ранее параллельных работ , чего в принципе невозможно достичь при использовании иерархической модели.
Предположим, орграф представлен и сформирован на функциональном или объектно-ориентированном языке программирования (простая абстракция), что не создает особых трудностей в процессе прикладной реализации этой модели, но ограничения, возникающие на данном этапе, также весьма существенны. На самом деле модель комплекса работ в виде единственного орграфа не является оптимальной и пригодной для практики – она немногим лучше, чем иерархическая модель. Такова реальность. Но выход есть. Он заключается в повышении уровня абстракции и унификации общей схемы с избавлением от лишних допущений и проблем. Чем более абстрактной и высокоуровневой является модель, тем она лучше для практики, почти всегда. Существующие решения слишком конкретны, что не позволяет им быть практически пригодными. Модель комплекса работ в виде сетевого графика – это замечательно, но что нужно сделать, если необходимо иметь одну модель нескольких комплексов работ, в том числе выполняемых параллельно во времени? Необходима модель более высокого уровня.
Мультипроектное планирование фактически подразумевает, что основной моделью деятельности объединенного коллектива разработчиков проектов является направленный мультиграф , такой, что на множестве доменов связности . Использование модели мультиграфа , по сравнению с моделью орграфа позволяет подняться на ступеньку выше и учесть некоторые дополнительные элементы в сетевом планировании, к примеру, параллельное выполнение нескольких проектов одной и той же организацией. Для этого необходим прикладной инструментарий для решения мультипроектных задач, которого на данный момент нет.
Реализация задачи мультипроектного планирования для управления расписаниями на графах
Рассмотрим конкретный пример представления задачи мультипроектного планирования
в виде комплекса типовых задач составления расписаний на графах. Возьмем типовой сценарий, когда несколько параллельных проектов (допустим, четыре) выполняются с различной начальной датой и содержат уникальные, отличающиеся друг от друга работы с различной длительностью, каждый узел графа имеет уникальный идентификатор (строка, число или Guid). Упрощенные абстрактные примеры проектов представлены на рис. 1.
Рис. 1. Упрощенный пример представления мультиграфа
для проектов A, B, C, D: АD-BD, BC-BD – общие используемые работы;
AA, AC, BA – обозначения этапов или контрольных точек проекта
Как видно из представленной на рис. 1 модели, множество параллельно выполняющихся проектов A, B, C, D являются независимыми или могут иметь общие используемые работы (тестирование, написание проектной документации, инструкций для пользователей). Необходимы обобщенные, унифицированные методики решения таких задач на практике, являющиеся основой для создания мощных инструментальных средств мультипроектного планирования с использованием детерминированной машины Тьюринга [6].
Этапы решения задачи мультипроектного планирования
Рассмотрим кратко постановку задачи формирования согласованных с исполнителями расписаний при мультипроектном планировании.
Задано. 1. Множество работ или процессов , для которых заданы свойства: объединения, когда укрупненная работа состоит из более простых работ ; связности; отсутствия замкнутых контуров:
2. Заданный мультиграф , такой, что , на множестве доменов связности . Описывает последовательность планирования работ .
3. Отрезки планирования , или начальные (стартовые) точки формирования расписаний в определенное время.
4. Нормативная продолжительность выполнения плановых работ, которая утверждена исполнителями и согласована с Центром. Для ее определения могут быть использованы методы пассивной и активной экспертизы, а также опрос исполнителей с определением «пессимистичной» и «оптимистичной» оценки , . Другие способы определения нормативов могут быть получены с использованием техник восстановительно-прогнозирующего нормирования
[7, 8] или прецедентного подхода [9].
5. Базовый временной интервал (окно, слот), являющийся неделимым отрезком
непрерывного времени .
Перечень основных ограничений:
6. Множество жестких (hard) ограничений, формализуемых в виде соответствующих кортежей работ и простоев:
7. Множество мягких (soft) ограничений. Формируются при реализации процедуры согласования предпочтений исполнителей и Центра :
8. Согласованные механизмы планирования и стимулирования где – план на основе сведений в иерархических играх с обменом информацией [10] (игры Б. Ю. Гермейера).
Функция стимулирования зависит от равновесных, по Штакельбергу, расписаний и действий агентов , направленных на его выполнение.
9. Доменная модель запросов и пожеланий агента и метод ее отождествления (remap) с «мягкими» (soft) ограничениями фактически описывает набор справочников классификаторов ролей, операций, ресурсов: , множества элементов классификаторов , и классификатор ресурсов для всех работ , которые планируются Центром на основе общих элементов , , , индивидуальных для отличающихся конкретных проектов портфеля; совокупность активов , каждый из которых имеет соответствующую стоимость использования, включая всех исполнителей (агентов) . Активы могут принадлежать к некоторому классу и (или) группировать подмножество ролей (владеть набором компетенций) .
Критерий. Рассматриваемая задача использует трехкомпонентный критерий оптимальности , в составе которого можно выделить компоненты: время, затраты и количество учтенных запросов и пожеланий исполнителей расписаний. Элементы критерия: время, где – продолжительность -х (l – порядковый номер работы на критических путях мультиграфа) работ на критических путях мультиграфа ; затраты, , где – стоимость использования j-го актива, который запланирован для выполнения работ расписания; количество невыполненных мягких ограничений (запросов
и пожеланий ), , .
Требуется. Сформировать оптимальное по критерию согласованное расписание проведения работ с привязанными к ним активами (ресурсами) , которое удовлетворяет всем нормативным требованиям и ограничениям.
Формирование детального решения показанной выше задачи выходит за рамки этой статьи. Подробное описание механизмов построения согласованных расписаний в иерархических системах – это отдельная трудоемкая и интересная задача, рассмотреть которую здесь, в силу ограниченности объема, не представляется возможным.
Представим укрупненно основные базовые этапы решения задачи мультипроектного планирования, которые могут быть выполнены на ЭВМ, они частично описаны в работах [11, 12]. Современные языки программирования высокого уровня, такие как С++, С#, Java, Python, Javascript, подходят для решения сформулированной нетривиальной задачи. Основные части этой процедуры представлены ниже.
2.1. Этап формирования доменов связности проектов. Домен связности фактически представляет собой пространство, которое содержит совокупность (множество) связанных между собой узлов орграфа . Для определения этого домена необходима некоторая начальная точка (базовая окрестность), с которой инициируется выполнение поисковой процедуры на графе. Идеальным выбором здесь является множество начальных узлов мультиграфа для которых характерно, что вектор родительских по отношению к ним узлов не содержит элементов (пустое множество) . В качестве поисковой процедуры допустимо использовать «глубокий» (deep search) или «широкий» (wide search) поиск на мультиграфе Процесс формирования доменов связности в мультиграфе (см. рис. 1) показан на рис. 2.
Рис. 2. Построение доменов связности орграфа
2.2. Этап семантической кластеризации доменов связности задачи. Как можно заметить, решение задачи предыдущего этапа формирует домены связанных между собой узлов мультиграфа , которые содержат общие элементы (вершины и дуги). Решение задачи кластеризации (объединения доменов) по определенному семантическому признаку, условию позволит выделить как независимые орграфы, так и сформировать графы, имеющие общие работы. Кластеризация может быть осуществлена на практике в соответствии с утверждениями, представленными далее. Если домены частично (слабо) пересекаются, при этом непересекающиеся узлы имеют или не имеют родителей (детей), значит, мультиграф содержит общие работы. Если домены частично (сильно) пересекаются, при этом непересекающиеся узлы не имеют родителей (детей), значит, имеется отдельный орграф, который не приведен к сетевой структуре. В противном случае имеем дело с отдельным орграфом, который является приведенным к сетевой структуре. Пример решения задачи семантической кластеризации показан на рис. 3.
Рис. 3. Решение подзадачи семантической кластеризации
Далее по ходу решения задачи мультипроектного планирования осуществляется приведение орграфа к сетевому виду, когда структура не содержит циклов (циклы размыкаются с добавлением фиктивных работ), а также множество оконечных узлов орграфа дополняется начальными и конечными узлами с фиктивными связями.
2.3. Этап приведения доменов связности к сетевой структуре. Определение в каждом домене связности векторов узлов оконечных окрестностей и дополнение их фиктивными работами для формирования сетевого представления (рис. 4).
Рис. 4. Пример приведения к сетевой структуре
Рассмотрим более сжато, для краткости, остальные этапы.
2.4. Топологическая сортировка узлов мультиграфа , в результате которой вектор узлов упорядочивается в зависимости от положения узла в общей топологии графа. Сортировка узлов орграфа производится согласно начальному порядку, заданному узлами и ребрами на подмножестве вершин. Механизм топологической сортировки направленного графа использует поэтапное удаление узлов, у которых отсутствуют родительские элементы с последующим восстановлением графа. Для этого применяется исторический вектор ранее удаленных элементов (дуг, узлов).
Следовательно, для некоторого типового алгоритма (синтеза, визуализации) в дальнейшем формируется нормализованная структура данных, используемая впоследствии для унификации решения частных задач.
2.5. Определение оконечных вершин мультиграфа , а также критических путей для всех орграфов , входящих в состав .
Вершины соответствуют стартовым (начальным) и конечным узлам в векторе топологически отсортированного графа. Вычисление временной продолжительности критических путей для всех орграфов.
Критический путь вычисляется с использованием временной разницы и вещественного числа, что позволяет одновременно работать в терминах календарного времени и относительных значений весов. Такой способ позволяет также решать разнообразные логистические задачи прокладывания путей, маршрутов и построения транспортных расписаний.
2.6. Определение раннего срока свершения события (event) . Ранний срок, необходимый для выполнения всех работ, предшествующих данному событию (прямая итерация), определяется в соответствии с выражением
где – ранний срок свершения события ; – продолжительность (вес) работы между событиями ; – множество работ (направленных дуг), относящихся к событию . Ранние сроки могут быть определены с использованием алгоритмов муравьиной колонии, Эдгара Дейкстры или Беллмана – Форда [3, 4].
2.7. Определение позднего срока свершения события (обратная итерация). Он определяется как момент времени, после которого остается столько времени до критического срока, сколько необходимо для завершения всех работ, следующих за этим событием:
где tп (ei) – поздний срок свершения события ; – продолжительность работы между событиями ; – множество работ, выходящих из события .
Резерв времени для события определяется в соответствии с выражением
2.8. Определение полного резерва времени для работы – по сути, максимальной продолжительности, на которую можно задержать выполнение работы или увеличить ее длительность,
не изменяя критического срока:
2.9. Определение резерва времени для работы – максимального количества времени, на которое можно увеличить продолжительность данной работы, не изменяя при этом начальных сроков последующих работ при условии, что предшествующее событие наступило в свой ранний срок:
Последовательное выполнение всех рассматриваемых выше этапов позволяет на практике в автоматическом или автоматизированном режиме формировать расписания для организаций, осуществляющих мультипроектную деятельность, что позволит создавать инструментальные средства управления проектами нового поколения.
Заключение
В статье рассматриваются основные этапы автоматического построения расписаний в задаче мультипроектного планирования. Реализация этих этапов с использованием языков планирования высокого уровня (С++, C#, Java, Python и т. д.) позволит разрабатывать инструментально-программные средства планирования деятельности предприятий, организаций принципиально нового уровня, отличительной особенностью которых является ориентация на комплексную проектно-процессную деятельность, поддержка смешанного и параллельного планирования.
Отдельные элементы представленной укрупненной процедуры построения расписаний реализованы в разработанном авторами программном обеспечении, включая систему согласованного построения расписаний «TmBuilder» [13].
1. Голенко Д. И. Статистические методы сетевого планирования и управления. М.: Наука, 1968. 400 с.
2. Адельсон-Вельский Г. М. О некоторых вопросах сетевого планирования // Исследования по дискретной математике. М.: Наука, 1973. С. 105–134.
3. Bellman R., Gross O. Some combinatorial problems arising in the theory of multistage processes // Journal of the Society for Industrial and Applied Mathematics. 1945. V. 2. N. 3. P. 124–136.
4. Bellman R. Mathematical Aspects of Scheduling Theory // Journal of the Society for Industrial and Applied Mathematics. 1956. V. 4. N. 3. P. 168–205.
5. Джексон Д. Р. Очереди с динамическим правилом приоритета // Календарное планирование. М.: Прогресс, 1966. С. 357–377.
6. Turing A. M. Computer machinery and intelligence // Mind. 1950. V. 49. P. 433–460.
7. Авдеев В. П., Карташов В. Я., Мышляев Л. П., Ершов А. А. Восстановительно-прогнозирующие системы управления. Кемерово: Изд-во КемГУ, 1984. 89 с.
8. Авдеев В. П., Мышляев Л. П., Соловьев В. Н. О восстановительно-прогнозирующем регулировании технологических процессов // Изв. вузов. Черная металлургия. 1978. № 10. С. 165–168.
9. Варшавский П. Р., Еремеев А. П. Реализация методов поиска решения на основе аналогий и прецедентов в системах поддержки принятия решений // Вестн. Моск. энергет. ин-та. 2006. № 2. С. 77–87.
10. Гермейер Ю. Б. Игры с непротивоположными интересами. М.: Наука, 1976. 326 с.
11. Добрынин А. С., Кулаков С. М., Зимин В. В., Бондарь Н. Ф. О формировании комплекса инстру-ментальных средств ИТ-провайдера для построения расписаний процесса внедрения сервиса // Науч. обозр. 2013. № 8. С. 93–101.
12. Кулаков С. М., Грачев А. В., Добрынин А. С., Койнов Р. С. Формирование расписаний в задачах временного планирования // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. 2014. № 4. С. 103–111.
13. Свидетельство о государственной регистрации программы для ЭВМ № 2014613280 РФ. Программа построения расписаний в проектно-процессной деятельности и сервисном управлении / Добрынин А. С., Койнов Р. С., Кулаков С. М., Зимин В. В.; № 2014610775; заявл. 06.02.2014; зарегистр. 21.03.2014
