BUILDING UP SCHEDULES IN MULTIPROJECT DESIGN MANAGEMENT SYSTEMS
Authors:
1.
Siberia State Industrial University
(Senior Lecturer of the Department of Automation and Information Systems)
Russian Federation
Russian Federation
2.
Siberian State Industrial University
(Doctor of Technical Sciences, Professor; Professor of the Department of Automation and Information Systems)
3.
Siberia State Industrial University
(Senior Lecturer of the Department of Automation and Information Systems; Leading Informatization Specialist of the Department of Systems and Network Technologies)
Type:
Article
Pages:
from 105
to 114
Status:
Published
Received:
23.07.2021
Accepted:
26.07.2021
Published:
26.07.2021
Subject area:
UDK 50 Общие вопросы математических и естественных наук
Language:
Russian
Keywords:
building up schedules, multi-project planning, directed graph, multigraph, domain, clustering
Abstract (English):
The article focuses on the problem of algorithmizing the process of building schedules in various spheres of human activity by using the modern mathematical apparatus, as well as achievements in the field of systems analysis, game theory, and graph theory. Nowadays, there have been analyzed and determined the boundaries of the effective application of many well-known heuristic and metaheuristic algorithms, which have shown good results in practice. However, despite the achievements in the discrete optimization, scheduling and network planning, the new problems of drawing up so-called coordinated schedules in the field of multi-project planning, which take into account the preferences (requests, wishes) of specific schedule executors, are still of practical interest. There have been considered the approaches and main stages of solving the problems of constructing coordinated schedules in multi-project planning, which is relevant for the development of new generation software and tools
The article focuses on the problem of algorithmizing the process of building schedules in various spheres of human activity by using the modern mathematical apparatus, as well as achievements in the field of systems analysis, game theory, and graph theory. Nowadays, there have been analyzed and determined the boundaries of the effective application of many well-known heuristic and metaheuristic algorithms, which have shown good results in practice. However, despite the achievements in the discrete optimization, scheduling and network planning, the new problems of drawing up so-called coordinated schedules in the field of multi-project planning, which take into account the preferences (requests, wishes) of specific schedule executors, are still of practical interest. There have been considered the approaches and main stages of solving the problems of constructing coordinated schedules in multi-project planning, which is relevant for the development of new generation software and tools
Keywords:
building up schedules, multi-project planning, directed graph, multigraph, domain, clustering
building up schedules, multi-project planning, directed graph, multigraph, domain, clustering
Введение
В статье рассматриваются теоретические и прикладные аспекты управления мультипроектными разработками. Предложенные подходы могут быть использованы для создания инструментальных информационных систем нового поколения, систем управления проектами, которые отличаются более сложными подходами к управлению по сравнению с известными
и широко распространенными 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. Golenko D. I. Statisticheskie metody setevogo planirovaniya i upravleniya. M.: Nauka, 1968. 400 s.
2. Adel'son-Vel'skiy G. M. O nekotoryh voprosah setevogo planirovaniya // Issledovaniya po diskretnoy matematike. M.: Nauka, 1973. S. 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. Dzhekson D. R. Ocheredi s dinamicheskim pravilom prioriteta // Kalendarnoe planirovanie. M.: Progress, 1966. S. 357-377.
6. Turing A. M. Computer machinery and intelligence // Mind. 1950. V. 49. P. 433-460.
7. Avdeev V. P., Kartashov V. Ya., Myshlyaev L. P., Ershov A. A. Vosstanovitel'no-prognoziruyuschie sistemy upravleniya. Kemerovo: Izd-vo KemGU, 1984. 89 s.
8. Avdeev V. P., Myshlyaev L. P., Solov'ev V. N. O vosstanovitel'no-prognoziruyuschem regulirovanii tehnologicheskih processov // Izv. vuzov. Chernaya metallurgiya. 1978. № 10. S. 165-168.
9. Varshavskiy P. R., Eremeev A. P. Realizaciya metodov poiska resheniya na osnove analogiy i precedentov v sistemah podderzhki prinyatiya resheniy // Vestn. Mosk. energet. in-ta. 2006. № 2. S. 77-87.
10. Germeyer Yu. B. Igry s neprotivopolozhnymi interesami. M.: Nauka, 1976. 326 s.
11. Dobrynin A. S., Kulakov S. M., Zimin V. V., Bondar' N. F. O formirovanii kompleksa instru-mental'nyh sredstv IT-provaydera dlya postroeniya raspisaniy processa vnedreniya servisa // Nauch. obozr. 2013. № 8. S. 93-101.
12. Kulakov S. M., Grachev A. V., Dobrynin A. S., Koynov R. S. Formirovanie raspisaniy v zadachah vremennogo planirovaniya // Vestn. Astrahan. gos. tehn. un-ta. Ser.: Upravlenie, vychislitel'naya tehnika i informatika. 2014. № 4. S. 103-111.
13. Svidetel'stvo o gosudarstvennoy registracii programmy dlya EVM № 2014613280 RF. Programma postroeniya raspisaniy v proektno-processnoy deyatel'nosti i servisnom upravlenii / Dobrynin A. S., Koynov R. S., Kulakov S. M., Zimin V. V.; № 2014610775; zayavl. 06.02.2014; zaregistr. 21.03.2014
