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

Поиск любого пути от а до &осуществляется следующим образом. Берем первый узел Х\ = а, помещенный в рабочую ячейку do, и отыскиваем все коды из L, у которых на месте i или у стоит номер узла Х\. Все выбранные из L коды запи­ сываем в массив 0 , который предназначен для фиксации в нем кодов, являющихся разветвлениями пути между узла­ ми а и Ь. Последовательность дуг (кодов) искомого пути рас­ полагаем в массиве R со знаком «плюс» или «минус» в за­ висимости от того, пройдет ли путь от а до Ъв направлении дуги Uij или против него.

Вмассиве © выбираем последний занесенный в него код

иобозначаем его через

Этот код помещаем в массив R (вслед за кодами, которые в нем уже записаны) со знаком «плюс», если номер вершины Х\, указанный в ячейке do, совпадает с I. Если же х\ из do совпадает с k, код (2.3) заносим в R со знаком «минус». В на­ чальный момент массив R пуст, и код (2.3) записываем в первую ячейку. Одновременно в массиве 0 очищаем нулем последнюю ячейку, в которой находится код (2.3). В ячейку

сим тот из узлов I или k, который является следующим про­ межуточным узлом на пути от а до & независимо от того, будет ли искомый путь проходить в направлении дуги или против него. Далее весь процесс повторяем заново. В массиве L просматриваем все коды и отбираем те, у которых на ме­ сте i или 7*стоит номер Х2 , находящийся в ячейке do.

Выбранные из L коды помещаем в массив 0, начиная с первой свободной (очищенной) ячейки, вслед за кодами, ко­ торые там уже есть. Затем из массива 0 берем для занесения в R последний код, после чего определяем следующий про­ межуточный узел Хз искомого пути и записываем в do. Этот процесс повторяем до тех пор, пока в качестве узла Xk не бу­ дет взят узел х = Ъ. Тогда первый путь от а до Ъ, т. е. Х\= а—»- -+Х2- * . . .-^хп = Ъ, считается найденным.

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

вdo, и анализируем знак ячейки (b-\-xk) рабочего массива В. Количество ячеек в массиве В равно числу вершин графа G(X, U). Он предназначен для того, чтобы в его знаковой ча­ сти фиксировался признак (знак «минус») включения оче­ редной вершины в искомый путь. Знак «минус» записываем

вячейку (&-И) каждый раз, когда продолжением пути яв­

43

ляется вершина i, и меняем на знак «плюс» при исключении этой вершины из массива В. В качестве массива В может быть взята знаковая часть первых N ячеек массива © (N — количество вершин графа). Если при анализе знак ячейки (Ь + Хь) оказывается отрицательным, то код (2.3) из 0 вычер­ киваем и в массив В не заносим. Далее в массиве © с конца просматриваем оставшиеся коды и процесс продолжаем.

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

Для определения длины пути следует выделить в кодах массива R значе­ ния весов atj со знаком кода и про­ суммировать их. Найденный путь и его длина выдаются на печать, и весь процесс повторяется заново для пои­ ска новых путей. С этой целью в мас­ сиве R выбираем последний код, из которого выделяем номер узла, не совпадающий с содержимым do. В массиве R последний код заменяем нулем, затем вновь рассматриваем последний код из 0 и весь процесс продолжаем заново. Поиск заканчи­ вается тогда, когда массив 0 полно­ стью очищен. Для массивов L и 0 нужно выделить столько ячеек, сколько дуг на графе. Массив R зай­ мет N ячеек.

Описанный машинный алгоритм был реализован в виде стандартной программы на ЭВМ «Минск-22». Укрупненная блок-схема программы представлена на рисунке 2.3.

КРАТКОЕ ОПИСАНИЕ БЛОК-СХЕМЫ:

Блок 1. Формирование рабочих массивов L, 0, R. Блок 2. Подготовка исходных данных к вычислениям.

Блок 3. Выбор узлового события и зависящих от него собы­ тий из массива L.

Блок 4. Поиск очередного узла, не образующего контура.

44

Г л а в а III

СИНТЕЗ СЕТЕВОГО ГРАФА

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

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

46

очень сложен, то возможных вариантов изображения сете­ вых графиков насчитывается огромное количество.

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

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

§ 1. ОПРЕДЕЛЕНИЕ И ПРИНЦИПЫ ПОСТРОЕНИЯ ПЕРВОНАЧАЛЬНОЙ СЕТЕВОЙ МОДЕЛИ

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

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

Правила построения сетевой модели:

Правило 1. Количество вершин на графе равно числу моделируемых работ, так как каждая работа изображается кружком.

Правило 2. Номера работ на сети не должны повторяться. Правило 3. На графе должны быть одна начальная ра­

бота — миноранта и одна конечная — мажоранта.

Правило 4. Стрелки показывают возможные связи между работами. Длина их не имеет значения.

Правило 5. При наличии нескольких начальных (ко­ нечных) работ на графе вводится фиктивная миноранта (ма­ жоранта), которая должна быть соединена с указанными работами стрелками.

Правило 6. Все числовые характеристики работ (время, ресурсы и т. д.) представлены в узлах.

47

Правило 7. Стрелка, связывающая две любые работы i и j в направлении означает, что работа j может начи­ наться только после завершения i-й работы.

Правило 8. Работы i и j, не соединенные стрелками, счи­ таются независимыми и могут выполняться относительно друг друга в произвольном порядке, если не существует ка­ кой-либо третьей работы к, связывающей их следующим об­ разом :

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

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

Поскольку указанное обстоятельство не гарантирует оптимальности выбранной топологии и минимум Ткр, введе­ ны дополнительно новые правила.

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

AS

для трех работ —

для четырех работ

Правило 11. Работы, входящие в состав полного конту­ ра, назовем к о н т у р н ы м и . Контурные работы могут сле­ довать в произвольном порядке относительно друг друга, но не одновременно (параллельно).

Правило 12. На контурные работы правило 7 не распро­ страняется, так как окончательный порядок выполнения контурных работ устанавливается в процессе вычислений.

Для полных контуров, состоящих из трех работ (напри­

с внешними работами, не входящими в его состав, должна удовлетворять следующим правилам.

Правило 13. Каждая работа полного контура должна быть связана входящей стрелкой хотя бы с одной внешней работой, не принадлежащей к полному контуру. Если такой связи не существует, то контурная работа соединяется вхо­ дящей стрелкой с минорантой /0:

Правило 14. Каждая работа полного контура должна быть связана выходящей стрелкой хотя бы с одной внешней работой, не принадлежащей полному контуру. Если такой