Software & Systems

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

Методы сетевого планирования основаны на идее оптимизации критического пути и являются эффективным средством составления проектов и наблюдения за их выполнением [1].

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

Представим сетевой граф G системой (V, U, φ, w), где V={1, 2, …, v} – множество вершин графа (события); U={u} – множество ребер графа (работ), причем V∩U=Æ; φ – функция инциденции, ставящая в соответствие каждому ребру uÎU упорядоченную пару вершин (v1, v2), называемых началом и концом ребра u. Ребро u находится в отношении инциденции со своими вершинами. Функция w(u) определяет трудоемкость выполнения работы u исходя из нормативов экспертных оценок или опыта и измеряется в единицах трудоемкости, стоимости и пр.

В основе организации производства на предприятии лежит рациональное сочетание во вре- мени и в пространстве всех основных, вспомо- гательных и обслуживающих процессов. Особенности и методы этого сочетания разнообразны в различных производственных условиях. Однако при всем многообразии этих условий организация производственных процессов должна быть подчинена некоторым общим принципам. К ним относятся непрерывность, пропорциональность, ритмичность, параллельность [2].

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

Работа характеризует любое действие, требующее затрат времени и ресурсов.

Планирование работ, управление технологическими процессами при выполнении проекта проводятся на интервале времени от начала до момента завершения проекта.

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

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

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

Представленная задача близка к классической задаче о назначениях [3, 4], но отличается тем, что в ней дополнительно вводится ограничение на завершение всего комплекса работ в заданный директивный срок Тдир.

Пусть имеются множество исполнителей I={1, 2, ..., n}, множество работ R={r1, r2, ..., rn} и (n´n)-матрица численных оценок (например производительностей) C={cij}, где cij – оценка закрепления исполнителя i за работой rj, i= j= Назначения – взаимно однозначные отображения множества {1, 2, ..., n} в себя; назначение π исполнителю i предписывает работу rπ(i); численной оценкой такого закрепления является ciπ(i) – элемент матрицы C, i=1, 2, ..., n. Каждое назначение π оцениваем по критерию К(π)= В указанной интерпретации значение этого критерия – суммарная стоимость исполнителей при назначении π. Требуется найти назначение, при котором суммарные затраты исполнителей минимальны.

Задача может быть сформулирована в виде

                                                (1)

,                                   (2)

где Ткр – длина критического пути Lкр сетевого графа G.

Рассмотрим возможность решения сформулированной задачи (обозначим ее символом Z) методом динамического программирования. Для этого введем в рассмотрение совокупность частных задач Z(i, Wi), формулируемых по исходным данным задачи Z; здесь iÎ{1, 2, ..., n}, а Wi – i-элементные подмножества совокупности {1, 2, ..., n}. В задаче Z(i, Wi) между исполнителями {1, 2, ..., i} следует распределить совокупность работ, индексы которых перечислены в Wi, критерий задачи прежний – суммарная производительность имеющихся исполнителей. Оптимальное значение критерия в задаче Z(i, Wi) обозначим В*(i, Wi). В таком случае В*(п, {1, 2, ..., n}) – оптимальное значение критерия в исходной задаче Z.

Как очевидно,

В*(1, {j})=c1j для всех jÎ{1, 2, ..., n}.        (3)

Если i>1, имеем

         (4)

i=2, 3, …, n,               

здесь Wi – произвольное i-элементное подмножество из совокупности {1, 2, ..., n}.

Записанные равенства (3), (4) являются соотношениями динамического программирования для решения задачи Z. Легко видеть, что оценкой числа элементарных операций, выполняемых основанным на соотношениях (3) и (4) алгоритмом, является функция, которая экспоненциально зависит от п.

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

Решение задачи о назначении с применением алгоритма динамического программирования позволяет получить начальное приближение решения сформулированной задачи, при котором стоимость выполнения комплекса работ проекта будет минимальной, однако ограничение на время выполнения проекта (2) может не выполняться.

Необходимо расширить алгоритм решения задачи о назначении для того, чтобы решить общую задачу (1), (2).

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

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

Для решения задачи нахождения критических путей сетевого графа модифицируем подход, представленный в [5], основанный на методе динамического программирования решения задачи нахождения кратчайших путей.

Пусть задан конечный взвешенный ориентированный граф G с множеством вершин V={1, 2, ..., v}, значения веса всех дуг неотрицательны. Вес дуг трактуем как их длину. Последовательность i1, i2, ..., ik вершин графа G определяет путь из вершины i1 в вершину ik, если для каждого l=1, 2, ..., k–1 в данном графе имеется дуга (il, il+1); указанные дуги образуют путь i1, i2,…, ik. Сумма длин дуг, образующих путь, называется длиной этого пути. Для каждой вершины х графа требуется найти путь минимальной длины (критический путь) из вершины 1 в вершину х.

Вес дуги графа G обозначим τ(i, j). Длину критического пути из 1 в х будем называть расстоянием от вершины 1 до вершины х. Расстояние от вершины 1 до вершины х обозначим s(x).

Ясно, что s(1)=0. Пусть H – множество вершин, длина критических путей в которые из вершины 1 уже известна. В начальной ситуации это множество одноэлементно: H={1}. Обозначим s(1, M) минимальную из длин критических путей от вершины 1 до вершин множества М, МÍ{2, 3, ..., v}. Очевидно, что для множества вершин Н, содержащего вершину 1, имеет место

s(1, N\H)=(s(i) +τ(i, j)).                   (5)

Пусть минимум правой части (5) реализуется на паре (i0, j0). Тогда критический путь из вершины 1 в вершину j0 получаем добавлением к критическому пути из вершины 1 в вершину i0 дуги (i0, j0), длина s(j0) этого пути равна s(i0)+τ(i0, j0)).

Формула (5) – рекуррентное соотношение динамического программирования для решения задачи отыскания критических путей. Пользуясь этой формулой, на первом шаге определяем ближайшую к вершине 1 вершину i1 из совокупности {2, 3, ..., v}. На втором шаге находим ближайшую к вершине 1 вершину i2 из совокупности {2, 3, ..., v}\{i1}; на третьем шаге – ближайшую к вершине 1 вершину i3 совокупности {2, 3, ..., v}\{i1, i2} и т.д. В процессе счета строится дерево D критических путей из вершины 1 в остальные вершины. Корнем D является вершина 1; если на произвольном шаге алгоритма минимум правой части (5) реализуется на паре (i0, j0), к конструируемому дереву добавляется ребро (i0, j0).

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

Шаг 0. Определяется начальное распределение исполнителей (решение задачи о назначениях).

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

Шаг 1. Рассчитываются критический путь Lкр и соответствующее ему критическое время T [Lкр(G)]=s(i, V).

Шаг 2. Если Tкр£Tsup, то решение получено и осуществляется переход на шаг 6.

Шаг 3. Определяется пара (i, rj), iÎI, rjÎU, для которой снижение длины критического пути на единицу дополнительных затрат максимально:

.

Шаг 4. Если сокращение критического времени положительно, то xij=1, I=I\{i*}, U=U\{rj*}, переход на шаг 1.

Шаг 5. Решения задачи не существует. Осуществляется корректировка сроков и состава кооперации исполнителей.

Шаг 6. Получено решение задачи: X=½Xij½, Tкр, C=C(X).

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

Таким образом, метод сетевого планирования может составлять основу информационной поддержки реализации структурно-сложных проектов. Разработанная методика является эффективным средством для заказчика при планировании НИОКР на этапе конкурсного размещения заказов на разработку СТС.

Литература

1.     Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении организационными структурами. М.: Синтег, 2001.

2.     Экономика производства оборонной продукции: учеб. пособие; [под ред. Г.С. Подистова]. М.: Изд-во Военного фин.-эконом. ун-та МО РФ, 2001. 234 с.

3.     Кофман А., Дебазей Г. Сетевые методы планирования. М.: Прогресс, 1968.

4.     Гаврилов Н.Н., Карамзина Н.С., Колосова Е.В., Лысаков А.В., Цветков А.В. Анализ и управление проектами. Практический курс: учеб. пособие. М.: Изд-во Рос. экон. акад., 2000.

5.     Коган Д.И. Динамическое программирование и дискретная многокритериальная оптимизация: учеб. пособие. Н. Новгород: Изд-во Нижегородского ун-та, 2004. 150 с.

References

1.     Burkov V.N., Zalozhnev A.Yu., Novikov D.A. Teoriya grafov v upravlenii organizatsionnymi strukturami [Graph theory in organizational structure management]. Moscow, Sinteg Publ., 2001, 124 p.

2.     Podistov G.S., ed. Ekonomika proizvodstva oboronnoy produktsii [Economics of military production]. Study guide, Мoscow, Military Finance and Economics Univ. of the Russian Federation's Defense Ministry Publ., 2001, 234 p.

3.     Kaufmann А., Desbazeille G. La méthode du chemin criti­que: application aux programmes de production et d'études de la méthode P.E.R.T. et de ses variants. Dunod Publ., 1964, 181 p. [Russ.ed.: Belenkiy V.Z. Setevye metody planirovaniya. Moscow, Prоgrеss Publ., 1968, 182 p.].

4.     Gаvrilоv N.N., Каrаmzinа N.S., Коlоsоvа Е.V., Lysа- kоv А.V., Tsvеtkоv А.V. Аnаliz i uprаvlеniе prоеktami. Prаkti­chеskiy kurs [Project analysis and project management]. Study guide, Мoscow, Rоs. ekоn. аkаd. Publ., 2000, 114 p.

5.     Kogan D.I. Dinamichеskое programmirovanie i diskret­naya mnogokriterialnaya optimizatsiya [Dynamic programming and discrete multi-criteria optimization]. Study guide, N. Novgorod, Lobachevsky State Univ. of Nizhniy Novgorod Publ., 2004, 150 p.