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

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

Рис. 3.3.

Условие (3.4) позволяет установить принадлежность ра­ бот I и г* к критическому пути. Если работы г* и I располо­ жены на критическом пути, то, согласно (3.3), порядок i* -> -W будет предпочтительнее, и на очередь ставится работа ik, поскольку общая продолжительность проекта Т vip = T(ik~+

Это вытекает непосредственно из условия (3.4), левая часть которого представляет минимально возможное время для осуществления оставшейся части проекта. Действитель­ но, если неравенство (3.4) справедливо при

max{L*ft; ti-\-Li*)=Likf

57

то в правой его части величина ?гА+^Гйпоказывает, что вре­ мя завершения работы ikи всех работ пути L*k больше сум­

марной продолжительности работ, не поставленных на оче­ редь (р = 0 ). Следовательно, ik лежит на критическом пути.

и I находятся на критическом пути. Действительно, соглас­ но (3.4), суммарная продолжительность работ с индексом р = = 0 меньше величины 2 ^ + 2z+£/*. Учитывая (3.3), работу

ik необходимо начать раньше 1 -й.

При одновременном соблюдении условий (3.3 )и (3.4) оче­ редной порядковый номер р присваивается рассматривае­ мой й работе и проставляется в 2*-й строке таблицы 3.1. Далее выполняется шаг 5. Если не удовлетворяется хоть од­ но из неравенств для всех строк ik таблицы, лежащих выше

I, то порядковый номер р ставится в строке I с minL* = Z+ i

В нашем случае для ik= 1 (вторая строка таблицы 3.1 поме­ чена знаком «плюс») справедливо неравенство (3.3):

(2 5 + 2 0 + 5 + 3 )+ 0 + 0 < 2 5 + m a x{1 5 ; 3+5}; 53>40.

Так как строк со знаком «плюс» в шестом столбце таблицы больше нет, то порядковый номер р = 1 будет у работы 2 = = 1— 4 и записывается во второй столбец таблицы 3.2.

Шаг 5. Для вычисления общей продолжительности про­ екта на каждой итерации находим две суммы: <+* и о2”* Пер­ вая сумма представляет отрезок времени от момента начала проекта до момента окончания работы полного контура i, которой присвоен очередной индекс р = п :

о2в после каждой очередной итерации увеличивается и, ко­

58

гда станет на очередь последняя работа полного контура, будет равно

После первой итерации имеем:

c^m axfo.*0; o11-{-Li*}=max{0; a11JrL i*\=311Jr Li*=

Для рассматриваемого примера, используя данные таб­ лицы 3.1, для i= l= 4 получаем две суммы:

Шаг 6. Для работы i полного контура, которой присво­ ен индекс р, находим сумму £ г+ £ * . Эту величину вычита­ ем из всех элементов третьего столбца таблицы 3.1. Если при этом получится отрицательное число, то вместо него в тре­ тий столбец заносим нуль. Разность будет отрицательной,

шествующих внешних работ, что означает равенство нулю длины L.

Результаты вычитания показаны в таблице 3.2.

Шестым шагом заканчивается очередная итерация и действие алгоритма повторяется с шага 2. Строки, в кото­ рых индекс р проставлен, т. е. р~^ 1, в последующих итера­ циях не рассматриваются. Таким образом, за. т (т — коли­ чество работ полного контура) итераций устанавливается порядок следования работ заданного полного контура, т. е. определяются индексы р для всех работ.

59

Для нашего примера на второй итерации верхний в столбце минимальный элемент Lt будет выбран для i = l =

Для определения Ткр на каждой итерации по формулам (3.5) и (3.6) проводим следующие вычисления:

IV 0^ = 52+ 5= 57; o24=max{67; 57+0}=67.

Следовательно, Ткр = 67.

Окончательный вариант распределения работ полного контура во времени представлен на рисунке 3.4. Здесь обо-

Рис. 3.4.

60

значения работ полного контура и величин Lt и Lt* совпа­ дают с элементами рисунка 3.2. Легко проверить, что поря­ док выполнения работ полного контура на рисунке 3.4 яв­ ляется оптимальным. Любой другой вариант последователь­ ности дает большую длину критического пути. Например, при 2->-4->-1->-3 продолжительность Ткр = 7 0 , а при 2->4->■ ->3->1 Т кр = 7 5 .

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

1.Набор правил, лежащих в основе предложенного алго­ ритма, дает достаточно хорошее приближение к оптимуму.

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

3.В ряде случаев величину Ткр можно улучшить за счет перемещения работ с минимальным значением индекса р при L t = 0 в конец последовательности. Это обусловлено тем, что в начальный момент первый порядковый номер р при­ сваивается работам, для которых Lt= 0. Если tt работ до­

статочно велико (например, t£(P=i) > L A(P» 2)) , то последующие работы начнутся позже, чем это допустимо.

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

§ 3. ПОСТРОЕНИЕ ОПТИМАЛЬНОГО СЕТЕВОГО ГРАФА

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

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

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

61