Файл: Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями.pdf

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

Методы распределения ограниченных ресурсов

В последнее время при строительстве любого объекта наиболее важной проблемой является решение задач кален­ дарного планирования, оптимального в смысле критериев, связанных с ресурсами второго вида — нескладируемыми. Поскольку в литературе по сетевому планированию дается достаточно подробный обзор методов решения задач распре­ деления ресурсов [5, 16, 29], мы не будем останавливаться на способах их решения, а ограничимся лишь перечислением основных, обращая внимание на постановку решаемых задачГ

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

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

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

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

22

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

Проводимые исследования и накопленный опыт говорят о рациональности применения и разработки подобных мето­ дов. Не случайно поэтому большинство разработанных к на­ стоящему времени методов решения реализует эвристиче­ ский подход. Общеизвестная задача минимизации времени осуществления комплекса при заданном уровне ресурсов рассматривается во многих работах [5, 27, 60, 67].

Алгоритм, предложенный в работе W . Gray и Е. Kidd [60], основан на правиле приоритета операций, согласно ко­ торому в первую очередь выполняются операции фронта с меньшим полным резервом времени и большей интенсивно­ стью потребления ресурсов. Под фронтом понимается сово­ купность работ, которые могут производиться в данный мо­ мент времени одновременно.

Аналогичный подход используется В. Н. Бурковым и С. Е. Ловецким [5]. При этом предполагается, что скорость выполнения каждой операции прямо пропорциональна коли­ честву ресурсов в некоторых пределах, т. е.

Vijit^Lijrijit), 0

С помощью метода, изложенного в работе R. Blair [57], решение задачи сводится к моделированию на ЭВМ. Цель моделирования — определение различных вариантов рас­ пределения ресурсов в пределах между минимальной и мак­ симальной продолжительностью осуществления комплекса.

Методы решения задач оптимального распределения ре­ сурсов по критерию минимума продолжительности выполне­ ния проекта описаны в работах В. Н. Буркова [4— 7], где по­ лучили дальнейшее развитие точные методы решения.

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

23

основе которых лежит принцип сглаживания потребности в ресурсах, т. е. сдвига операций, обладающих резервами времени, в ближайший интервал, где потребление ресурсов ниже среднего уровня [58, 63, 66].

Попытка решения общей задачи сделана в работе А. А. Me. Gee и М. D. Markarian [67]. Задача заключается в рас­ пределении по операциям имеющихся ресурсов таким обра­ зом, чтобы суммарное их использование в каждый момент времени t не превышало заданного уровня R, а проект вы­ полнялся за время Т и при этом минимизировалась стои­ мость всего комплекса. В основе алгоритма лежит также принцип сдвига операций в пределах резервов времени до получения допустимого решения по ресурсам. Сокращение срока окончания проекта до заданного осуществляется уве­ личением количества ресурсов на критических работах.

Д. И. Голенко [20] рассматривает статистические мето­ ды решения задач оптимального распределения ресурсов при наличии одного или нескольких видов ресурсов, при постоянной и переменной интенсивности их потребления.

В работах С. И. Зуховицкого, И. А. Радчик [27], Б. С. Разумихина [41— 44], А. А. Воронова [17], Е. П. Петруши­ на [40] и многих других [1, 4, 27] получили дальнейшее развитие математические методы решения, где задача рас­ пределения ресурсов по операциям сводится к линейному, квадратичному и целочисленному программированию.

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

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

24

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

§ 2. ОБЩИЕ ВЫВОДЫ И ЦЕЛЬ ИССЛЕДОВАНИЯ

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

Непрерывно растущее число различных методов расчета сетей, как уже упоминалось, не решает данного вопроса. Поэтому необходима разработка общих методов решения сетевых задач, позволяющих оптимизировать сеть не только по времени и ресурсам, но и топологически. Оптимизировать график топологически — это значит найти самый лучший, самый выгодный план выполнения работ при заданных усло­ виях и ограничениях для того, чтобы продолжительность критического пути была минимальной.

Поясним сказанное на примере. Допустим, что имеется какой-либо объект управления (например, комплекс работ по разработке запасов шахтного поля), который можно рас­ сматривать как последовательность взаимосвязанных работ. Укрупненный сетевой график этого проекта представлен на рисунке 1.9. Номера работ проставлены в кружках, а соот­ ветствующие им временные параметры — в квадратах. Пред­ положим, что работы (вершины графа) Хз и х 4 технологиче­ ски могут осуществляться в любой последовательности, но не одновременно. Например, можно пройти сначала выра­ ботку 1 (работа х3), затем — выработку 2 (работа х4), или на­ оборот. Одновременное выполнение недопустимо из-за того,

25

в любом порядке, но одним оборудованием.

ш

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

С помощью анализа расчета сети определяем общую про­ должительность осуществления комплекса в предположе­ нии, что выбрана следующая очередность работ: Х3-+Х4, X7-+XS-+X9. Продолжительность критического пути Х\-*~ -+Xar->~Xe-+X7^>-X8->-X9-*-X)o-+Xn-+Xi2 равна 38. Если зададим теперь новую последовательность Х3-+Х4, Xg-*~X7^-Xg, то про­ должительность критического пути Х1->-Х2->'Х4-+Хз->-Хв-+Х7-+- -*-X9-^-Xio-^Xn-^x\ 2 станет равной 44.

Вариант Х4-+Х3, Хт-^xg-^xg увеличивает Ткр до ^8. Выбрав порядок Х3-+Х4, Xg—>~Х9—>~Х7 ИЛИ Х3-+Х4, Хд-+X7-+Xg, будем иметь новое значение Ткр = 3 3 .

Устанавливая произвольный порядок выполнения кон­ турных работ {хз и х 4; х 7, х 8, хд), будем получать различные значения Ткр. На элементарном примере сетевой модели, со­ держащей всего два контура, показано, насколько сложно решение задачи выбора оптимального (в смысле min Ткр) варианта топологии сети. Методы для реализации задач та­ кого типа неизвестны и для точного решения их можно пред­ ложить только перебор всех вариантов. Но перебор имеет лишь теоретическую ценность, так как приводит к громад­ ному объему вычислений и затрудняет решение практиче­ ских задач большой размерности даже с использованием

26

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

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

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

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

иреализации на ЭВМ.

За д а ч а 1. Для построения многовариантного сетевого

графа (с контурами) найти систему правил, определяемую принятой технологией организации работ.

27