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

связи не существует, то контурная работа соединяется вы­ ходящей стрелкой с мажорантой 1 м•

Правило 15. Внешними работами — вершинами по отно­ шению к рассматриваемому полному контуру — могут слу­ жить работы других полных контуров. Это показано на ри­ сунках :

Правило 16. Если все работы полного контура II выпол­ няются только после завершения работ полного контура I, то на графе они изображаются следующим образом:

50

i , ■

Другими словами, каждая вершина контура I должна соеди­ няться стрелкой с вершинами контура II. При отсутствии одной из таких связей, например

работа п при условии п-^-т по времени может начинаться параллельно с работами i и но обязательно после k. Если же для п-й работы будет лучше порядок т-^п, то, естествен­ но, она выполнится после окончания i-й и j-й работ, так как т-я работа будет начата только после работ i и у.

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

а

Подобное изображение противоречит правилу 7.

В полном контуре, в отличие от рассмотренного, две лю­ бые работы соединены стрелками в двух различных направ­ лениях :

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

Правило 17. На графе не должно быть контуров, кроме полных. Машинный алгоритм обнаружения всех контуров, кроме полных, изложен в первом параграфе главы VI.

§ 2. АЛГОРИТМ ВЫБОРА ОПТИМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ВЫПОЛНЕНИЯ РАБОТ ПОЛНОГО КОНТУРА

ПО КРИТЕРИЮ ВРЕМЕНИ

1.Общие замечания. Имеем комплекс работ, образу

щих полный контур. Обозначим эти работы через 1, 2, . . .

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

Если допускается од­ новременное выполне­ ние работ, то в состав полного контура та­ кие работы не вклю­ чаются. В сетевом гра­ фе их можно предста­

вить параллельными, и по времени это Судет наилучшии вариант.

Предположим, что имеются работы i*, которые не при­ надлежат к полному контуру и предшествуют контурным работам или следуют за ними. Назовем подобные работы

62

внешними по отношению к контурным. Таким образом, ра­ боты полного контура и внешние составляют проект (рис. 3.1). Пусть проект начинается с работы г0 и заканчивается работой , которые соответственно назовем минорантой и мажорантой. Обозначим через tj продолжительность выпол­ нения j-й внешней работы. Тогда длина максимального пути Li от миноранты го до г-й работы полного контура представ­ ляет промежуток времени, по истечении которого может быть начата г-я работа.

Если Li = 0 , то внешних работ, предшествующих г-й, нет, и г-я работа комплекса может начинаться в любой момент времени. Обозначим через L * длину максимального пути от г-й работы контура до мажоранты гм. Тогда работы, лежа­ щие на этом пути, будут осуществляться в течение проме­

=1, 2 и 4 полного контура.

2.Постановка задачи. Для работ 1, 2, . . . , г, . . . , пг пол­ ного контура I необходимо выбрать такой порядок выполне­ ния, при котором длина критического пути проекта от ми­ норанты г0 до мажоранты гм минимальна. Как уже отмеча­ лось, критический путь зависит от топологии сети. Поэтому для каждого выбранного порядка следования работ полного контура продолжительность критического пути проекта есть

величина определенная.

Если учесть, что количество всевозможных последова­ тельностей для тп работ проекта равно числу перестановок Pm — 1 •2 •3 •... •т, то перебор такого количества и выбор наилучшей последовательности при достаточно большом т практически невозможны. Вознйкает необходимость разра­ ботки специального алгоритма.

53

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

Разберем действие алгоритма на конкретном примере (рис. 3.2). Заданный полный контур I состоит из четырех работ ( i = l , 2, 3, 4). На рисунке 3.2 они условно изображе­ ны прямоугольниками, в каждом из которых проставлена продолжительность £г в днях. Контурные связи на рисунке не представлены. Предполагается, что любая пара работ связана противоположно направленными дугами. Работы, внешние по отношению к работам полного контура, на ри­ сунке не показаны. Продолжительность внешних путей L t и Lt* для каждой i-й работы полного контура проставлена над стрелками.

Одновременное выполнение хотя бы двух из четырех за­ данных работ недопустимо. Необходимо уложить их в цепоч­ ку так, чтобы общая продолжительность критического пу­ ти от i0 до гм была бы минимальной. При этом следует учи­ тывать, что работа i= 1 полного контура может выполнять­ ся не раньше, чем через два дня, работа i= 2 — не раньше, чем через 7 дней, и т. д. Работа i— 4 может начинаться в любое время, так как L4= 0 (рис. 3.2). Внешние работы, ле­ жащие на пути длины L2*, например, будут следовать после завершения контурной работы г = 2 в течение 30 дней.

Рассмотрим действие алгоритма по шагам.

Шаг 1. Построение исходной таблицы. Для работ полно­ го контура строим таблицу, количество строк которой равно числу контурных работ (п г = 4). Количество столбцов таб­ лицы постоянно для любого полного контура и равно шести

(табл. 3.1).

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

54

торый будет показывать искомый порядок осуществления работ i. Например, р = 1 означает, что работа i, против ко­ торой стоит этот индекс, должна выполняться в комплексе первой, при р = 2 — второй и т. д. В начальный момент при­ нимаем все значения р равными нулю, а это говорит о том, что ни одна работа полного контура не поставлена на оче­ редь. В третьем столбце таблицы помещаем суммарные зна­ чения продолжительности внешних предшествующих работ Lit в четвертом — время выполнения г-й работы tt, в пятом— сумму продолжительностей внешних последующих работ Li. Шестой столбец рабочий и используется при вычислениях.

Строки таблицы располагаются сверху вниз в порядке уменьшения величин L *. При одинаковых значениях L * в первую очередь записывается строка для контурной работы i с меньшей продолжительностью t t . При одинаковых зна­ чениях L * и tt первой заполняется строка с меньшим зна­ чением L i .

Шаг 2. В третьем столбце (табл. 3.1) среди элементов находится минимальный. Если имеется несколько одинако­ вых минимальных значений Lt, то выбираем верхний в столбце. В нашем случае Lt = 0 для г = 4 . В шестом столбце таблицы в строке выбранного элемента L4 делаем пометку «min». Работа i= 4 может быть взята в качестве первооче­ редной. Условимся обозначать ее индексом I (£ = 4).

Шаг 3. Для отмеченной на шаге 2 строки l-Vi работы оп­

ik столбца таблицы, находящимися выше строки с отметкой «min». Строки ik, для которых справедливо неравенство

отмечаем в шестом столбце знаком «минус». При соблюде­ нии условия (3.1) выбранную работу с номером Z= 4 целесо­ образно производить раньше любой i*-й работы, так как в течение промежутка времени Lik одновременно будут выпол­

няться внешние работы на пути длины L* и контурная ра­ бота I.

Строки, для которых неравенство (3.1) не удовлетворя­

помечаем знаком «плюс». Действие шага 3 на этом закан­ чивается.

Поскольку неравенство 3.1 справедливо для 2, то в первой строке шестого столбца таблицы 3.1 ставим знак

55

«минус» (7 ^ 0 + 3 ). Вторую строку для i= 1 отмечаем зна­ ком «плюс», так как удовлетворяется условие (3.2): 2<С0+ + 3 . Выбор одной из работ, строки которых помечены знаком «плюс», может оказаться наилучшим вариантом на данном этапе, чем ранее найденная на шаге 2 работа I с отметкой «min». Это условие проверяется на шаге 4.

Шаг 4. В шестом столбце сверху вниз последовательно просматриваем обозначенные плюсом строки работ г* и для них проверяем выполнение двух условий:

£ i+ f/+ m a x {L z*; fift+ L ?A}> L iA+ fiA+m ax{Lift; ti+Li*}; (3.3)

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

Соблюдение условия (3.3) означает, что порядок следо­ вания работ г*-*-/ лучше, чем Z-W*, поскольку продолжи­ тельность T(l-*ik)> T {ik-+l). Следовательно, работа г* долж­ на начинаться первой.

Неравенство (3.4) проверяется при выполнении условия (3.3), которое устанавливает общую продолжительность Ткр с учетом работ, уже поставленных на очередь, включая ана­ лизируемые работы I и ik .

Если у рассматриваемой работы г* продолжительность максимального пути от момента ее начала до мажоранты — правой части неравенства (3.4) больше суммы продолжи­ тельностей работ, не поставленных на очередь — левой ча­ сти неравенства (3.4), то ее необходимо осуществлять пер­ вой (рис. 3.3, а). Это вытекает непосредственно из того, что ik -я работа, согласно (3.4), лежит на критическом пути. Дей­ ствительно, если принять во внимание общую продолжи­ тельность работ k с индексом р = 0, включая суммарную продолжительность их внешних работ на путях L** (левая часть неравенства (3.4)), то она будет меньше суммарной про­ должительности анализируемой й работы и внешних ра­ бот пути L*k (правая часть условия (3.4)). Другими словами,,

если поставить на очередь оставшиеся контурные работы к, то найденная к данному моменту продолжительность T(ik -W) не увеличится. Это говорит о том, что ik лежит на кри­

56