Сетевые модели и решение организационно-технических задач

П.Н. Шимукович, доктор технических наук

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

 

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

Анализ ситуации позволил установить следующее. Задача, в целом, является типовой, выполняется многократно в разных компаниях профессиональными исполнителями. Ее каждая очередная реализация шла по накатанной колее – никто ранее сокращения сроков не требовал. Поэтому при новой постановке задачи резервы сокращения сроков заказчику виделись в дополнительном наборе персонала, усилении технической оснащенности. Но сразу же возникал вопрос: что делать со всем этим «дополнительным» при выполнении задачи в интересах других компаний, для которых минимизация времени не является важной?

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

Рис.1. План выполнения задачи.

Вместе с тем следует отметить, что по своему графическому изображению такой план очень близок к диаграмме Ганта, которая в качестве основного результата планирования предлагается, например,MSProject [1]. То есть диаграмма Ганта, вследствие ее широкой известности, применяется пользователями в повседневной практике вне зависимости от того, рисуется ли она с помощью компьютерных средств или вручную. Соответственно план, определяющий организацию выполнения задачи, оказывается разработанным еще до применения специализированного софта. Велика ли будет польза, если этот же план перенести в тот же MSProject? Да, будет получена прекрасная возможность структуризации, учета  и распределения ресурсов, расчета критического пути и т.д. Но это все – последующие задачи, содержание и продолжительность которых определяется продуманностью и правильным выполнением подготовительного этапа. Ни формализованных процедур, ни хотя бы приближенных рекомендаций относительно того, как готовить исходные данные для построения плана (сетевого графика),  в таких программах не содержится. В этой связи закономерны и выводы пользователей о том, что при решении именно их задач эффективность софта не высокая.

Отыскание резервов по сокращению сроков выполнения задачи осуществлялось на основе метода сетевого планирования, в котором было выделено два этапа:

- организационно-технологический;

- технический.

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

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

Так как сетевой график – это, по сути, граф, то естественным было стремление применить известные операции преобразования графов к решению данной задачи: удалить ребра, удалить вершины, добавить ребра, добавить вершины и т.д. [2].Перечисленные операции удобно применять к графу, а вот в отношении фрагмента действительности, который этот граф отображает, дело обстоит значительно сложнее: не всегда очевидно, что можно добавить или удалить.Следует отметить, что теория графов традиционно применяется для графического отображения систем вообще и их частного случая – сетевой модели – в том числе. В этой связи более понятными представляются системные действия преобразования модели [3], позволяющие рассмотреть ситуацию в разных аспектах и предложить разнообразные действия по преобразованию ее исходного варианта: изменить количество входов-выходов событий, добавить связь, изменить ее свойства или направление, представить событие в виде системы, обеспечить выполнение объектом или его частью не только основной, но и вспомогательных функций и т.д. Именно путем перебора представленных действий удалось выявить события, допускающие ветвление, посути – перевод последовательно выполняемых работ в параллельные.

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

Рис.2. Сетевой график работ.

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

Рис.3. Сетевой график работ, построенный пакетом компьютерной математики.

 

График, который строит человек, может выглядеть еще более путаным, особенно при построении первых его вариантов.

На процедуре упорядочивания сетевого графика (в терминах теории графов – топологической сортировки)следует остановиться подробнее, так как при всей ее простоте в издаваемых в последнее время книгахо сетевых методах она почему-то не находит отражения. Кроме того, имеющиеся описания не всегда излагаются доступным языком. Например, в [4] процедура описана с применением векторной алгебры. В [5,6] упор делается на описании алгоритма и его последующей реализации с помощью тех или иных языков программирования, что тоже требует определенного уровня подготовки. Такая ситуация в итоге, как и в случае с решением анализируемой задачи самим заказчиком, приводит к тому, что исходное упорядочивание сетевого графика не выполняется, а результат планирования оказывается невысоким.

При решении данной задачи для упорядочения сетевого графика применялся метод Демукрона [4], предусматривающий выполнение нескольких последовательных шагов, результатом которых является разбиение графика на слои.Стремление предельно подробно описать содержание метода привело к тому, что само описание получилось большим. Чтобы его чтение не уводило читателей в сторону от основной темы статьи, описание вынесено в приложение.

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

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

 

Таблица 1

Процедура разбиения сетевого графика на слои

 

 

После выполнения упорядочивающей процедуры все события сетевого графика оказываются разбитыми на слои, нумерация которых идет справа-налево. Ее можно изменить на противоположную для придания нумерации привычного вида.Для построения сетевого графика теперь надо реализовать полученные результаты, то есть разместить события в соответствии с нумерацией уровней, что и выполнено при построении графика на рис.2. На рис. 2, например, отчетливо видно, что события 4 и 9; 16, 15, 11 и 13; 10 и 12 принадлежат к соответствующим уровням и между ними нет связей. Это позволяет рассматривать перечисленные события как параллельно выполняемые, а не последовательные. Из этого же следуют и другие выводы:

- время выполнения работ 13 и 16 вообще мало чем ограничено – их можно выполнять в любой промежуток времени, начиная с момента завершения работы 3 и 4 соответственно и вплоть до наступления события 17. Это дает возможность руководителю свободу маневра при организации работ;

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

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

Как следует из результатов построения сетевого графика, на критическом пути, определяющем итоговую продолжительность выполнения задачи, располагаются работы: 1, 2, 4, 5, 6, 7, 8, 10, 14, 15, 17, 18. Их суммарная продолжительность составила 21,5 дня вместо 27, которые планировались на выполнение задачи ранее.

В рамках второго – технического – этапа изыскивались резервы в сокращении сроков выполнения работ, связанные с выполнением технических доработок объектов, с которыми надлежало оперировать при выполнении задачи. Данный этап можно рассматривать в качестве подуровня предыдущего этапа, так как он предусматривает его дальнейшую детализацию. В этой связи были подвергнуты повторному анализу объекты, с которыми предстояло работать, и выбраны для последующих преобразований те из них, которые завершались событиями 6, 7 и 8. Очевидно (рис.2), что на сетевом графике эти события располагаются последовательно. Организационными мерами перевести их расположение из последовательного в параллельное и сократить тем самым время выполнения задачи не удалось.По сложившейся практике работу, заканчивающуюся событием 8, можно было начинать только после наступления события 7, а работу, заканчивающуюся событием 7 – только после наступления события 6. Анализ конструкции узлов, с которыми выполнялась работа, и порядка их сочленения показал, что они действительно могут быть состыкованы лишь в случае соблюдения правил их пространственного расположения и центрирования один относительно другого. То есть, каждый последующий узел должен определенным образом входить в ранее собранное изделие. Как известно, входимость отдельных узлов в состав итогового изделия принято изображать с помощью схем разузлования [7]. На таких схемах каждому узлу присваивается уровень, который показывает, через сколько промежуточных сборок данный узел входит в основную сборку. Пользуясь этим подходом, исходное исполнение собираемых узлов можно изобразить следующим образом (рис.4).

Рис.4. Существующая схема разузлования собираемых узлов:

1 – основная сборка; 2, 4, 6 – вспомогательные устройства; 3, 5, 7 – основные узлы.

 

Из анализа рис.4 следует, что каждый узел требует для выполнения монтажа наличия вспомогательных устройств – для каждого узла по отдельному устройству. При этом к уже собранной части изделия пристыковывается вначале вспомогательное устройство, затем на нем монтируется основной узел. Для каждого из выделенных узлов этот цикл повторяется. При этом к вспомогательным устройствам предъявлялся ограниченный перечень требований: быть прочными, обеспечивать удобство монтажа-демонтажа основных узлов. Столкнувшись с затруднением в сокращении сроков выполнении задачи, естественным является расширение перечня предъявляемых требований к собираемым компонентам. В частности, PN-метод [3] предлагает выполнить следующие действия: принять к рассмотрению новые свойства элемента или его частей; добавить связи между элементами, изменить их параметры; выделить и использовать вспомогательные, дополнительные функции, сопровождающие реализацию главной функции; увеличить количество внутренней информации системы. Как все вместе, так и каждое представленное действие по отдельности подталкивают мысль к тому, что вспомогательные устройства должны отвечать не только ныне существующим требованиям, но и некоторым новым. Путем удовлетворения этих требований должна формироваться дополнительная связь между отдельными вспомогательными устройствами, должна появиться возможность реализовать с их помощью некоторую дополнительную функцию, которая не обязательно должна быть прочностной, а может быть и информационной.

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

Рис.5. Предложенная схема разузлования.

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

 

Выводы:

1. Обеспечено сокращение продолжительности выполнения задачи заказчика на 26%.
2. Сетевые модели являются эффективным инструментом анализа и оптимизации выполнения задач. Для получения значимого эффекта от их применения, в том числе на основе современных компьютеризированных средств, необходимо выделение и тщательная отработка подготовительного этапа, результатом которого является упорядоченный по слоям сетевой график.
3. Творческий этап – обязательная составная часть процесса поиска вариантов преобразования исходной сетевой модели в искомую. Удобный инструментарий для его выполнения содержится в PN-методе, который, как и сама сетевая технология, является системным.

 

Литература:

1. Четфилд Ч, Джонсон Т. MicrosoftProject 2010. – М.: ЭКОМПаблишерз, 2011. – 656 с.
2. Храмова Т.В. Лекции по теории графов. Учебное пособие. – Новосибирск: СибГУТИ, 2011. – 98 с.
3. Шимукович П.Н. ТРИЗ-противоречия в инновационных решениях: PN-метод. Изд. 2-е. – М.: Издательский дом «ЛИБРОКОМ», 2013. – 216 с.
4. Кофман А., Дебазей Г. Сетевые методы планирования. – М.: Издательство «Прогресс», 1968. – 182 с.
5. Белоусов А.И., Ткачев С.Б. Дискретная математика. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – 744 с.
6. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. – 406с.
7. Васильева Л.Н., Деева Е.А. Моделирование микроэкономических процессов и систем. – М.: КНОРУС, 2009. – 400 с.

 

Приложение

Процедура разбиения сетевого графика на слои методом Демукрона

Составляется таблица (табл.1), у которой количество столбцов и количество строк равно количеству выделенных событий задачи. В ячейках символом «х» обозначен факт наличия связи (работы) между соответствующими событиями. Справа от основной таблицыразмещается примыкающая таблица, в ячейках которой римскими цифрами обозначены уровни, на которые надлежит разбить включенные в график события. Стыкуются между собой левая (основная) и правая (примыкающая) части таблицы через столбец с номером «0». Алгоритм заполнения примыкающей таблицы состоит в следующем. Выделяется событие (события), которое не имеет потомков, то есть, не имеет связей (работ), которые являются выходящими из данного события. Такое событие относится к последнему слою. На следующем шаге из рассмотрения исключаются как событие последнего слоя, так и ведущие к нему связи. В результате получается усеченный график, в котором не имеющими потомков становятся очередные события (событие), их следует отнести к предпоследнему слою. Описанная процедура повторяется до тех пор, пока не будут рассмотрены все события исходного сетевого графика. Таким образом, смысл действий состоит в том, что надлежит последовательно вычеркивать связи между событиями, начиная с того, которое исходно не имеет следующих за ним связей. В таблице 1 на уровне 0 не имеет последующих связей событие 18. Двигаясь по строке 18 слева-направо убеждаемся, что эта строка пустая и поэтому на нулевом уровне присоединенной таблицы записываем 0. Тем самым определяется, что работа 18 является последней и она завершает выполнение задачи. Все другие строки таблицы содержат то или иное количество символов «х», что в уровне 0 (столбце с номером «0») соответствует проставленным цифрам. Таким образом, на нулевом уровне размещается событие №18. На втором шаге упорядочивающей работы просматриваем столбец 18, то есть столбец, номер которого соответствует номеру события, размещенного на предыдущем уровне. Очевидно, что на пересечении столбца 18 и строки 17 стоит символ «х». Это означает, что теперь следует вычеркнуть связь между событиями 17 и 18, что приводит к получению цифры 0 на первом уровне примыкающей таблицы в строке 17. Все остальные цифры примыкающей таблицы остались неизменными.

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

                                                                                                                             

                                                              Рис. 6. Схематическое изображение процесса упорядочения сетевого графика по алгоритму Демукрона.

На следующем шаге просматриваем столбец №17. В нем содержатся четыре символа «х», то есть, на втором уровне стали без потомков четыре события. Соответственно, здесь надлежит вычеркнуть 4 связи, что и обозначено соответствующими нулями на втором уровне примыкающей таблицы. Наличие четырех нулей в полученном уровне приводит к изменению порядка действий в сравнении с предыдущим уровнем: надлежит осуществить проверку не одного, а сразу четырех столбцов на предмет отнесения событий к очередному уровню. То есть, первый сверху ноль размещен в строке 11. Следовательно, принимаем во внимание столбец 11 основной таблицы и находим в нем символ «х» в строке 9. Соответственно при формировании уровня III в строке 9 происходит уменьшение количества связей на единицу. Второй сверху ноль уровня II размещен в строке 13. Следовательно, принимаем во внимание столбец 13 основной таблицы и находим в нем символ «х» в строке 3. Соответственно при формировании уровня III в строке 3 происходит уменьшение количества связей на единицу. Третий сверху ноль уровня II размещен в строке 15. Следовательно, принимаем во внимание столбец 15 основной таблицы и находим в нем символ «х» в строке 14. Соответственно при формировании уровня III в строке 14 происходит уменьшение количества связей на единицу. В данном случае полученная цифра – ноль, то есть событие 14 не имеет потомков при его размещении на уровне III. Соответственно для события 14 определяется окончательный номер уровня, на котором оно размещается. Описанные выше действия применительно к строкам 9 и 3 получением нуля на уровне III не заканчивались. Соответственно для событий 9 и 3 уровень III не является окончательным и работа с этими событиями должна быть продолжена. Четвертый сверху ноль уровня II размещен в строке 16. Следовательно, принимаем во внимание столбец 16 основной таблицы и находим в нем символ «х» в строке 5. Соответственно при формировании уровня III в строке 5 происходит уменьшение количества связей на единицу. Так как и здесь положение события 5 характеризуется цифрой 1, а не 0, то для него уровень III тоже не является окончательным и работа по поиску места его размещения в последующем должна быть продолжена. На этом формирование уровня III завершается. Анализируем уровень (столбец) III. Очевидно, что в нем цифра 0 размещается в строке 14. Следовательно, для дальнейшего упорядочивания сетевого графика во внимание нужно принимать столбец 14 основной таблицы и повторять выполнение описанных выше процедур.В представленной последовательности действия выполняются до тех пор, пока в примыкающей таблице не будут получены конечные нули во всех строках, то есть пока не будет полностью проанализирована вся основная таблица.

Выражаю признательность А.В. Кудрявцеву за конструктивное обсуждение статьи на этапе ее подготовки.