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

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

Все вычисления будем проводить на графе, построенном на языке «работа — связь». Считаем, что временные оценки tt работ i перенесены на выходящие из них дуги. Условим­ ся обозначать продолжительность максимального пути до i-й вершины графа через Lj.

Основные шаги алгоритма:

1. Коды (i, d{) массива L сортируем в порядке увели­ чения номеров вершин j. Здесь df— min^.

2.Ячейки рабочего массива F очищаем нулями. Пола­ гаем Li0 для миноранты io равным нулю.

3.Просматриваем коды (i, j, dt) массива L один раз. Вы­

числения проводим по формуле

где Lj° — первоначальное значение максимального пути до вершины взятое из ячейки (/+ ;) массива F (в начальный момент оно равно нулю);

Lt— максимальная величина пути до вершины i, опре­ деляемая из ячейки (/-И ) в массиве F ;

di— временная оценка вершины i, взятая из рассматри­ ваемого кода (i, j, dt) массива.

Вычисленное по формуле (6.2) значение Lj заносим в ячейку (/+ ;) массива F и далее анализируем следующий код в массиве L. Для каждого кода из массива L проводим вы­ числения по формуле (6.2). Процесс закончится, когда будут просмотрены все коды из L. Так как массив L рассортиро­ ван, то достаточно просмотреть все коды только один раз.

Алгоритм вычисления поздних окончаний работ на гра­ фе, построенном на языке «работа — связь». Вычисления поздних окончаний работ проводятся на обычном сетевом графе, в котором отсутствуют полные контуры. Имеется в виду, что граф уже синтезирован и для работ полных конту­ ров установлена последовательность их выполнения. Вре­ менные оценки ti работ перенесены на дуги.

Основные шаги алгоритма:

1.Позднее окончание L?-° последней завершающей ра

боты графа (мажоранты In ) принимаем равным значению

L?-H, вычисленному по алгоритму, изложенному выше.

lN

140

2.Ячейки рабочего массива F, в котором будут фикси­ роваться величины LF-°, очищаем нулями.

3.Массив L, рассортированный по уменьшению номеров вершин, просматриваем один раз. При этом для каждого оче­ редного кода (i, j, d) находим для i-й работы позднее окон­ чание по формуле

где Lik — позднее окончание i-й работы, вычисленное ранее

при выборе предыдущих кодов (г, d j) из L ;

L4-0— позднее окончание j-й работы из ячейки Значение Lf-° затем заносим в ячейку (/-j—г) и анализи­

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

Алгоритм определения критического пути и резервов времени работ на графе с полными контурами. Основные шаги:

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

2. Для каждой работы — вершины i сетевого графа по формуле (6.2) определяем ее раннее начало — L?-H (величи­

на £Р-Н), т. е. продолжительность максимального пути от

миноранты io до г-й вершины. Значения Lt фиксируем в ячейках массива F (по первому адресу).

3. По формуле (6.3) рассчитываем поздние окончания LJ'0 каждой г-й работы и записываем в ячейках массива

F(по второму адресу).

4.Массив F просматриваем один раз и для каждого i из (/+г)-й ячейки находим величину Att — резерв времени

по формуле

войдет в критический путь.

§ 4. ОПИСАНИЕ ПРОГРАММЫ «ВВОД, КОНТРОЛЬ, КОМПОНОВКА»

Программа «Ввод, контроль, компоновка» предназначе­ на для подготовки исходной информации, которая затем ис­

141

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

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

Работу основных блоков программы «Ввод, контроль, компоновка» покажем на примере формирования исходных данных для алгоритма синтеза сетевого графа по стоимости.

из5л£5.?8ш|,„| " ----^8 5л 2,5, 7,8

Блок-схема программы приведена на рисунке 6.1, она включает следующие основные блоки:

142

1. Ввод информации, перевод исходных данных и пара­ метров из десятичной системы счисления в двоичную, фор­ мирование const (0101— 0127, 1170— 1215). В скобках ука­ заны адреса команд программы.

2. Формирование массива D* с параметрами bt и at , массива D** с параметрами D t и d h массива L с кодами

(i, jf di). Запись массивов на МЛ (1122— 1154, 1235— 1277).

3.Проверка одного входа (миноранты io) и одного выхо­ да (мажоранты iN), анализ отсутствия на графе вершины с номером i, где 0<Ci<iN, N — максимальный номер вершины на графе (0130— 0173).

4.Поиск на графе неполных контуров и печать конту­ ра (0175— 0343, 1163— 1167).

5.Формирование массива полных контуров К (0350— 0437, 1155— 1162, 1220— 1232, 1300— 1345).

6.Блок упорядочения вершин на графе. Новые номера фиксируются в ячейках массива F (0344— 0453).

7.Запись на МЛ рабочих массивов L*, рассортирован­ ных в порядке возрастания и убывания номеров вершин i

иj (0454— 0562).

8.Формирование рабочих массивов V и D*** (0631— 0634, 0563— 0745, 1216— 1217).

9.Запись на МЛ const и параметров I, N, k, h, R q, io, iN

(0476— 0750).

10.Стандартная программа сортировки методом Шелла

(0760— 1064).

11.Стандартные программы перевода чисел из одной си­

стемы счисления в другую: перевод чисел из десятичной си­ стемы в двоичную и из двоичной в десятичную (1065— 1121).

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

назначение этого блока состоит в следующем. Все параметры (аг, 5г, dit *), соответствующие i-м номерам вершин, в ви­

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

В рассматриваемом блоке коды в массивах L, D*, D** располагаются в порядке возрастания новых номеров вер­ шин.

Блок-схема представлена на рисунке 6.2. Назначение операторов:

143

1. Организация цикла для формирования массивов дан ных:

hd i»

2.Формирование кодов (0, Dit dt) и (0, bit аг), засылка их в рабочие массивы D**, D*.

3.Запись массивов D*, D** на магнитную ленту.

4.Получение из массива входных данных рабочего мас­

сива L с кодами (i, j, dt ), где i и j — номера вершин после выполнения блока «Упорядочение вершин».

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

5.Чтение с МЛ массивов D* и D**.

6.Выделение из рабочего массива F новых номеров

(JVhob, 0» 0) и приформирование их к кодам массивов D* и

D**.

7. Сортировка кодов массива D* в порядке возрастания новых номеров вершин.

8.Сортировка кодов массива D** в порядке увеличения новых номеров вершин.

9.Запись на магнитную ленту кодов из D* и D**.

Б л о к 3. Поиск на графе висячих вершин. Блок-схема представлена на рисунке 6.3.

Назначение операторов:

1. Просматриваем коды (i, j, dt) массива Б и в ячейках

144

(f-j-i) и (f~hj) рабочего массива F накапливаем: по первому адресу — количество дуг, выходящих из £-й вершины графа (число п), а по второму адресу — количество дуг, входящих в ;-ю вершину (число т).

2. Анализируем содержимое ячеек рабочего мас­ сива F по второму адресу, т. е. проверяем условие т = 0.

3.Проверяем условия: п= 0?

4.Анализируем: j = i N?

5.При m = N = 0 печатаем пропущенную вершину j и продолжаем просмотр ячеек из массива F.

7.Анализируем: все ли ячейки j просмотрены в масси­ ве F. При полном просмотре массива F все действия опера­ торов заканчиваются, в противном случае вновь выполня­ ется оператор 2.

8.Проверяем условия: п= 0?

Назначение операторов блока 4 (рис. 6.4):

1.Сортировка кодов массива L по возрастанию номеров вершин £ и j методом Шелла.

2.Очистка ячеек рабочего массива F. Организация цик­ ла для массива полных контуров К.

ячейку (Д-f-l)* Далее выполняется оператор 5.

5.При знаке «плюс» в ячейку (/+ 1 ) массива F записы­ вается содержимое (Д +1).

6.Анализ на конец массива К.

7.Организация цикла для просмотра кодов массива L.

8.Выбор на сумматор кода (£, j, dt ) из массива L, фор­ мирование ячеек:

0002) 0000 0000 и

0003) 0000 0000 у.

9. С помощью индексных ячеек 0002 и 0003 анализиру­ ется содержимое (/+£) и (/+ ;) из F, где стоят новые номера

контурных вершин. Если содержимое ( /+ 0 и (/+J) равно ну­ лю, продолжается просмотр кодов из L. В противном случае прежние номера вершин i и j из L заменяются на новые.

Рис. 6.4.

10.Анализ: закончен ли просмотр кодов из L.

11.Сортировка массива L по увеличению номеров вер­ шин i и j. Организация цикла для просмотра кодов из мас­

сивов L и L\, где L — массив кодов (г, j, d *) для всех вер­ шин графа, L\— массив кодов, соответствующих неконтур­ ным вершинам и контур-узлам.

146

12.В массиве L анализируются два рядом стоящих кода.

Вслучае их совпадения первый код заносится в массив L\ и сравнивается со следующим кодом из L. Если эти коды различны, то они заносятся в L\ и последний сравнивается со следующим из L. Из-за рассортированности массива L одинаковые коды будут находиться рядом. Сравнение осу­ ществляется по индексам i и /.

13.Анализ на конец массива L.

14.Формирование количества кодов (дуг) в массиве L.

Ячейки рабочего массива F и пять рабочих ячеек R +1-T-.R+

+5 очищаются нулями.

15.Организация цикла для просмотра кодов массива L\.

16.Выбор очередного кода (г, j, dt) из массива Iq. Про­

бавляется единица) в рабочей ячейке Д + 1 . В кодовую часть ячейки (/+ ;') приформировывается индекс г, по которому произошло изменение в (/+;)•

18. В рабочую ячейку Д +З заносится максимальное из значений (аг + 1 ), получаемых после работы оператора 17, а индекс i, по которому произошло изменение, запоминается

врабочей ячейке Д +4.

19.Проверка неравенства: 2 V > a i+ l. Если оно соблю­

дается, переходим к оператору 20, в противном случае — к оператору 22.

20.Анализ: все ли коды из L\ просмотрены.

21.После полного просмотра массива L\ анализируется содержимое ячейки .R-f-l* Если (Д-|-1)=0, то циклов на

23.В кодовой части ячейки (/-H i) выделяется номер вер­ шины ik, от которой зависит выполнение И

24.Анализ совпадения номеров вершин U = ik. Если они совпадают, то работает оператор 25, в противном случае — оператор 23, где вместо (/-H i)-й ячейки в массиве F рассмат­

Блок-схема представлена на рисунке 6.5.

147