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

/

ВОЛЖСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ВОДНОГО ТРАНСПОРТА

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

ШЕЯНОВ Анатолий Владимирович

МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ УПРАВЛЕНИЯ ОБСЛУЖИВАНИЕМ ДЕТЕРМИНИРОВАННЫХ ПОТОКОВ ОБЪЕКТОВ ПЕРЕМЕЩАЕМЫМ ПРОЦЕССОРОМ

Специальность 05.13.01 — Управление в технических системах

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

Научный руководитель: д.т.н. профессор Ю.С. Федосенко Научный консультант: к.ф.-м.н. доцент Д.И. Коган

Н.Новгород

1998

ВВЕДЕНИЕ............................................................................................................................................ 4

ГЛАВА 1. ПОТОКОВЫЕ ЗАДАЧИ ОБСЛУЖИВАНИЯ: ОБЗОР ЛИТЕРАТУРЫ И ПРОБЛЕМАТИКА............................................................................................................................... 19

§1.1. Потоковые задачи обслуживания.............................................................................................. 19

§1.2. О вычислительной сложности потоковых задач обслуживания ......................................... 22

§1.3. Возможные подходы к решению................................................................................................24

§1.4. Выводы по главе..........................................................................................................................27

ГЛАВА 2. МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ ОБСЛУЖИВАНИЯ БИНАРНОГО ПОТОКА ОББЕКТОВ........................................................................................................................ 29

§2.1. Построение математической модели........................................................................................29

п. 2,1.1. Содержательная постановка ............................................................................................ 29

п.2.1.2. Математическая модель.................................................................................................... 30

п.2.1.3. Постановка экстремальной задачи.................................................................................... 32

§2.2. Оценка вычислительной сложности задачи.............................................................................33

§2.3. Применение метода динамического программирования для решения задачи...................34

п.2.3.1. Алгоритм решения методом ДП........................................................................................ 34

п. 2.3.2. Варианты улучшения алгоритма........................................................................................ 38

п. 2.3.3. Опыт реализации алгоритма.............................................................................................. 40

п. 2.3.4. Пример технологии расчета............................................................................................... 42

п. 2.3.5. Результаты вычислительного эксперимента.................................................................... 46

§2.4. Применение метода ветвей и границ к решению задачи.......................................................49

п. 2.4.1. Алгоритм решения методом ВГ.......................................................................................... 49

п.2.4.2. Возможные вариатыреализации алгоритма .................................................................... 56

п. 2.4.3. Пример технологии расчета............................................................................................... 60

п. 2.4.4. Результаты вычислительного эксперимента.................................................................... 66

§2.5. Основные результаты и выводы по главе.................................................................................72

ГЛАВА 3. МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ ОБСЛУЖИВАНИЯ МУЛБТИПОТОКА ОББЕКТОВ.......................................................................................................................................... 73

§3.1. Построение математической модели........................................................................................73

п.3.1.1. Содержательная постановка ............................................................................................ 73

п.3.1.2. Математическая модель .................................................................................................... 75

п.3.1.3. Постановка экстремальной задачи.................................................................................... 76

§3.2. Применение метода ветвей и границ к решению задачи.........................................................77

§3.3. Результаты вычислительного эксперимента...........................................................................78

§3.4. Полиномиально разрешимые частные подклассы задачи синтеза.......................................79

§3.5. Обобщения рассматриваемой модели.......................................................................................83

п.3.5.1. Учет директивных сроков обслуживания объектов........................................................ 83

п. 3.5.2. Учет штрафов за простой процессора ............................................................................ 85

§3.6. Основные результаты и выводы по главе................................................................................. 86

ГЛАВА 4. РАЗРАБОТКА АЛГОРИТМОВ СИНТЕЗА РАЦИОНАЛЬНЫХ РАСПИСАНИЙ ДЛЯ ОДНОПРОЦЕССОРНЫХ МОДЕЛЕЙ ОДНОФАЗНОГО ОБСЛУЖИВАНИЯ. ОЦЕНКА УСТОЙЧИВОСТИ РЕШЕНИЯ ........................................................................................................ 88

§4.1. Алгоритмы синтеза рациональных расписаний......................................................................88

п.4.1.1. Простейшие алгоритмы..................................................................................................... 90

п. 4.1.2.Алгоритм последовательного зондирования....................................................................... 90

п. 4.1.3. (р,ф-алгоритм .................................................................................................................... 91

п.4.1.4. Использование алгоритма ветвей и границ в качестве эвристического.......................... 92

п.4.1.5. Кристаллизация (simulated annealing) ................................................................................ 94

§4.2. Результаты вычислительного эксперимента........................................................................... 96

§4.3. Оценка устойчивости решения............................................................................................... 100

п.4.3.1. Понятие устойчивости .................................................................................................... 100

п. 4.3.2. Пример численного исследования устойчивости решения............................................. 103

§4.4. Основные результаты и выводы по главе............................................................................... 107

ГЛАВА 5. СТРУКТУРА ПРОГРАММНОГО КОМПЛЕКСА...................................................... 108

§5.1. Назначение и возможности программного комплекса........................................................ 108

п. 5.1.1 Краткое описание .............................................................................................................. 108

п. 5.1.2 Характеристики и возможности комплекса.................................................................... 108

§5.2. Структура программного комплекса...................................................................................... 110

§5.3. Интерфейс программного комплекса..................................................................................... 111

п.5.3.1 Возможности, предоставляемые интерфейсным модулем............................................. 111

п.5.3.2 Структура меню................................................................................................................ ИЗ

п.5.3.3 Рабочие экраны программы............................................................................................... 113

§5.4. Основные результаты и выводы по главе............................................................................... 116

ЗАКЛЮЧЕНИЕ ................................................................................................................................. 117

ЛИТЕРАТУРА ................................................................................................................................... 119

ПРИЛОЖЕНИЯ................................................................................................................................. 127

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

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

Приложение 3. Исходные тексты программных модулей

ВВЕДЕНИЕ

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

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

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

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

Математическое описание СТТ для рассматриваемых в работе целей выполнено в рамках дискретных моделей однофазного обслуживания процессором (прибором) конечных

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

Применительно к различным задачам управления ресурсами в системах со стационарным процессором дискретные оптимизационные модели обслуживания рассматривались в работах А.С.Беленького [14], В.С.Гордона [24], Р.В.Игудина [19], Д.И.Когана [32], С.Е.Ловецкого [43] [10], B.C.Танаева [45], Ю. С.Федосенко [49] и ряда других авторов, а соответствующие программно-технические комплексы поддержки управления СТТ были созданы, в частности, для Камского грузового района, Уфимского порта и других [21][22].

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

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

конечном множестве допустимых управлений и теоретически могут быть решены путем непосредственной оценки всех возможных вариантов. Однако время, требуемое на отработку переборного алгоритма, сильно зависит от размерности дискретной модели. Например, число различных расписаний в простейшем случае однопроцессорного однофазного обслуживания объектов «-элементного потока равно числу всех возможных перестановок, т.е. п\. Это означает, что на компьютере, оценивающем 600 тысяч расписаний в секунду (Pentium 11/233 MHz), частная задача синтеза оптимального решения для п = 11 может быть решена полным перебором лишь за 1,109 мин. Данные для других значений п приведены в таблице 1.

Таблица 1.

п Время синтеза Единица измерения

оптимального решения времени

10 б, 048 Секунда

15 25,225 Сутки

17 18,798 Год

20 128578 Год

О такого рода зависимостях принято говорить что они носят характер "комбинаторного взрыва". Порождающие их математические модели СТТ приводят к NP-трудной проблематике [34],[25].

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

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

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

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

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

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

Именно эти направления, наряду с задачами моделирования рабочих процессов в СТТ, образуют объект исследования данной диссертационной работы.

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

Достижение намеченной цели требует рассмотрения следующих задач:

- обзор отечественной и зарубежной литературы по теме;

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

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

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

- разработка алгоритмов синтеза точного решения задачи синтеза оптимального расписания обслуживания конечного детерминированного потока объектов перемещаемым процессором в рамках концепций Динамического программирования (ДП) и Ветвей и границ (ВГ);

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

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

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

рования, вычислительный эксперимент. При выполнении исследований автор опирался на работы по указанным разделам ряда отечественных и зарубежных ученых (Батищев Д.И., Беленький A.C., Бурков В.Н.,

Левнер Е.В., Ловецкий С.Е., Прилуцкий М.Х.,

Подчасова Т.П., Резер С.М., Советов Б.Я.,

Сотсков Ю.Н., Стронгин Р.Г., Таланов В.А.), а также на результаты, полученные Коганом Д.И., Федосенко Ю.С., Сигалом И.Х., Танаевым B.C., Фейгиным М.И.,

Шкурбой В.В., Garey М., Johnson D.

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

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

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

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

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

ftp://ftp.aqua.sci-nnov.ru/math/shedule.zip

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

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

Реализация результатов работы. Работы по теме диссертации выполнялись в соответствии с координационными планами научных исследований РАН по комплексной программе "Кибернетика", поддержаны грантами Российского фонда фундаментальных исследований (проект 9601-01428) и Госкомитета по ВО РФ (95.2.4-16). Материал диссертации использован в учебном процессе кафедры Информатики и автоматизации производственных процессов Волжской государственной академии водного транспорта и кафедры Информатики и автоматизации научных исследований Нижегородского государственного университета им. Н.И.Лобачевского.

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

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

- XI-й Международной конференции по проблемам теоретической кибернетики (Ульяновск, 1996).

- 1У-й конференции "Нелинейные колебания механических систем" (Нижний Новгород, 1996).

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

- Международной конференции "Нечеткая логика, интеллектуальные системы и технологии" (Владимир, 1997).

- Международном семинаре "Нелинейное моделирование и управление" (Самара, 1997).

- Х-й Всеро�