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

г*-.

г

о На правах рукописи

см

СТРОКИНЛ Юлия Германовна

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

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

управления

л в т о р е ф к р л г

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

уфл 1997

Работа выполнена на кафедре промышленной электроники Уфимского государственного авиационного технического университета. Научный руководитель: доктор технических наук,

профессор Ефанов В.Н. Официальные оппоненты: доктор технических наук, профессор Миронов В.В. кандидат технических наук, Перельман В.И.

Ведущее предприятие: ОКБ «Гидромеханика»

Защита диссертации состоится ЛЫЪХ 1997г. в " "

часов на заседании диссертационного совета К - 063.17.03 Уфимского государственного аскационного технического университета по адресу: 450000, Уфа-центр, ул. К.Маркса 12.

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

Автореферат разослан " ^ "

1997г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Ефанов В.Н.

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

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

Методическую основу перечисленных задач составляет теория расписаний, которая использует модельный подход к анализу реальных процессов. Исследования в данной области математического программирования ведутся достаточно давно, при этом разнообразие используемых моделей и степень их универсальности постоянно увеличиваются. Важное место в разработке теории И методов решения задач составления расписаний занимают работы Канторовича Л.В., Конвея PJT-, Парамонова ФЛ, Португала В.М., Таиаева B.C. и многих других исследователей. Однако целый круг актуальных вопросов по-прежнему остается открытым, поскольку совершенствование методов теории расписаний проходило, ¿ основном, без кардинальных изменений анализируемых моделей.

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

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

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

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

пятая решений при составлении расписаний функционирования производственных систем.

Задачи исследования. Для достижения поставленной цели в работе сформулированы н решены следующие задачи:

- предложена математическая модель гетерогенной задачи составления расписаний;

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

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

- исследованы методы повышения разрабатываемых расписаний с учетом неопределенных факторов производственной обстановки;

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

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

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

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

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

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

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

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

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

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

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

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

Тематика работы связана с планами госбюджетных научно-исследовательских работ № АП-ПЭ-35-95-03 и № АП-ПЭ-35-96-03 по разработке архитектуры алгоритмического и программного обеспечения многопроцессорных и управляющих систем с элементами искусственного интеллекта.

На защиту выносятся:

- математическая модель гетерогенной задачи составления расписаний;

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

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

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

- интеллектуальная подсистема поддержки принятия решений для диспетчера промышленного предприятия.

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на : международной научно-методической конференции "Проблемы качества высшего образования" (Уфа, 1994 г.); региональной конференции "Реализация многоступенчатой подготовки специалистов в вузах Башкортостана" (Уфа, 1994 г.); всероссийском совещании "Базы данных и информационные технологии в системах непрерывного образования" (Уфа, 1995 г.).

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

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, библиографии и приложения. Работа содержит страниц машинописного текста и 121 наименование библиографических источников.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе проведен критический анализ современного состояния теории расписаний, с учетом которого сформулированы основные задачи исследования.

Термин "теория расписаний" появился в начале 60-х годов. Он включа-* и в себя круг вопросов, связанных с построением календарных, планов (расписаний) и использует модельный подход к анализу реальных процессов. В рамках данной теории вырабатываются рекомендации по улучшению качества планирования: создаются разнообразные методы, помогающие принять решения в рассматриваемых ситуациях.

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

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

- многофункциональные приборы, позволяющие обслуживать' несколько требований;

- комплексные требования, которые могут одновременно обслуживаться несколькими приборами;

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

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

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

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

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

На основе проведенного анализа этих проблем были сформулированы цели и задачи данного исследования.

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

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

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

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

(и,а,\' (1)

где и = N х М - декартово произведение множества N ={1, 2,..., п} требований, поступающих на обслуживание и М = {1, 2,... т} - множества обслуживающих приборов, Пр - множество предикатов, заданных на множестве и.

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

С целью.описания алгебраической структуры в работе введены следующие понятия.

Субъектом расписания называется элемент % е и, т.е. пара вида (N0; Мо), где N0 Мо е М.

На множестве субъектов расписания ио е и вводится отображение Р(0: это отображение ставит в соответствие каждому субъекту расписания Ное и

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

Отображение Po(t) : Uo->To называется элементом расписания, а отображение Pw: w->Tw, wcU - фрагментом расписания.

Множество частичных операций Fw = {f i, f2, ..., f,}, позволяющих сформировать из множества фрагментов расписаний {wb w2, ...,wr } множество U

U = Üwk, (2)

к - ]

называется правилом составления расписания.

Помимо отображений Pw(t) и правил Fw в состав алгебраической структуры входят формулы прикладного характера, определенные па множествах wk. Важное место среди указанных формул занимает совокупность оценочных функций s = {е\, е2, ..., ¿к}, устанавливающая степень соответствия данного фрагмента расписания предъявляемым требованиям.

В свою очередь, логическая структура модели объединяет:

- совокупность h-арных предикатов, которые по определенным правилам сопоставляются с h-арным отображением Pw(t);

- элементарные (атомарные) формулы пида;М0 eN, М0 еМ, uo eU, ТсеТ;

- логические знаки "и" - &; "или" - V, импликация -» ("если, то") и т.д.;

- символ следования;

- предикатные знаки: ее, =;

- кванторы э, V;

- предикаторные скобки {};

- паросочетания вида: P0(t): Uo -+Т0..

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

В многостадийных системах процесс обслуживания любого требования i е N включает h(i) последовательный стадий. При этом каждому требованию i и каждой стадии q, 1 sq^h(i) его обслуживания сопоставляется некоторое множество приборов М^с {1, 2,... М}. Требование К''я на стадии q может быть обслужено любым прибором L е M'q, в этом случае требование i можно представить как h(i) элементарных требований. Таким образом сложный процесс обслуживания описывается как ряд более простых последовательных процессов в одностадийных системах. Тогда на стадии q необходимо обслуживать

и

Nq = £ Л^ требований.

Выражение для предикатов модели (1), применительно к стадии ц, усложняется из-за необходимости учета предыстории обслуживания на предыдущих стадиях

Я, -{лфг..„...,АГ,;Л/,_„...,Л/, }. (3)

Объединение частных видов предикатов для отдельных стадий дает следующий маршрут составления расписания для многостадийной системы

улгз^Э^ХВДОМ)-* Уладм.^адэдохл^А«, Л/г)-»... ->н.....лг2,л„ Мн,уи... М„М,) ^(^.....Л^Л',; мЫ1У.....

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

{ЛГ,/>•(',*).ЛГ }, ^ (5)

где множества Лг* и М' определяются в виде

а отображение К) формируется с учетом распределения ресурсов на каждой стадии

¿=1 м ¿-I '

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

Учет специфики гетерогенных задач составления расписаний в рамках введенной модели потребовало использование обобщенных требований и приборов. Под обобщенным требованием понимается множество требований, обслуживающихся многофункциональным прибором. Требование такого вида имеет сложную структуру и зависит от всех входящих в него элементарных требований Ио^к, N^+1, ...) . Аналогично, множество приборов, обслуживающих комплексное требование, будем называть обобщенным прибором. Его функционирование зависит от входящих 6 него так называемых, элементарных приборов Мо(Мь Мк+1,...).

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

Введенное понятие позволило получить компактную форму записи универсальной модели гетерогенной задачи в следующем виде

(Ыфхм^мадрсдейм^)}), (7)

где Ъ - множество параметров задачи.

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

1. Декомпозиция множества требований по выбранному Х(1) признаку, в соответствии с которым данное множество разбивается на конечное число классов эквивалентности.

здесь Х(Х\1)) - множество требований (элемент исходного фактор-множества требований), обладающих признаком Х(|) К-го вида,

отображение подмножества требований на подмножество приборов, -подмножество приборов, обслуживающих требования Л^Л^1') , причем каждому //(Л}1') будет соответствовать свое подмножество на исходном множестве приборов и А^Л'^) £ М.

Анализ показал, что при = исходная задача распадается па

совокупность несвязанных подзадач распределения требований Л^(ЛГ^) между приборами множества М. Если Р)то для устранения конфликта при независимом составлении фрагментов расписания предлагается использовать два подхода.

Первый предусматривает принудительное распределение общих частей подмножеств приборов Л/(Л^1)), например, за счет выбора стратегии обслуживания требований Ы(Хкт) на фиксированных временных интервалах, либо за счет назначения приоритетов по каждому виду признака.

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

2. Декомпозиция множества приборов по признаку Х(2). Аналогично предыдущему случаю это приводит к разбиению множества приборов на конечное число классов эквивалентности

(ЛГ(*«>)* Л/(Л?>),{ЛЧЛ?'), Р(1,Х12)), ЩХ?)}), (9)

здесь - множество приборов (элемент исходного фактор множества

приборов), обладающих признаком X® К-го вида, К = - подмноже-

ство требований, которые нуждаются в обслуживании приборов, обладающих Х(2) признаком, причем N(X(^>)cN .Если р|Лг(Д^3>) = 0, то исходная задача

ХЦ)

распадается на совокупность несвязанных подзадач распределения приборов между требованиями N. Если Р^СХ^') * 0, то для устранения КОН-

ОД

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

3. Совместная декомпозиция множеств приборов и требований - декомпозиция по признаку

В этом случае выбранное подмножество приборов М,(Хт) закрепляется за определенным подмножеством требований ЛГ,(Х<3)) и обслуживание осуществляется в рамках установленного соответствия

где Р({,Х(3)) - оператор, устанавливающий отображение между требованиями и приборами данных подмножеств. Тогда Л^Х^с N и ("^(Х'3')* 0 , аналогично «Д'й)с А/ и =

I

4. Согласованная декомпозиция множества приборов и требований. В этом случае множества N и М декомпозируются по какому-то общему признаку Х(4).

(лг(л4>).ад4>),{лг(л1,>),«г,^4'),л/(л14>)} '(П)

где ЛГ(Л^4)) с N, и М(Х^) сД/.

Если |и (или)["| ЛД^4')* 0. то для устранения конфликтов "(*) »(*> используется методика, описанная в л.1, п.2. Учитывая чрезвычайную сложность возникающих при этом ситуаций, подобный метод декомпозиции целесообразно использовать только в том случае, когда существует общий признак, позволяющий разбить множества требований и приборов на непересекающиеся подмножества.

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

(ЛГ.Л/',{Л",Р(Г,),ЛГ }), (12)

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

(Лг;(г,)» мл2„),{м,{2кг,Р(т„1к,я'), л/,0г,у». (13)

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

-пользованием метода рандомизации, нечетких множеств и интервальных вычислений.

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

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

Реализация первой части этой процедуры осуществлялась с учетом следующих обстоятельств:

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

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

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

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

£ = (е1,£1,...е1 ). (14)

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

е^ =4с,-МсУЛО-,Р;М;а,т), ' (15)

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

вания к типа, при осуществлении декомпозиции по требованиям ( г = 1, Ьк );

и

номер многофункционального прибора к типа, при осуществлении декомпозиции по приборам ( / = 1,й, ); р е Р; я е 0; <3 и Р - множество номеров строк и столбцов соответствующей подматрицы, N - множество требований;« - весовой коэффициент, определенный в зависимости от признака декомпозиции; т

- номер признака декомпозиции.

Необходимо отметить, что при составлении оптимального варианта из фрагментов могут возникнуть следующие ситуации:

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

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

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

Общее выражение для показателей композиции будет иметь енд

трт^ДсХадеда). (16)

Эти функции зависят от тех же величин, что и совокупность локальных критериев в (15). Основное ее отличие заключается, как рассматривалось выше, в том, что обслуживанию подлежат только те требования, которые не были удовлетворены в рамках декомпозированной задачи, а в качестве приборов используются только те, которые ранее не были задействованы.

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

07)

тк(с)

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

ритма формирования оптимального расписания, представленная на рис.1. Отдельные элементы этой схемы реализуют следующие функции:

- блок 1 осуществляет ввод и предварительный анализ исходных данных (допустимых фрагментов расписания или вариантов допустимых расписаний);

- блок 2 формирует локальные или глобальные критерии в зависимости от этапа решения задачи составления расписаний; '

№0.1. Алгоритм формирования оптимального расписания

- блоки 3-5 проверяют выполнение перечисленных свойств критериев;

- блок 6 осуществляет поиск вариантов, оптимальных по безусловному критерию предпочтения, с использованием метода рабочих характеристик;

- блок 7 проверяет возможность перехода к условной оптимизации, если такая возможность отсутствует, то процедура поиска завершается;

- блок 8 формирует интегрированный критерий с учетом субъективного мнения ЛПР;

- блок 9 осуществляет окончательный выбор оптимального варианта на основе имеющейся информации об условном критерии предпочтения;

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

Важное место в работе занимают вопросы исследования задачи составления гетерогенных расписаний в условиях неопределенности. ^Специфика этой задачи состоит в том, что нельзя, как правило, найти единственный оптимальный вариант, а можно выделить лишь хорошие в разных отношениях расписания, поскольку сопоставимыми между собой оказываются только те расписания, которые оценены при одном и том же сочетании исходной информации: Для сокращения высокой размерности, обусловленной необходимостью вариации исходных данных и использованием различных видов декомпозиции, предлагается принцип "дискретизации" допустимых решений, предусматривающий разбиение исходной совокупности построенных расписаний на классы эквивалентности по значениям оценочных функций. Анализ элементов полученных фактор-множеств проводился с использованием вероятностных, нечетких и интервальных шкал.

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

Для адекватного представления процедуры решения гетерогенной задачи составления расписаний структура подсистемы рассматривается как бпоч-но-иерархическая. В ее составе выделены следующие уровни (рис.2): уровень формирования фрагментов расписаний (I); уровень формирования вариантов расписаний (II); уровень типовых задач составления расписаний (III); уровень гетерогенных задач (IV).

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

Рис. 2. Структура алгоритмического обеспечения интеллектуальной подсистемы поддержки принятия решений гетерогенной задачи

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

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

Жесткие связи отражают специфику гетерогенных задач и образуют структуру неизменяемой части программной системы - ядра системы.

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

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

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

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

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

Анализ оценочных функций выявил в качестве наиболее важных критериев оптимальности показатели равномерности загрузки оборудования и минимизации перемещений партий деталей между рабочими местами (с ранговыми оценками, соответственно, 0.5 и 0.2). В результате был получен оптимальный по обобщенному критерию вариант плана, загрузки цеха. Это позволило повысить равномерность загрузки, оборудования, минимизировать число его переналадок при изготовлении различных групп деталей: и. сократить объем перемещений партий, деталей.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

В процессе работы над диссертацией были получены следующие результаты:

- сформулирована математическая модель гетерогенной задачи составления расписаний;

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

- предложен способ декомпозиции и оптимальной композиции задачи состав-

- разработан метод формирования.расписания в условиях неопределенности;

- предложена интеллектуальная подсистема поддержки принятия решения для диспетчера промышленного предприятия.

Программная реализация подтвердила высокую эффективность методики составления гетерогенных расписаний, позволяющей сократить время составления расписаний функционирования сложных производственных систем, а также учебных занятий на 20-30%. Применение указанной методики при составлении гтпяия работы ш»уаи1гч<>гкг1гп цеха, позволило повысить, на. 10% равномерность загрузки оборудования, минимизировать число переналадок оборудования при изготовлении; различных групп деталей и сократить на 15% объем перемещений партий деталей.

СПИСОК ЛИТЕРАТУРЫ

1. Стариков В.Н., Осипова.Г.В,, Строкина Ю.Г. Информационные базы данных в задаче составления расписания занятий в вузе // Реализация многоступенчатой подготовки, специалистов в вузах Башкортостана. Тезисы докладов. -УГАТУ, Уфа, 1994.-с.44 - 45.

2. Стариков В Л., Осипова ГЛ., Строкина Ю.Г. АРМ диспетчера бюро расписаний// Проблемы качества высшего образования: Тезисы докладов. - УГАТУ: Уфа, 1994. - с. 106-107.

3. Стариков В.Н., Тархов C.B., Строкина Ю.Г. Программный комплекс поддержки планирования учебного процесса в вузе/ Свидетельство о регистрации программы для ЭВМ. Per. № 50950000007 от 15 .02.1995.

4. Стариков В.Н., Строкина Ю.Г. Разработка и введение баз данных в программном комплексе поддержки планирования учебного процесса в ву-зе//Проблемы создания национальной академической системы баз данных и баз знаний. Часть 2. - УГАТУ: Уфа, 1995. - с. 49 - 50.

5. Строкина Ю.Г. Модель эффективной реберной раскраски к задаче составления расписаний учебных занятий // Управление в сложных системах: Межвузовский научный сборник. - УГАТУ: Уфа, 1995. - с. 113 -116.

6. Ефанов В.Н., Строкина Ю.Г. Интеллектуальная подсистема поддержки принятия решений диспетчера промышленного предприятия // Депонированная научная работа в ВИНИТИ Ш73-В97. - Уфа: УГАТУ 1996. - 15 с.

7. Ефанов BJH., Строкина Ю.Г. К проблеме построения гетерогенных расписаний для производственных систем // Депонированная научная работа в ВИНИТИ №172-В98. - Уфа УГАТУ. 1996. - 14 с.