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

= max{max[0-1-304-3—4]}=тах{29; 30}=30. k

Теперь перейдем к следующему шагу.

Шаг 5. Определение оптимальной последовательности выполнения работ рассматриваемого полного контура 7. В результате действий шагов 3 и 4 найдены значения L* и Lt и, тем самым подготовлена информация для использо­ вания алгоритма А. В нашем примере в контуре 7 = 1 (рис. 3.9) должен быть установлен оптимальный порядок осуще­ ствления работ 3 и 4 при вычисленных значениях L3= 0,

П= 3 4 , L4= 2 и L\ = 2 5 .

Реализуя алгоритм А, получаем в полном контуре 7 = 1

порядок следования работ 3->4. Таким образом, вместо контура 7 = 1 окончательно имеем только одну дугу U3 .4. Внеся это изменение в граф, представленный на рисунке 3.9, синтезируем новый граф (рис. 3.11) с одним полным кон­ туром II. Граф на рисунке 3.11 служит объектом дальней­ ших действий алгоритма.

Шаг 6. Анализ условия: все ли полные контуры про­ смотрены. Если в графе на шаге 5 работы всех полных кон­ туров вытянуты в цепочку, то он и будет искомым сетевым графом. На этом шаге алгоритм заканчивается. Если же в графе имеется хотя бы один нерассмотренный полный кон­ тур, то повторяем действия алгоритма с шага 3.

Граф, полученный на шаге 5, принимаем за исходный и переходим к действиям шага 3, т. е. снова определяем ран­ ние начала работ сети, для чего временно контурные связи полного контура вычеркиваем.

В нашем примере шаг 3 выполняется относительно гра­ фа, представленного на рисунке 3.11. На следующей итера­ ции в качестве выбранного полного контура 7 берем контур II. На шаге 6 убеждаемся, что все полные контуры просмот­ рены. Оптимальный сетевой граф изображен на рисунке

71

Г л а в а IV

ОПТИМИЗАЦИЯ СЕТЕВЫХ ГРАФИКОВ ПО РЕСУРСАМ

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

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

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

73

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

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

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

§ 1. ПОСТАНОВКА ЗАДАЧИ

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

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

а) минимальная величина затрат (минимальный объем ресурсов) rmin , при которой работа производится за макси­ мальное время Dt;

б) максимальная величина затрат (максимальный объ­ ем ресурсов) rmax, при которой работа выполняется за ми­ нимальное время di.

Закон потребления ресурсов выражается линейной зави­

где и bt— заданные величины.

74

Из поставленных условий следует, что размер потребле­ ния ресурсов для i-й работы и ее продолжительность заклю­ чены в пределах

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

Ниже приводим эвристический алгоритм решения сфор­ мулированной задачи, в основу которого положена идея градиентного метода [33].

§ 2. АЛГОРИТМ СИНТЕЗА И ОПТИМИЗАЦИИ СЕТЕВОГО ГРАФИКА ПО СТОИМОСТИ

Опишем шаги алгоритма на конкретном примере. По пра­ вилам, изложенным в первом параграфе главы III, строим исходный граф G{X, U) с полными контурами (рис. 4.1). Чис­ ловые характеристики работ исходной сети приведены в таблице 4.1. Предположим, что объем имеющихся ресурсов составляет Во = 60. Требуется на основе этих данных уста­ новить в сетевом графике оптимальный порядок выполне­ ния контурных работ 3, 4 и 7, 8, 9 таким образом, чтобы длина критического пути Ткр была минимальной и объем используемых ресурсов на всех работах не превышал уровня i?o= 60 .

Шаг 1. Вводим фиктивную вершину г= 1 2 . Временную оценку работы 1 1 переносим на дугу (1 1 , 1 2 ).

Шаг 2. Полагаем все временные оценки работ — вершин графа (рис. 4.1) равными £г,тах = Di% Согласно формуле

75