ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

Network planning method for developing complex engineering systems

The article was published in issue no. № 2, 2014 [ pp. 22-26 ]
Abstract:The problem of developing a performance planning method for structural-complicated projects. These projects can also include development of complex engineering systems, such as weapons and military equipment, power engineering facilities, industry and transport facilities is formulated and formalized. A project is a set of operations necessary to ach ieve the purpose. The duration of every operation is known. They are conne cted by order relation (obligatory precedence). A tran-sition to a market economy and modifications in domestic and international situation with crisis developments in national economy have lead to a necessity of critical analysis of methods for maintening state requirements for production and new approaches to these problems solution. The proposed solution method is based on network planning method, on the idea of critical path optimisation. Known methods are improved based on the dynamic programming scheme . The critical path of the project graph defines performance time of the project. A cooperation of project performers is formed based on a solution of the assignment problem using a dynamic programming method and the offered algorithm, that allows consider ing the works precedence ratio defining project structure. Enterprise industrial engineering is based on rational combination of all basic, auxiliary and serving processes in time and space. Singularities and methods of this combination are вшааукуте in various working conditions. At the same time industrial engineering should be correspond to general principles. They are continuity, proportionality, rhythm, parallelism concern. The offered method allows implementing these principles.
Аннотация:Сформулирована и формализована задача разработки метода планирования выполнения структурно-сложных проектов, к которым можно отнести и разработку сложных технических систем, таких как вооружение и военная техника, объекты энергетики, промышленности и транспорта. Под проектом будем понимать совокупность операций, необходимых для достижения цели. Длительность каждой из них известна, и они связаны отношением порядка (обязательным предшествованием). Переход к рыночным экономическим отношениям и изменения во внутренней и международной обстановке, осложненные кризисными явлениями в национальной экономике, объективно обусловливают необходимость критического анализа методов обеспечения государственной потребности в продукции и вы-работки принципиально новых подходов к решению этих задач. Метод решения задачи основан на применении метода сетевого планирования, на идее оптимизации критического пути. При этом известные методы доработаны на основе схемы динамического программирования. Критический путь графа проекта определяет время выполнения проекта в целом. Формирование кооперации исполнителей проекта основано на решении задачи о назначениях с использованием метода динамического программирования и предложенного алгоритма, позволяющего учесть отношение предшествования работ, определяющее структуру проекта. В основе организации производства на предприятии лежит рациональное сочетание во времени и в пространстве всех основных, вспомогательных и обслуживающих процессов. Особенности и методы этого сочетания разнообразны в различных производственных условиях. Однако при всем многообразии последних организация производственных процессов должна быть подчинена некоторым общим принципам. К ним относятся непрерывность, пропорциональность, ритмичность, параллельность. Предложенный метод позволяет реализовать перечисленные принципы на практике.
Authors: Dopira R.V. (rvdopira@yandex.ru) - NPO RusBITex (Professor, Head of Department), Tver, Russia, Ph.D, Kordyukov R.Yu. (romkord@yandex.ru) - Main Department of scientific and research activities and technological support of the advanced technologies of the Ministry of defense of the Russian Federation, Main Department of scientific and research activities and technological support of the advanced technologies of the Ministry of defense of the Russian Federation, Russia, Ph.D, Begletsov A.A. () - Military Representativ Office of the Ministry of Defence of the Russian Federation, Moscow, Sergienko S.V. (romkord@yandex.ru) - Department of an Operational Administration Command the Ministry of Defence of the Russian Federation, Москва, Russia
Keywords: dynamic control, network model, critical path, forecasting time series, network planning, net graph
Page views: 12808
Print version
Full issue in PDF (6.10Mb)
Download the cover in PDF (0.87Мб)

Font size:       Font:

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

Методы сетевого планирования основаны на идее оптимизации критического пути и являются эффективным средством составления проектов и наблюдения за их выполнением [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.


Permanent link:
http://swsys.ru/index.php?page=article&id=3803&lang=&lang=en&like=1
Print version
Full issue in PDF (6.10Mb)
Download the cover in PDF (0.87Мб)
The article was published in issue no. № 2, 2014 [ pp. 22-26 ]

Perhaps, you might be interested in the following articles of similar topics: