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

САШТ-ПЕТЕРБУИХЛШИ ИНСТИТУТ АВМЦЖШОГО ПИШОРССТРОШЛ

На npasas рукогоса

ЕПГКЕЗ Д'*!ттрй1 Алзксэевет

S29.73.C51.23

РЕШЕНА ЗАДШ СОСТАВЛЕНИЯ РАСПИСАНИЯ JWI ПSK5S С"СТЕ! НА ОСНОВЕ гзажшшюл ЫОДЕШ

Сгг/шгз-тыюсть. C5.I3.II -"Езтематэтвскоэ и прогрг:"!на-э сбэспз^энпэ вячг.гип-ТОЛЫПП rranioi, KCMJZOKCOB,, ración и сэтогт

Автореферат

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

Санкт-ПотерОург 1992

Работа выполнена в Саикт-Петербургском институте авиационного приборостроения

Научный руководитель -

Доктор технических наук, профессор Е.И. Перовская

, О&щиалышо оппоненты:

Доктор технических наук, профессор A.A. Пэрвозванскнй

Кандидат технических наук Л.Л.Логинова

Ведущее предприятие -

Санкт-Паторбургский институт информатики и автоматизации АН России

Защита диссертации состоится ■ЯГ- {■¿¿-ОУ-^-Ъ.992 г.

в _ часов на заседании специализированного совета

К 063.21.03 Санкт-Петербургского института авиационного приборостроения то -адресу: 190000, Санкт-Петербург, ул. Герцена 67.

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

Автореферат разослан " " ^¿^¿¿-JL-_1992 г.

Ученый секретарь специализированного совета

Фильчаков В.В.

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

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

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

Пэль работы.Конечной цэлыэ исследований является разработав эффективных алгоритмов- решения задачи составления расписания для дискретных технологических систем (ДТС), функционирупцих в условиях изменения целей, ситуаций а критериев, и создание прикладного программного обеспечения, п Езде комплекса программ составления расписаний для ГДТС.

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

1. Разработка расширенной модели ГДГС.

2. Разработка на баге метода двойного ранжирования (ЫДР) 8$фективного алгоритма решения задачи составления расписания (ЗСР) путем выделения инвариантной (не зависящей от основных и оптимизирующих требований) и настраиваемой частей метода.

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

4. Разработка программного обеспечения, реализующего возможности решения задачи составления расписания для ГДГС. .

5. Планирование и организация машинных экспериментов, позволянцих оценить эф!ктишость теоретических разработок.

Мэтодика исследования базируется на теории расписаний, теории графов и теории множеств.

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

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

2. Разработан метод получения оценок составимости для модели ГДТС, примененный дополнительно и для получения оценок наличия решения в поддеревьях дерева поиска решения.

3. Предложена оптимизация процесса составления расписания по узким местам - совладение основного требования (полное удовлетворение целевого задания).

4. Доказана оптимальность МДР по отношению к критерию штрафа за отступление от требований пользователя.

?Практическая ценность результатов .диссертационной работы заключается в следующем :

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

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

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

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

Реализация___На основании научных

результатов, полученных в диссертационной работе, проводимой в рамках. НИР : "Разработка математического п программного обеспечения систе>.щ оперативного планирования и упрзвлония в интегрированном производственном комплексе" (ВИПГГ, г.Санкт-петербург), "Комплекс задач календарного планирования работа участка термопластавтоматов" (НИИ '.-"К г.Новгород), "Разработка типовой подсистема автоматизации производства промниленно-учобного назначения и. програтято-гатодпческого обеспечения учебных дисциплин по автоматизации производства" (НИИ ВО, г. Москва; БТУ, г. Будапешт), создан кстдлзкс программ оперативного планирования для использования при оперативном планировании гибких дискретных технологических систем.

Ресошю указанных задач позволило получать Еначлтольный 8конс»2чзскеЯ аффект (около 50 тнс. руб.) за счет повышения производительности труда, огоратиппоста и адекватности принятия управленческих репепий.Впедрзние результатов дис^эртацсонной работа с указанием экономического аффзкта по ксгдсП пз разработок подтвервдавтся соотвэтствукцвя! акта1"!.

Апробация работы. Основные положения п результата работа докладывались на Всесоюзной научно-технической конференции "Автоматизация исследования, проектирования и испытаний слоеных технических систем" (Калуга, 1989), на Всесоюзном научно-техническом совещании "Программяоо обеспечение новой информационной технологии" (Калинка, 1989), на Зональной конференции "Автоматизация технологического проектирования" (Пенза, 1989), на Четвертой Дальневосточной научно-технической конференции "САПР и надежность автоматизированного производства в машиностроении" (Владивосток, 1930).

Публикации. Основное содержание работы отражено в семи печатных работах, в том числе двух регистрациях в ГосФАП, общим обьеыом 2,1 печатных листов.

Структура и объем работы. Диссертационная работа изложена на 139 страницах, содержит 1страницу иллюстрации и таблиц, 8 рисунков. Работа состоит из введения, четырех глав, заключения, списка использованной литературы из 90 наименований.

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

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

В первой главе на основе обзора литературных источников по теме диссертации рассмотрены модели и методы, предлагаемые для решения задачи составления расписания (ЗСР), дан их критический обзор с позиции применимости в условиях гибких систем.

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

При анализе моделей, предлагаемых в рамках ЗСР, показано, что, с одной стороны, большинство моделей в значительной степени используют конкретные особенности реальных систем, с другой - не обеспечивают необходимую степень адекватности представления при изменении параметров систем. Из-за этого простое перенесение имеющихся моделей в область гибких систем невозможно. Поэтому математическая модель ГДТС для задачи составления расписания должна быть расширена и представлена в

виде математического описания следующих характеристик : < Б, с, ТП, 0, о, Ф, р, т >, где

Б - множество объектов обработай;

с - множество целевых заданий допустимых для ГДТС;

ТП- множество технологических процессов определенных в ГДТС;

0 - множество технологических операций, реализуемых в ГДТС;

с - множество ресурсов ГДТС разных типов;

Ф - множество ограничений налокенных на среду функционирования ГДТС;

Р - множество критериев для оценки качества работы ГДТС, рассматриваемых в зависимости от производственной ситуации;

1 - период функционирования.

Далее показано, что методы решения задачи составления расписания сильно привязаны к имеющимся моделяд п естественным образом наследуют жесткую ориентацию на уникальные особенности конкретных систем. За счет максимального конкретизирования во многих работах удается значительно снизить исходную размерность задачи, что обуславливает широту . спектра применяемого метематического аппарата. Гибкие се систекы, наоборот, характеризуются невозможностью фиксированного выделения такого рода особенностей, поэтому приходится работать с довольно большим пространством поиска решения. ЗСР з тепой постановке является нр-полюа, что приводит к необходимости отказаться от точного решения, которое, в общем случве, можно найтп только полным перебором. Указанное, обстоятельство делает невозможным применение точной оптимизации, сужая область возможного математического аппарата до класса обобщенных эвристических методов. В данных условиях были выделены два подхода, позволяющих достичь решения задачи составления- расписания в условиях ГДТС. Эти методы обладают вагшзел свойством, необходимым для работы в изменяющихся условиях - инвариантностью к параметрам ГДТС.

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

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

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

Таким образом, задача составления расписания для ГДГС (представленной в виде расширенной обобщенной модели) выглядит следующим образом: Для ГДТС { л, с, ТЛ, о , с, Ф, ФП, Рщ , Т11Д} необходимо найти расписание работы ресурсов (О), реализующее целевое задание (С), в соответствии с технологией (ТП), удовлетворив ограничениям (Ф) н проведя пошаговую оптимизацию функции штрафа ?ш в соответствии с предложенным набором функций предпочтения (ФП).

Во второй главе представлено формализованное описание модели ГДТС и ЦДР, доказана оптимальность ЫДР относительно минимизации критерия штрафа за отступление от требований пользователя. Дано обсувдение принципов программной реализации . МДР на основе выделения инвариантной и настраиваемой части.

Как отмечалось выше, ГДТС может быть представлена восьмеркой :

< й, о, ТП, о, о, Ф, ?ш, т >.

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

Под объектами образующими множество объектов обработки

п Е { й1 }1=7ТП • будем понимать объекты, для которых получение заданных свойств в результате взаимодействия единиц оборудования системы, является целью функционирования всей системы. Причем в качестве отдельного объекта, при необходимости, может выступать и некоторое множество неразличимых по отношению к данному техпроцессу объектов - партия.

Отсюда, целевое задание (с) представляет собой описание связи обрабатываемого объекта и технологии обработки (в виде упорядоченного набора допустимых операций г техпроцессов): с = < (1, тп >, где

а € п, тп € ТП.

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

Хс^ < ГАр Е^, тп1, Он^ 0к1, Тн1, Тк1, Р1>, где

И - имя партии;

Ей - количество входящих в нее объектов;

тп - технологический процесс;

он, Ок - начальная и конечная операции для прерваных техпроцессов;

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

Р - приоритет партии.

Для каждой партии в целевом задания определен некоторый технологический процесс :

ТПГ < °1к>к=1,К1 •

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

Хо1к= < 1о1к- ё1к, т1к> 'гда

о - имя операции;

§ - обобщенный ресурс;

т - нормативное время выполнения операции о.

Обобщенный ресурс представляет собой множество имен групподнородных ресурсов, различающихся по типам:

{ }1-1.11к. где

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

Группы ресурсов выбираются из общего множества ресурсов о представленного J тшами, каждый из которых разбит на м^групп :

о = { / а* = ( 4 }.=1><т

однородных ресурсов, где группе однородного ресурса состоит из отдельных единиц :

^а = { ^шп }п=1

т

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

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

= < 1*4 , .....>,где

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

Система . ограничений (Ф) складывается из множества основных и неосновных ограничений.

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

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

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

для V 1',1н V к',к" V ,1*1 "«г

если [(IV к")]&[(111к,< 1111к„)У(11Ик„< ?11к,)],

11 1« то е1к * ;

- соблюдение связей операций то заданному техпроцессу:

для V 1 V к',к» : к' < к" => 11к, < ^1кН ;

- соблюдение сроков начала - окончания разработок;

для V 1 V к => 11к > г & I с 1„ ;

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

для V 1 V к => - ^ )= ;и т.д.

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

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

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

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

В основу реализации прогрр*«мной системы положен метод двойного ранжирования, основанный на декомпозиции критерия во множество оптимизирующих условий (ФП). Дадим формализованное описание метода:

Задача составления расписания для МОР описывается с помощью пятерки:

{ е, 1, V, ф, ф >; где

~ МНОЖ0СТВО типов объектов, участвующих в процессе функционирования;

1 - упорядочивания функция для типов объектов;

~ Упорядочивающие функции для объектов одного

типа*

~ ограничения задачи для каждого типа

объектов;

~ ограничения системы (технологические) для каждого типа объектов.

Соответственно, необлодимо ввести определения для упорядочивания и проверки ограничений.

Упорядочение. Пусть задано некоторое множество и упорядочивающая функция в : Ы ■* н, тогда и упорядочено по в (по возрастанию), если

37:Х*Х : VI»,1" 7(1')<7(1") => В(т1,)<В(ш1м), где

Упорядочение типов объектов проведено, если для Е={Е1)1=ТТТ задш?а некоторая упорядочивающая функция г: Е ■* л:

Зх:Х*Х : VI',1" %(±*)<Х(А") => *<Е1,)<1(Е±и).

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

Проверка ограничений. Пусть задано некоторое множество и ограничение ф в виде функции ф: ы .{0,1}, где

х={1.....I), тогда множеством удовлетворяющим ограничению ф,

назовем такое множество ы^, что

VI rfl)=M\{mi:(|)(m1)=0}.

Естественным путем для сокращения мсг^ости кногэствэ, которое необходимо упорядочить, является предварительный учет всех ограничения. Однако нэ все ограничения, гагут Сыть рассмотрены на данном этапе. Дело в тон, что просэрха ограничений задачи для элементов лвбого типа шгэт быть отлокена в процессе набора комбинации до того гаг*.епта, пока d этой комбинации не окакутся некоторые црэдопредэлешко тшы элементоз. Напрпглэр, в простейшем случае, наличие временного промежутка для транспортной операции у выбранной совокупности элементов мотет бить просэрэно только лтпь послэ Ыгбора кошфзтного транспортного сродства с соотЕотстпуг^зй споростъп. Таким образом, № смеет два места провзрсп огрсппчанЕй. Сначала ' на этапе выбора претендентов проверялся ограничения системы (технологические). Затем, после упорядочил тип, претендента рассматриваются с позиций удовлетворения посмопшх отложенных ограничений - ограничений задачи, для непосредственного вхопдения в комбинацию.

Итак, проверка ограничений систе-ш ф состой? в определении множества прэтендентоз Е|ц)» где i - тип объектов, стос^к после упорядочивания на место х(1), где %(1) - функция обратная к функции x(i) - Ограничений систсмн q для

каждого i-того типа объектов могет бнть несисльно, позтсг^у

«? " { "Pin }i-lti . n-l.Hj-

Тогда, с учетом прогэдмго упорядочения тппоз по f :

ni ' ' Vi ^(i) - W(eXd).J !n2?-tíX(i).n(eX(i).á) }

teosecTBo претендентоп упорядочиваем та заданной

функции Y-(1) : 3 р:Х-а : Vk\ k"

p(k-) < P(k-) -> Ví(i)(e»(i)tk,).< ^(1)(e¡(1)>¡£B).

гдо x-{1.....

Ограничения задачи, которые могут бить отлозены выглядят следующим образом: для объектов типа i определено Sj ограничений:

íi={íPs.?.s >B=T7S • Us'^iek^TTTT ' гдэ

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

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

VI', VI:

шах к

где 1' - номер текущего уровня.

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

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

3 -Я»^ € ! % „

ш . иш>

Теперь, оперируя данными понятиями, ыоано представить расписание полученное та ВДР.

Расписанием будет некоторое подмножество декартового произведения множеств упорядоченных по. функции * типов влементов, рассматриваемых при постановке задачи: й <= 1£(1)х ^(2)х ... х .

Без ограничения общности предположим, что н

не н х ... х .

Тогда И - { гх : г1-{в|(1)-К1,е|(2), ... ,е|(1)) >1=1>ь, где Ь

1) |Н| = Ь , и {Ь,} = Н.

1-1 1

__«v

2) V 1, V 1 е^^е и П0ЛУчен в соответствии с

минимальным значением функции предпочтения.

Далее, во второй главе приведено доказательство того, что

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

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

Итак, задача составления расписания задается следу едки образом :

< б, с, ТП, о, о, Ф, ФП, рш , т >, или

< Б, С, ТП, О, О, V, ф, ф, Рш , т >,

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

В выделяемый инвариант предлагается в неизменном вида включить следующие параметры модели : а, с, ТП, о, о, ?п, т.

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

Входящие в инвариант : гп, 7Ц, ф^, фц п

входящие в настраиваемую часть : Ун, фц, фц.

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

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

Итак, получали разбиение на инвариантную и няотрвкяяар^пп части :

инвариант : < о, с, ТП, о, о, уц, Рш , 2 >,

настраиваемая часть : < гн, Уц, фц, >.

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

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

В третьей главе цредставлено обсуждение вопросов программной реализации ЦДР для решения ЗСР для ГДТС. В контексте основного ограничения ЗСР - выполнения целевого задания, рассматриваются: метода предварительного анализа выполнения 10; выполненная на их основе алгоритмическая проверка поддеревьев дерева перебора на наличие решения и стратегия направленная на удовлетворение основного ограничения.

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

В рамках данной проблемы можно выделить два пути :

- получение оценки существования решения н соответственно уверенности в том, что поиск его ве окончится безрезультатно;

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

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

Введем множество ' как множество всех подмножеств множества всех открытых слева отрезков лежащих в промежутке планирования (О.Твд]. Назовем множество 'Т' множеством пространств назначения.

Каждому конкретному объекту (партии или ресурсу) поставим в соответствие допустимое пространство назначения :

4» "> • гда *}т «

аналогично для партий :

• р1=> гдэ € 5!.

Исходя из данного определения ПРОСТРАНСТВОМ НАЗНАЧИЛИ совокупности объектов р1, р2, ... , раназовеы

„« П *« П ... (I .

i , . ■ . ,в i с о

Рассмотрим класс отображений а, заданных на етонествв т : О : т ■» т.

На базе введенного класса отобразений а для лэбого объекта заданные ограничения могут быть представлены в виде схимаицего отображения q из класса о : >

р^ => ч : пли где

€ е причем ^ с я^. Аналогично задаются

ограничения.и для ресурсов.

Постановка задачи составления расписания ограничивает интервал на котором ведется планирование. Таким, образом, пространство назначения партий р1 ограничено сверху интервалом планирования о < < т^ , Подсчитав его мощность, с учетом

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

и? = I I. где 1-ТТь . Р1

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

т к1

V - 1Т1

Чк •

к=1

Проверяемое условие выглядит следующим образом :

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

4

Янл = * ^ .

®га п=1

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

Ь К1

RTj -1 I <Tik' • 4 »• r«e

Sm 1=1 k=1

<°lk

При нарушении условия

иначе.

rHj, > rTJ

ßm

говорят о несоставимости расписания в связи с недостатком ресурса.

Данные оценки можно уточнить, учитывая тот факт,что абсолютный наличный ресурс некоторой группы имеет смысл только пр*.{ наличии соответствующего свободного пространства для единиц ресурсов принадлежащих группам связанным с данной в процессе выполнения .операции.Каличие свободного пространства анализируется по отношению к пространству назначения некоторого обрабатываемого объекта, который однозначно присутствует в какдой из составляемых комбинаций и связывает определенные ресурсы на время выполняемой операции. Итак, для некоторой партии р и некоторой группы ресурсов g имеем следующее выражение для наличного ресурса :

Nn

и ( WD П « , ) - ( WD П и « 1 ).

Vl4 11=1 Pl 4а Pl n=1 <4

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

к1

-1 < Tik * < °ik' 4 >• А к=1

Необходимое условие составимости в данном случае имеет следующий вид I

^4 > ^4

Для случая .1=1 и и=1 полученная оценка является достаточно строгой. Рассматривая случай ¿=1, м>1, можно отметить появление моментов не учитываемых рассматриваемой оценкой. Для этого варианта, при выполнении анализа на составимость, получаем уже

множество оценок требуемых и наличных ресурсов для каждой

группы соответственно. Здесь для объемной проверки соответствия

мощности ресурсов целевому заданию необходимо осуществить

проверку необходимого услоеия составимости для вссх подмножеств

множества оценок наличного ресурса. Алгоритмическая сложность

м

группового просмотра составляет 11*2 .

Оценка наличия решения в поддеревьях дерева поиска решения

г lia основе оценок составимости можно провести оценку наличия решения в поддеревьях дерева решения на этапе составления комбинации. Фактически, поиск претендента на вхождение в комбинацию представляет собой опеределение наличия промежутка определенной длительности в его пространстве назначения. Сделать это можно только простым перебором тактов пространств назначения претендентов исследуемой группы. Однако, можно определить занятые такты и на основе этой информации прекратить дальнейший . поиск, если необходимого промежутка заведомо нет. Для этого строится оценочное пространство, которое будет представлять собой потактовое произведение пространств назначения однородных претендентов на вхождение в комбинацию (при кодировании занятого такта единичным битом). Иначе говоря, длл групш однородных претендентов x1t х2 ,..., юге ем оценочное пространство следующего вида : 2 = w и« и ... и* .

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

^КОМб = "р П 21 Л 22 П — Л 2К ' ГД9 wp - пространство назначения выбранной партии;

£к - оценочные пространства груш.

Если такой промежуток найден, то продолжаем поиск, который проходит следующим образом. Из первой группы объектов, удовлетворяющих ограничениям, берем элемент и штаемся оценить существование комбинации с его присутствием : = w Л wi n s2 il ... Л 2К , где

- пространство назначения объекта

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

второй группы пространство 2коми+х1*+21' где ** ~ означает, что

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

Узкие места и применение оценок узости ситуаций в процессе поиска решения

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

Простейшая оценка узости ситуации для партии р^^ выглядит следующим образом :

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

оказался успешным, то рассматриваем для элементов

г =

операции определенной для данного объекта :

«.JSluL.

Е

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

В___четвертой____главе дано описание программного

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

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

В основу комплекса программ положена идея создания ядра системы составления расписания, инвариантность которого к виду ограничений и оптимизирующих требований была задана изначально, что позволило использовать его в качестве инструментального сродства при построении ряда систем оперативного планирования целевого назначения для различных предметных областей. Инвариантное ядро вошло в комплекс программ, оперативного планирования наряду с настраиваемой частью, поддерживающей адаптацию системы к уникальным параметрам реальных обьектов. Комплекс программ выполнен на ПЭВМ ibu/pc в операционной среде US Dos 3.30. Общий объем программ составил 15000 операторов языка программирования TUREо pascal.

В состав комплекса программ оперативного планирования входят подсистема ввода анализа и коррекции информации и подсистема составления расписания.,<

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

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

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

На базе разработанного комплекса программ был спланирован и проведен ряд экспериментов по определению эффективности использования ' результатов исследований. Подтверждена эффективность применения оценок наличия решения на разных этапах составления расписания. Отсечение ветвей не содержащих решепие позволяет сократить общий объем вычислений в 2-3 раза для производственной ситуации, характеризующейся сильной загруженностью исполнительных средств (от 85% и выше). Применение стратегии составления расписания по "узким местам" позволяет проводить динамическое разрешение критичных ситуаций возникввдих в ходе составления расписания независимо от оптимизирующих требований заданных пользователем. На ряде примеров процент полностью составляемых расписаний был повышен на 20-25%.

Разработанный комплекс программ оперативного планирования ГДТС был успешно применен на практике в различных предметных областях : при составлении графика работ конструкторско -технологического отделения ВШИТ; при составлении расписания работы участка термопластавтоматов Новгородского завода им. ХПУ партсъезда; при разработке программного обеспечения учебно-производственного назначения для гибкого участка опытного производства Будапештского Технического Университета.Эффективность указанных реализаций подтверждена соответствующими актами о внедрении.

ЗАКЛЮЧЕНИЕ

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

Основные научные и практические результаты работы сформулируем следующим образом :

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

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

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

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

6. Проведены эксперименты, подтверждающие на ряде примеров эффективность теоретических предложений.

7. Общий экономический эффект от внедрения комплекса программ оперативного планирования составил 50 тысяч рублей.

По теме диссертационной работы Шершнева Д.А. опубликовано 7 печатных работ, в том числе зарегистрировано 2 программных средства в ОВАЛ .МГУ и НИИ ВО.

1. Игнатьев М.Б., Шершнева О-В., Шершнев Д.А. Стратегия оперативного планирования в задаче диспетчирования IHG // Тезисы докладов Всесоюзной научно-технической конференции "Автоматизация исследования, проектирования и испытаний сложных технических систем". Калуга., 1989, с.85.

2. Перовская Е.И., Шершнев Д.А., Шершнева О.В. Программа составления расписания, инвариантная к основным и оптимизирующим требованиям / ОФДП МГУ, LI., 1989. No Ы89063.

3. Перовская К.И., Шершнев Д.А. Оперативное планирование. Комплекс программ / ОМП НИИ ВО, M, 1992. Но 92522.

4. Перовская Е.И., Шершнев Д.А., Шершнева О.В. Разрешение противоречивости моделей в задаче календарного планирования//Тезисы докладов Всесоюзной научно-технической конференции "Автоматизация исследования, проектирования и испытаний сломшх технических систем". Калуга., 1989, с.43-44.

5. Перовская Е.И., Шершнева О.В., Шершнев Д.А. Гибкий подход ît основным и оптимизирующим требованиям в задаче календарного планирования ГПС//Тезисы докладов Всесоюзного научно-технического совещания "Программное обеспечение новой информационной технологии". Калинин., 1989, с.145-146.

6. Шершнева О.В., 'Шершнев Д.А. Программа составления расписания в среде меняющихся целей производства//. Тезисы докладов зональной конференции "Автоматизация технологического проектирования". Пенза.: ПДНТП, 1989, с.58-59.

7. Перовская Е.И., Шершнев Д.А., Шершнева О.В. Разработка системы оперативного планирования для ГПС// Тезисы докладов четвертой Дальневосточной научно-технической конференции "САПР и надежность автоматизированного производства в машиностроении". Владивосток.: ДВПИ, 1990, с.157-158.

, I