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

;Ч*Б ОД 1 0 фРВ 1998

На правах рукописи ХАДОНОВ Зураб Мусаевич

УДК 681.3

ТЕОРИЯ И ПРАКТИКА АВТОМАТИЗИРОВАННОГО

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

Специальность 05.13.12 — Системы автоматизации проектирования

Автореферат диссертации на соискание ученой степени доктора технических наук

Москва 1998

Работа выполнена в Московском государственном горном университете и Северо-Кавказском государственном технологическом университете.

Научный консультант

академик МАИ, РАЕН, докт. техн. наук, докт. фнз.-мат. наук, проф. В. А, ГОРБАТОВ.

Официальные оппоненты:'

Лауреат Государственной премии СССР,

академик РАЕН, проф., докт. техн. паук В. Н. БУРКОВ,

Лауреат Государственной премии РФ, академик МАИ, РАЕН, проф., докт. техн. наук В. М. ЛОХИН,

проф., докт. фнз.-мат. наук Р. В. ХАИРУЛЛИН.

Ведущая организация — АОЗТ «Кавказэлектронстрой» (Владикавказ).

Защита диссертации состоится 20 февраля 1998 г. в 14 час. на заседании диссертационного совета Д.05'3.12.12 в Московском государственном горном университете по адресу: 117935, Москва, Ленинский проспект, 6.

С диссертацией можно ознакомиться в библиотеке Московского государственного горного университета.

Автореферат разослан 20 января 1998 г.

Ученый секретарь диссертационного -овета

доц., канд. техн. паук М. А. РЕДКОЗУБОВ.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы.

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

Можно выделить четыре этапа развития систем автоматизированного проектирования (САПР) в строительстве.

Первый этап (60-е годы). Средства вычислительной техники используются для решения отдельных задач проектиро-вани я:

— расчет железобетонных строительных конструкций, форм железобетонных элементов, арматуры и закладных де-I алей;

- расчет металлоконструкций и других строительных конструкций;

— некоторые расчеты при проектировании технологии и организации строительства.

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

Второй этап (70-е годы). Создаются САПР с доминирующим позадачиым переходом, при котором, система состоит из разработанных отдельных задач, при этом функциональные задачи автоматизируются отдельно. .Математическое обеспечение САПР включает метод конечных элементов, методы исследования операций. Разрабатываются теория автоматизации календарного планирования и теория проектирования возведения объектов, при этом применяются методы имитационного моделирования. Главная цель разработки САПР на этом этапе — сокращение числа проектировщиков.

Третий этап (80-е годы). Совершенствование проектирования на основе системного анализа. САПР — диалоговые интегрированные системы, охватывающие все этапы проектирования с ориентацией автоматизированного выполнения чертежных работ. Разрабатываются системотехнические принципы стыковки и совместимости систем архитектурно-строительного проектирования зданий и сооружений со смежными системами организационно-технологического проектирования, управления строительством. Начало реального внедрения информационных технологий автоматизированного проектирования.

Четвертый этап (90-е годы). САПР —сеть автоматизированных рабочих мест (АРМ), охватывающая весь процесс проектирования. Разрабатываются базы знаний, экспертные системы, информационные средства работы с трехмерной графикой. Применяются методы искусственного интеллекта и дискретной математики (компьютерно-информационной математики). Дальнейшая интеграция разрозненных задач в сложные автоматизированные системы, включающие в себя АРМы чертежного, информационно-поискового, расчетного обеспечения.

Одной из основ математического обеспечения разрабатываемых САПР являются сетевые модели. Первые версии методов СРМ (Critical Path Method), PERT (Programm Eva-lution and Review Technique) основывались на сетевых моделях с детерминированной структурой сети, при этом в методе СМР параметры работ также детерминированы, а в методе PERT—вероятностные величины. Более поздней версией методов, основанных на сетевых моделях, является метод GERT (Graphical Evalution and Review Technique), ориентированный на сетевые модели, вероятностной структурой. Как продолжение этого направления, интенсивно разрабатываются сетевые модели не только с вероятностной структурой, но и модели с нечеткой структурой и нечеткими данными. Это объясняется интенсивным использованием сетевых моделей при финансовой интерпретации. На основе сценарного подхода в финансовой области появились пакеты «On Target 1.0» (фирма Symantec), «Новый Атлант»'(фирма Галактика), «Project 5.0» (фирма Про-инвест Консалдинг) и другие для календарно-сетепого планирования, управления и прогнозирования инвестиционных проектов.

В решение проблем создания САПР технологий управления распределенными системами, в том числе при строительной интерпретации, большой вклад внесли ведущие ученые

B. Н. Бурков, В. А. Горбатов, В. М. Лохин, Б. А. Картозия,

C. А. Редкозубое, А. П. Полежаев, О. В. Логиновский, В. Ф. Макаров, Д. С. Самойлов, А. А. Гусаков, С. А. Силенко, П. Б. Каган, А. Кофман, Г. Дебазей, А. В. Гинзбург, П. Пако, Р. Морган, М. Ховард, Дж. Кэлли, Дж. Гиллерсн, В. П. Румянцев, В. А. Кузьмов, Ю. Б. Розаев, В. И. Сосков, Р. Булд-сон, Б. Рой, Д. Фалкереон, У. Фрезер и др.

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

Если при финансовой интерпретации сетевых моделей основной задачей является оценка принимаемых решений в зависимости от сложившейся ситуации, то при строительной интерпретации основной задачей является формирование «точечного» управления компонентами строительного процесса. Отсюда, структура модели и тип данных в первом случае являются вероятностными, нечеткими, во втором случае — детерминированными.

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

Работа выполнялась в рамках научно-технических государственных и отраслевых программ, в том числе:

— научно-тематических планов министерства общего и профессионального образования РФ;

— межвузовской научно-технической программы, утвержденной приказом Госкомвуза РФ № 630 от 16.10.92 г.;

— программы правительства РСО-Алання «Производственные ресурсы РСО-Аланни» и ряда других программ.

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

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

Задачи исследований.

Вышесформулированная научная проблема определила следующие задачи исследований:

— обобщение сетевой модели для случая распределенных систем и аналитическое задание соответствующих диаграмм Ганта с целью организации вычислительного процесса, оптимального как по временной, так и по емкостной сложности, при автоматизированном проектировании гибких технологий управления;

— разработка теории оптимизации ресурсно-временных характеристик проекта;

— исследование оптимального ресурсно-временного распределения в случае альтернативного ресурсного обеспечения и в случае непредвиденных, чрезвычайных ситуаций при реализации проекта;

— разработка инструментальных программных средств автоматизированного проектирования гибких технологий управления распределенными системами и внедрение их при строительной предметной интерпретации в промышленность и учебный процесс в университетах.

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

Защищаемые положения и научная новизна работы заключается в:

— обобщении сетевой модели для распределенных систем, при котором выявлена связь между полным временным резервом события и критическими временами сетевой модели и ее подмоделей, вершина сочленения которых соответствует этому событию;

— предложении аналитического булевого задания диаграммы Ганта, позволившем оперировать с диаграммой как с системой булевых функций, используя при этом аппарат булева анализа;

— впервые разработанном теоретико-графовом аппарате ресурено-временной оптимизации проекта, основанном на ха-рактеризации диаграмм Ганта и раскраске введенных графов связности;

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

Практическая значимость диссертации состоит в:

— разработке программных инструментальных средств, позволивших автоматизированно проектировать и моделировать гибкие технологии управления распределенными системами;

— промышленном внедрении разработанных методов, алгоритмов и программных инструментальных средств при строительстве и модернизации горных и других предприятий;

— использовании научных результатов в учебном процессе строительных и горных специальностей университетов.

Реализация, внедрение и использование результатов диссертационной работы.

Разработанные модели, методы, алгоритмы и программные средства реализованы на современных ПЭВМ с помощью языка С++ и успешно внедрены в АО «Владикавказ-строй», АОЗТ «Кавказэлектронстрой», АО «Кавказтранс-строй» с экономическим эффектом свыше 3 млрд. руб. в год в ценах 1995 г., о чем имеются соответствующие акты о внедрении; использованы в учебном процессе при чтении дисциплин «Управление строительным производством», «Разработка САПР строительных технологий» в Северо-Кавказском государственном технологическом университете и при чтении дисциплины «Методы оптимизации» в Московском государственном горном университете.

Диссертация обобщает результаты тридцатилетних исследований, проведенных под руководством и при непосредственном личном участии диссертанта.

Апробация работы.

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

всероссийских и республиканских симпозиумах, совещаниях, в том числе, международной конференции по логическому управлению (Варна, 1994), Всемирном конгрессе «Информационные процессы, технологии, системы, коммуникации и сети» (Москва, 1995), Всемирном конгрессе «Информационная математика, кибернетика и искусственный интеллект в информа-циологии» (Москва, 1996), Международном симпозиуме «Информационная математика в информациологии» (Ижевск, 1997).

Публикации.

Основные положения диссертации отражены в 30 публикациях, в том числе, трех монографиях.

Объем и структура диссертации.

Диссертация состоит из введения, пяти глав, содержит 102 > рисунка, 21 таблицу и список литературы из 74 наименова-

\ ний.

И

Основное содержание работы

Будем называть проектом совокупность событий (операций), необходимых для достижения некоторой цели, длительность каждого из которых нам известна или определена экспертным путем, и которые связаны отношением частичного порядка.

Проект может быть представлен сетевой моделью (взвешенным графом) или логической диаграммой <(У, )}), (<{^(5/, 5у)})>, каждая вершина которой взаимнооднозначно соответствует событию : г^еУ, и взвешена временем его выполнения 1(81), дуга (и,-, — транспортной операции (5,, Б/), реализующей транспортирование (транспортное запаздывание) результата выполнения события для выполнения события Б; за время, равное /(5,,

При разработке проекта необходимо составить перечень событий и операций и определить их трудоемкость.

Сетевую модель с начальным событием 51+ и конечным —

можно рассматривать как интервал [5|+, при теоретико-решетчатой интерпретации: ( у^г 5л_])(51+<

сЯ, <£„-)•

Путь, определяющий минимальное время (5!+, 5„~) выполнения всех событий (операций), задаваемых сетевой моделью [5|+, 5Я~], называется критическим. В дальнейшем Тт\п (¿>1+, 5Я~) будем называть временем критического пути или критическим временем.

Очевидно, что критическим путем является путь, составленный из событий и операций, сумма времени выполнения которых максимальна.

Вычисление критического времени сводится к применению рекурсивной процедуры:

для события 5у вычисляется максимум суммы

шах + ( <?,)), ^ е= Г~] (5,)

к

с последующим суммированием его с временем выполнения t(Sj) события Sj, полученное число сопоставляется с событием 5у-:

7(5/)= 4 тах^&ь) + $;)). (I)

к

При вычислен»» полагаем 51+) равным 0. Оче-

видно, что T{Sj) есть критическое время сетевой модели [5|+, 5у-]". При ] = п, в итоге получаем, что критическое время сетевой модели [5,+,

События (операции), включенные в критический путь, называются критическими, невключеппые — некритическими.

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

— время /(5; )—ожидаемое время наступления события

— время /*(£/) —предельное время наступления события ■V/ , превышение которого приведет к изменению общего времени завершения всего проекта.

Для критических событий предельный срок (*(5{) совпадает с ожидаемым временем /(3, ). Эти события не допускают никакого запаздывания н сроках их наступления, другими словами, критические операции не допускают никакой задержки в их выполнении.

Для каждого некритического события важно определить предельный срок его наступления, т. е. срок, превышение которого приведет к задержке выполнения всего проекта. Разность —называется полным временным резервом АI (5,) события 5, .

Определим синдром С ), порожденный вершиной как граф <У/, состоящий из вершин и(5у), \з(5,)<

<и(5у)<гз(5л_) и дуг, соединяющих эти вершины; антисиндром С(54), порожденный вершиной как граф <>, состоящий из вершин г>(5у), ).

Утверждение 1. Полный временной резерв события удовлетворяет соотношению (2):

+ 1 Sя-) + t(S¡)-(Txp{S¡+, 5,) + Ткр{Бг 5„-)). (2)

где Гкр |(51+, 5;)—критическое время антисиндрома С(5г); ТК9(81 5п_) —критическое время синдрома С(5().

Сетевая модель с точностью до временных резервов событий определяет диаграмму Ганта.

Диаграммой Ганта называется двухвходовая таблица, каждой строке которой взаимнооднозначно соответствует событие или операция, столбцу—временной квант, н если 1-е событие (операция) выполняется в /-м кванте, то клетка (¿, /) отмечается штриховкой.

Для аналитического задания диаграмм Ганта предложим булеву модель этих диаграмм.

Каждое событие 5/ '(операцию (Э^ 5/)) будем представлять в виде булевой функции /(Х + 2), где / = 0, 1; X, 2—десятичные эквиваленты двоичных векторов, Н--операция

арифметического сложения.

Для этого событие 5/ (операцию (5,, 5у)) будем рассматривать как временной ряд. На отрезке [0, Ткр (£1+, 5„-)] введем эталонные переменные (<),:

0, если 0 < £ < 2_1 • Гкр(5, + , Я«-)

1. если 2-1-Ткр(5, + , 5л-)<;<.Гкр(5Л5д-)

(3)

хг V) -

0, если 0 < / < 2-' • Ткр (5,+, 5,")

1, если 2-»-< 2~>• Гкр(V. 5Я")

0, если 0<^<2-т.7,1£р(51 + ,

1, если 2-1 • 7кр (5,+, V) < * < 2' -г • Гкр (5,+ /5п-).

кр

Эталонные переменные (0 являются периодическими, нами указан первый период этих переменных — соотношение (3), где число у — глубина временного квантования, равная значению соотношения (4):

у

где [] — ближайшее большее целое.

Эталонные переменные определяют пространство, в котором диаграмма Ганта задается в виде системы {/(5(),

)} булевых функций, число которых равно сумме событий и операций. Размерность пространства равна глубине квантования, точки этого пространства соответствуют конституентам — временным квантам А( , равным значению соотношения (5):

Л, = 2-<^>.ГКР(5Л V)

Функция, определяющая событие 5,- имеет вид:

(5)

¡'(Б,)

1. на квантах отрезков | Гпи„ (5,5,-)— Ь (5,) -}--,

7*т1и •=!», 1.....Л/ (5,) (6)

О — вне этих отрезков.

Функция, определяющая операцию , Бимеет вид:

1, на квантах отрезков

Гт,„(6\\(Я,- + 2 = 0, 1,.-.., д^(7)

О — вне этих отрезкой.

Как правило, функции получаются недоопределенными, и эту недоопределенность используют при определении минимального представления диаграммы Гапта в памяти компьютера.

Для оптимального распределения ресурсов введем граф связности по времени GCB( =<V, U>, однозначно определяе-хмый диаграммой Ганта, каждой вершине которого взаимнооднозначно соответствует событие (операция), и два события (операции) S¡, Sj связаны по времени, (u¡, uy)eí7, если определяющие их функции неортогональны

f(S,)&f(Sj)^ О f {Si) & / (Sj, Sk) ф 0, / (Sh Sj) & (f (Sj,

и они используют одни и те же ресурсы.

В диссертации показано, что более объективной характеристикой при оптимизации ресурсно-временных параметров является не эластичность проекта, а введенная в работе величина— его ортогональность, которая количественно оценивается как среднее обратное значение производных от могра-фов, определяющих булевы функции событий (операций).

Ортогональностью проекта называется число с (Г), определяемое соотношением (8)

е (Г) = —-- 2 -^-, (8)

k(k-l)u.t+i /._2/,у-г-/у

где k — количество событий (операций); ftj — количество квантов, в которых выполняются как i-e, так и /-е события (операции) одновременно; /, и — длительность í-ro и /-го события (операции) соответственно, при этом если начало и конец г-го и /-го событий (операций) совпадают, то в этом выражении учитывается только одно событие (операция), так как в противном случае с(Г) равно бесконечности.

Эта характеристика позволила найти оптимальную диаграмму Ганта из комбинаторного числа эквивалентных диаграмм Ганта, соответствующих одной сетевой модели. Показано, что количество эквивалентных диаграмма Ганта равно произведению полных временных резервов некритических событий (операций). Уже при средних проектах это число равно Ю®, а = 20-^200, что не позволяет использовать известные методы линейного и динамического целочисленного програм-

мирования. Этот факт определил использование и развитие методов компьютерно-информационной математики.

Раскраской графа С = <.У, и> называется разбиение его носителя V, при котором ни в одном из подмножеств не найдется ни одной пары смежных вершин:

у V,,

Каждому подмножеству V сопоставляется своя краска. Минимальное число таких подмножеств называется хроматическим числом Н(О) графа в.

События (операции) называются соцветными, если они принадлежат одному и тому же подмножеству при раскраске графа связности.

Раскраска вершин графа связности по времени <3С11; решает проблему определения одновременно выполняемых событий (операций). Очевидно, что соцветные вершины (события) могут выполняться одновременно.

Из характеризацнонного анализа известно, что хроматическое число Л (О) графа С равно его квазиплотности К), где р — плотность графа, К — его порядок, равный разности квазиплотности q и плотности р

К = Я-р.

Утверждение 2. Запрещенной фигурой сетевой модели [5[+, 5л~] (диаграммы Ганта) является квазиполный граф положительного .порядка (?(р, /С>0) в графе связности по времени Осв,

С)(р1к>0)<£0са((31\5п-). (9)

Утверждение 2 справедливо. Действительно, в силу вложи-мости квазиполных графов, 0(р, К) ]).

Граф связности по времени Сся, не может содержать цикла, в том числе" и нечетной длины, не входящего в полный

подграф; т. к. противное означало бы, что в сетевой модели (диаграмме Ганта) имеются «возвратные» события, при этом нарушалось бы свойство антисимметричности отношения частичной упорядоченности, что противоречит определению сетевой модели.

Как следствие утверждения 2, получаем утверждение 3.

Утверждение 3. Хроматическое число /1(бсв<) графа связности по времени равно его плотности.

Следовательно, хроматическое число /г(£/свг) равно максимальному числу попарно неортогональных функций соответствующих событий (операций).

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

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

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

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

няя доля графа Кенига сопоставлена работам (событиям, операциям), нижняя — ресурсам. Граф Кенига определяется матрицей инцидентности А ~\[а,j)\nxm.

| 1, если 1-й ресурс обеспечивает /-ю работу,

а,) = I

I 0, в противном случае.

Покрытие столбцов строками в матрице А порождает распределение ресурсов по работам.

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

При покрытии столбцов строками

— столбец уа поглощает столбец /¡г*-+Т{/а)сГ(/[з),

— строка ia поглощает строку £р-<->- Г(1а)^Г(гр ),

где Г(/« ), Г(/з), Г(г'а), Г (г? ) —сечения вершин Л, у'з, h в соответствующем графе Кенига.

Если ресурсы одинаковы, то после сжатия матрицы инцидентности остается хотя бы одно минимальное распределение. Если же ресурсы различны, то сжатие производить не целесообразно, так как при этом можно потерять минимальное распределение.

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

Исследовано распределение ресурсов для связных работ, для чего введен граф полной связности событий (операций) Ойв = <l7. ^cbî w£/свrw£/свг >, бинарное отношение этого графа определяет связность по времени UCB (, по ресурсам UCBr и технологическую связность UCBT. Функционалом качества решения задачи распределения ресурсов является зна-

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

Для раскраски графа в строим двоичную матрицу С, каждой строке которой взаимнооднозначно соответствует простой цикл нечетной длины, столбцу — вершина графа, и элемент матрицы равен 1 тогда и только тогда, когда /-я вершина входит в 1-й цикл, и 0 — в противном случае. По матрице С строим частотную матрицу отношений /Г = СГХС, элементы которой используются для оценки соцветности вершин графа. Каждую пару вершин графа и, и vj можно охарактеризовать значением производной

дО,дР (I, Л = (/■,- 2/„ +/,)//„, (10)

Р — предикат, равный 1, если вершины г^ и Vj входят в простой цикл, 0 — в противном случае; собственные частоты /¡, , равны количеству простых циклов, содержащих вершину

V; соответственно, взаимная частота /ц, равна количеству простых циклов, содержащих вершины г^ и V].

Чем больше значение производной, тем меньше эта связность и тем больше вероятность соцветности вершин ^ и и ¡. На основании этого при раскраске графа в качестве соцвет-ных вершин будем выбирать те пары несмежных вершин графа, которым соответствует минимальное значение выражения, соответствующего обратному значению производной от графа (10), и расстояние между ними равно двум. В случае, когда выражение, обратное (10), принимает минимальное значение для нескольких пар вершин, то в качестве соцветных выбирают ту пару, простые циклы нечетной длины которой в наибольшей степени пересекаются по ребрам графа.

Ресурсно-временная оптимизация при условии неизменной технологии строительства и транспортных операций сведена

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

Для построения гибкой технологии управления строительством в случае чрезвычайных, непредвиденных ситуаций с одновременной ресурсно-временной оптимизацией технологического процесса предложено использовать аппарат многокомпонентной раскраски (мультираскраски) графа полной связности.

Мультираскраской графа 0 = <У, С/> называется разбиение его носителя V: [} ¡У1 = V,-У,ь =0, при котором

смежным вершинам V*, сопоставлены векторы,

отличающиеся друг от друга в каждом разряде.

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

По крайней мере, непредвиденная ситуация «порождает» хотя бы одно ребро {5<( в графе ; при этом, если события 5,- , были несоцветнымп до непредвиденной ситуации, то возникшая ситуация не влияет на управление технологическим процессом, если же события 5г , были соцвет-ными до аварии, то управление технологическим процессом переключается и производится по компоненте, в которой события и несоиветны.

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

После разработки гибкого управления технологическим процессом строительного производства необходимо произве-

сти моделирование наиболее сложных производственных ситуаций.

Для проведения такого моделирования в диссертации предложена модификация сетей Петри путем учета времени с помощью идентификации соответствующего временного кванта Д, . ,

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

СЕТЬ— построение сетевой модели, вычисление критического пути и минимального времени выполнения строительного проекта;

РЕЗЕРВ — вычисление полных временных резервов некритических событий (операций);

Г-ДИАГРАММА — построение диаграммы Ганта, вычисление глубины временного квантования и длительности временного кванта;

ФУНКЦИЯ — задание событий (операций) в виде функций в булевом пространстве;

Т-СВЯЗНОСТЬ — определение бинарного отношения связности событий (операций) по реализуемой технологии;

/г-СВЯЗНОСТЬ — определение бинарного отношения связности событий (операций) по времени и ресурсам;

ПЛОТНОСТЬ — алгоритм вычисления плотности графа связности;

Г-ОПТИМИЗАЦИЯ— оптимизация ресурсов за счет временных резервов событий;

НСВ-РАСПРЕДЕЛЕНИЕ — распределение ресурсов для несвязных работ на основе порождения внешнеустойчивых множеств;

СВ-РАСПРЕДЕЛЕНИЕ — распределение ресурсов для связных работ путем его сведения к задаче раскраски вершин графа полной связности;

РАСКРАСКА — алгоритм, оптимальной раскраски вершин графа, основанный на использовании аппарата дифференцирования графов по предикату;

РЕСУРС — реберно-временная оптимизация, основанная на сужении сигнатуры графа полной связности;

АН-СИТУАЦИЯ — оптимизация гибкой технологии управления строительным производством при аварийных, непредвиденных ситуациях; оптимизация основана на мультираскрас-ке графа полной связности;

МОДЕЛЬ — моделирование сложных фрагментов гибкой технологии управления строительным производством на основе предложенной модификации сетей Петри;

ДИСПЕТЧЕР — управляющий модуль, определяющий последовательность возбуждения операционных (предыдущих) модулей.

Разработанный программный инструментарий представляет собой САПР гибких технологий управления строительным производством, имеет большую производительность, позволяет проектировать гибкие технологии управления строительством, включающие до ]04 событий (операций) с реактивностью обработки одного события 1—3 с.

Программный инструментарий успешно внедрен в практику промышленного проектирования на ряде предприятий, в том числе, в АО «Владикавказстрой», АОЗТ «Кавказэлек-тронстрой», АО «Кавказтрансстрой» с экономическим эффектом свыше 3 млрд. руб. в год в ценах 1995 г., о чем имеются соответствующие акты о внедрении.

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

Практические применения разработанного программного инструментария автоматизированного проектирования гибких технологий управления строительством показали уменьшение

2 ¡7

времени строительства на 10—20% и на 20—30% обеспечивающих ресурсов.

Теоретические результаты использованы в учебном процессе Северо-Кавказского государственного технологического университета и Московском государственном горном университете.

ЗАКЛЮЧЕНИЕ

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

Основные теоретические и практические результаты работы.

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

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

3. Определен граф связности по времени для оптимизации ресурсно-временных характеристик сетевой модели проекта. Оптимизация ресурсов сведена к задаче раскраски вершин графа связности по времени. Решена задача характеризации сетевых моделей — показано, что запрещенной фигурой сетевых моделей является квазиполный граф положительного порядка в графе связности по времени.

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

5. Показано, чго более объективной и эффективной характеристикой. чем эластичность проекта, является его ортогональность, которая количественно оценивается как среднее обратное значение производных от мографов, определяющих булевы функции событий (операций); эта характеристика позволяет найти оптимальную, в смысле ресурсно-временных параметров, диаграмму Ганта из множества эквивалентных диаграмм Ганта, комбинаторное количество которых равно произведению полных временных резервов некритических событий (операций).

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

7. Исследовано оптимальное распределение ресурсов при альтернативном обеспечении работ ресурсами как для несвязных, так и связных работ. Предложен эффективный алгоритм оптимального распределения для несвязных работ, основанный на порождении внсшнсустойчпвых множеств графа Ке-нига.

8. Исследовано распределение ресурсов для связных работ, для чего введен граф полно]! связности событий (операций), сигнатура которого определяет связность по времени, по ресурсам и технологической связности строительного производства. Задача оптимального распределения сведена к раскраске вершин графа полной связности, минимальная раскраска которого определяется его квазиплотностью. В силу этого обстоятельства, разработан эффективный алгоритм раскраски вершин, основанный на учете частот вхождения

2* 19

вершин и их пар в простые циклы нечетной длины этого графа.

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

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

11. Для успешного внедрения теоретических результатов в промышленность разработанное математическое обеспечение доведено до программной реализации в виде соответствующего инструментария на современных ПЭВМ с помощью языка С+ + , позволившего автоматизированно проектировать гибкую технологию управления строительным производством, включающим до 104 событий с реактивностью обработки одного события 1-4-3 с. Кроме разработанного программного обеспечения, в обратную связь инструментария включен операционный модуль МОДЕЛЬ, позволивший на основе предложенной в работе модификации сетей Петри, по-

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

12. Научные результаты, полученные в диссертации, внедрены в учебный процесс при чтении дисциплин «Управление строительным производством», «Разработка САПР строитель-пых технологии» в Северо-Кавказском государственном технологическом университете и при чтении дисциплины «Методы оптимизации» в Московском государственном горном \пп-верситсте. Разработанный программный инструментарий успешно внедрен в практику промышленных предприятий, в том числе, в АО «Владикавказегрой». АОЗТ «Кавказэлектрон-строй», АО «Кавказтрансстрой». В объединениях «Кавказ-электронстрой» и «Кавказтрансстрой» экономический эффект от внедрения разработанного программного инструментария составил соответственно 2 и 1 млрд. рублей в год в ценах ¡995 года, о чем имеются соответствующие акты о внедрении.

Содержание диссертации опубликовано в работах:

в виде статей:

1. Хадонов 3. М. Алгоритм расчета сетевого графика поточного строительства при заданных шггепспвиостях потоков. -— В сб.: Труды СКГМИ, вып. XXIX/Строительство. -Орджоникидзяе, 1968.

2. Хадонов 3. М., Остроух В. А., Борисов А. В. Алгоритм формирования потоков. — На стройках России, № 4, Орджоникидзе, 1969.

3. Хадонов 3. М., Онуфриев J1. Т., Пейкршвили И. М. Комплекс машинных программ в автоматизированной системе «Автоспутник». — В сб.: Труды МИСИ № 1 (71), Организация и экономика строительства. М.. МИСИ, 1969.

4. Хадонов 3. М., Павлов С. М. Алгоритм планирования непрерывных строительных потоков на основе сетевых графиков.— В сб.: Труды МИСИ № 1 (71), «Организация и экономика строительства». М., МИСИ, 1969.

5. Хадонов 3. М., Архипова А. А., Мачавариани 3. П. Поточное возведение комплексов очистных сооружений с приме-

нением метода сетевого планирования и управления.—На стройках Подмосковья, № 3. М., Стройиздат, 1970.

6. Хадонов 3. М., Борисов А. В., Остроух В. А. ЭВМ формирует потоки в сетевых графиках. — В сб.: Организация управления строительным производством с применением вычислительной техники, серия 9, вып. 2. М., Гипротис, 1970.

7. Хадонов 3. М., Архипова А. А., Мачавариани 3. П.

Строительство насосной станции по сетевому графику. — На стройках Подмосковья, № 4. М., Стройиздат, 1971.

8. Павлов С. М., Лебедев В. А., Хадонов 3. М. Поточное строительство с использованием системы сетевого планирования и управления. — Промышленное строительство, № 10, М., 1971.

9. Хадонов 3. М. Организация и управление поточным строительством на основе использования методов СПУ и ЭВМ.— В сб.: Труды СКГМИ. — Орджоникидзе, 1972.

10. Павлов С. М., Хадонов 3. М. Основные задачи сочетания поточного строительства с системой СПУ. — В сб.: Труды МИСИ/Организация НИР в строительстве. М., 1972.

11. Хадонов 3. М. Оптимизация сетевой модели строительства при поточном производстве работ. — В сб.: Труды СКГМИ, вып. XXXIII. —Орджоникидзе, 1973.

12. Хадонов 3. М., Кучкин Г. А., Митюшин В. С. Поточная организация строительства на основе сетевых графиков в тресте «Севосетинпромстрой». — В сб.: Организация, механизация и технология промышленного строительства. М., Мин-промстрой СССР, 1974.

13. Хадонов 3. М., Лазаренко Ю. В., Касаев Г. С. Проектирование оптимальной организации строительно-монтажного конвейера. — В сб.: Совершенствование организации управления строительным производством. — Орджоникидзе, СКГМИ, 1979.

14. Хадонов 3. М., Банхаев И. А., Куштов Я. Ю. Разработка моделей и алгоритмов для оперативного управления строительством с учетом изменяющихся условий. — В сб.: Совер-

шенствование организации управления строительным производством. — Орджоникидзе, СКГМИ, 1979.

15. Хадонов 3. М. Распределение ресурсов при промышленном строительстве.— В сб.: Труды СКГМИ в честь 50-летия СКГМИ. — Орджоникидзе, 1981.

16. Хадонов 3. М., Касаев Г. С., Крошко С. В. Об одной задаче формирования потоков при рассредоточенном строительстве.— В сб.: Труды СКГМИ/Строительство. — Орджоникидзе, 1982.

17. Хадонов 3. М., Тибилов М. А. Организация транспортирования бетонной смеси на Орджоникидзевском заводе КПД. — В сб.: Труды СКГМИ/Строительство. — Орджоникидзе, 1988.

18. Хадонов 3. М., Касаев Г. С., Дзеранов Т. В. Пути совершенствования технологии строительного производства в Северной Осетии. — В сб.: Труды СКГМИ/Строительство.— Орджоникидзе, 1988.

19. Хадонов 3. М., Тускаева 3. Р. Организационно-технологическое проектирование в системе инженерной подготовки строительного производства. — В сб.: Труды СКГМИ/Строительство. -- Владикавказ, 1992.

20. Хадонов 3. М. Оптимальное распределение ресурсов для несвязных работ.— В сб.: Труды СКГТУ, вып. 3.— Владикавказ, Терек,1997.

21. Хадонов 3. М., Лащенков А. В. Анализ простых временных сетей Петри приведением к обыкновенным.— В сб.: Труды СКГТУ, вып. 3.— Владикавказ, Терек, 1997.

22. Хадонов 3. М. Оптимальное распределение ресурсов

для связных работ. -В сб.: Труды СКГТУ, вып. 2. — Владикавказ, Терек, 1996.

23. Хадонов 3. М. Планирование строительных проектов.— В сб.: Информатизация производства. — Владикавказ, Терек, 1996.

24. Хадонов 3. М. Минимизация ресурсов. —В сб.: Информатизация производства. — Владикавказ, Терек, 1996.

25. Хадонов 3. М. Оптимизация операций в условиях аварийных ситуаций. — В сб.: Труды СКГТУ, вып. 2. — Владикавказ, Терек, 1996.

26. Хадонов 3. М. Теоретико-графовые модели информационных технологий при распределении ресурсов/Информационные технологии, № 10. М., Машиностроение, 1997.

27. Хадонов 3. М. Ресурсно-временная оптимизация в САПР гибких технологий управления. — В сб.: Информационная математика в информациологии. ПА, М.— Ижевск, 1997. и в виде монографий:

28. Павлов С. М., Хадонов 3. М. Проектирование организации строительства и производства строительно-монтажных работ. — М., Стройиздат, 1971, 256 с.

29. Хадонов 3. М. Управление строительным производством. — Владикавказ, СКГМИ, 1991, 123 с.

30. Хадонов 3. М. Теория автоматизированного проектирования гибких технологий управления строительным производством. Владикавказ, Терек, 1997, 112 с.

Степень участия диссертанта в публикациях, написанных в соавторстве в:

[2] предложена операционная часть алгоритма формирования потоков;

[3] разработана операционная часть автоматизированной системы «Автоспутник»;

[4] проведена формализация планирования строительных потоков на основе сетевых графиков;

[5] поточное возведение комплексов сведено к методу сетевого планирования и управления;

[6] разработана структура программы, порождающей потоки в сетевых графиках;

[7] разработан сетевой график строительства насосной станции;

[8] разработана сетевая модель поточного строительства;