Введение к работе
Экономические условия эксплуатации ресурсов целого ряда технических систем предъявляют повышенные требования к таким показателям качества управления, как быстродействие и гибкость настройки на изменяющиеся условия функционирования. К числу таких систем относятся, например, ГЛП и ГПС для мелкосерийного (единичного) производства, средства вычислительной техники и связи, а в наибольшей степени - технологические системы транспортного типа (СТТ).
Среди СТТ особой значимостью указанных обстоятельств отличаются крупномасштабные грузообразующие комплексы внутреннего водного транспорта, характеризующиеся высоким темпом изменения оперативной обстановки и как следствие достаточно жесткими требованиями, предъявляемыми не только к адекватности информационной среды принятия управляющих решений, но и х скорости автоматизированного формирования их проектов.
Актуальным направлением повышения эффективности использования ресурсов СТТ является реализация процессов управления на базе новых информационных технологий.
Данная работа посвящена моделированию и оптимизации процессов управления ресурсами СТТ с учетом специфики ряда массовых технологических процессов, з частности, на внутреннем водном транспорте.
Математическое описание СТТ для рассматриваемых в работе целей выполнено в рамках дискретных моделей однофазного обслуживания процессором (прибором) конечных детерминированных потоков объектов (заявок), т.е. на традиционном для теории расписаний языке постановок задач управления. Адекватность такого формализма реальным транспортно-технологическим процессам достаточно очевидна; при этом обеспечиваемая им точность моделирования динамического поведения объектов СТТ может быть повышена до необходимого уровня за счет выбора шага дискретности пространственно-временных параметров.
Применительно к различным задачам управления обслуживанием потоков объектов в системах со стационарным процессором дискретные оптимизационные модели
рассматривались в работах А.С. Беленького, B.C. Гордона, Р.В. Игудина, Д.И. Когана, СЕ. Ловецкого, B.C. Танаева, Ю.С. Федосенко и других авторов, а соответствующие программно-технические комплексы поддержки управления были созданы, в частности, для Камского грузового района, Уфимского порта и других транспортных предприятий РФ.
В отличие от вышеуказанных исследований и разработок основное внимание в данной работе уделено моделированию и синтезу оптимальных управлений обслуживанием объектов СТТ, в которых подвижность обслуживающего процессора является принципиальным отличительным качеством. Именно благодаря возможности управления дисциплиной перемещения процессора между стационарными терминалами обслуживания может быть в ряде случаев существенно улучшен эффект использования транспортно-технологических ресурсов СТТ.
Известно, что дискретные модели оптимизации использования ресурсов приводят к переборным задачам на конечном множестве допустимых управлений, которые теоретически могут быть решены путем непосредстзен-ной оценки всех возможных вариантов. Однако время, требуемое на отработку переборного алгоритма, сильно зависит от размерности дискретной модели. Например, число различных расписаний в простейшем случае однопроцессорного однофазного обслуживания объектов л-элемецтного потока равно числу всех возможных перестановок, т.е. л!. Это означает, например, чтс на компьютере, оценивающем 600 тысяч расписаний в секунду, задача синтеза оптимального решения для г- « 11 гложет быть решена полным перебором лишь зи 1,) (К-мин (здесь к далее в примерах временные оценги приведены к производительности процессора Pentium 11/233 MHz) . Примеры для других значений г. приведены б таблице 1.
Таблица 1.
О такого рода зависимостях принято говорить, что они носят характер "комбинаторного взрыва". Порождающие их математические модели СТТ приводят обычно к NP-трудной проблематике.
Заметим, что в иззестных эксплуатационных ситуациях на внутреннем водном транспорте модельный параметр п нередко принимает значения от 10 и выше." Так, для пиковых навигационных условий количество объектов з обслуживаемом судопотоке может достигать 15-20 единиц. При этом регламент оперативного управления диспетчерского уровня предполагает формирование суточного план-графика (расписания) обработки тоннажа плавучим грузоперерабатьшающим комплексом з течение одного часа. Ясно, что в подобных случаях синтез оптимального план-графика в режиме real-time переборным алгоритмом практически нереализуем.
Таким образом, возникает проблема разработки существенно более "быстрых" алгоритмов, позволяющих получать решения задач оптимизации однофазного обслуживания объектов дискретных детерминированных по-трков за практически приемлемое время.
Можно выделить два направления исследования задач синтеза оптимальных расписаний обслуживания объектов детерминированного потока.
-
Разработка достаточно быстрых алгоритмов синтеза точного решения для значений п, покрывающих существенную часть практически значимых размерностей потоков. Такие алгоритмы обеспечивают, а частности, возможность получения эталонных решений.
-
Разработка алгоритмов синтеза субопхималъных решений, предназначенных прежде всего для потоков больсой размерности.
Именно эти направления наряду с задачаьги моделирования рабочих процессов в СТТ образуют объект'исследования данной диссертационной работы^
Целью работы является разработка моделе;"!, алгоритмов и программных средств для оптимизации управления однофазным обслуживанием дискретных детерминированных потоков объектов перемещаемым процессором на основе современных информационных технологий.
Достижение поставленной цели требует рассмотрения следующих задач:
-і
обзор отечественной и зарубежной литературы по теме;
разработка базовой модели однофазного обслуживания конечного детерминированного потока объектов перемещаемым процессором и ее обобщающих модификаций ;
постановка экстремальной задачи;
анализ существующих методов решения оптимизационных задач управления однофазным обслуживанием конечных детерминированных потоков объектов;
разработка алгоритмов синтеза точного решения задачи синтеза оптимального расписания однофазного обслуживания конечного детерминированного потока объектов перемещаемым процессором в рамках концепций динамического программирования (ДП) и ветвей и границ (ВГ);
разработка и реализация алгоритмов синтеза субоптимальных расписаний обслуживания потока объектов перемещаемым процессором;
создаНТО» » 1иддд<аовательского программного комплекса для решения задач управления одностадийным обслуживанием потоков объектов перемещаемым процессором.
, Методическую и теоретическую базу диссертационной работы составляют подходы и инструментарий теории управления, теории расписаний и вычислительной сложности комбинаторных задач, математического программирования, вычислительный эксперимент. Лрі: выполнении исследований автор опирался на работа: пс указанным разделам ряда отечественны)' и заруб* -кннх ученых (Д.И. Ватищев, Е.В. Девнер, С.Е., Л^веихий,, М.Х. Прилуцкий, Т.П., Подчасова, СМ. Р«.-зер, В.А. Таланов), а такке на результаты, полученные Д.И. Коганом, Ю.С. Федосенко, B.C. Танеевым, М.И. Фейгиным, В.В. Шкурбой, И.Х, Сигалом, М. Сзгеу, D. Johnson.
Научная новизна работы состоит в следующих выносимых на защиту результатах:
- разработана базовая математическая модель одно
фазного обслуживания конечного детерминированно
го потока объектов перемещаемым процессором, а
также практически значимые модификации базовой модели;
сформулирована экстремальная задача синтеза оптимальной программы управления обслуживанием потока объектов перемещаемым процессором;
разработаны приемлемые для экспериментальных вычислительных исследований и штатного производственного использования алгоритмы синтеза оптимальных и субоптимальных управлений;
разработаны и реализованы программные средства синтеза оптимальных и субоптимальных управлений однофазным обслуживанием объектов конечного детерминированного мультипотока, разглашенные в Internetno адресу
. aqua.sci-nnov.ru/math/shedule. гір
Обоснованность и достоверность результатов обеспечена доказательствами сформулированных в работе положений и вычислительными экспериментами.
Практическая ценность. Разработанные модэли, алгоритмы и программные средства могут быть использованы в исследовательских и производственных компьютерных системах, предназначенных для решения задач оперативного управления дискретными ресурсами в динамических системах транспортного типа.
Реализация результатов работы. Работы по теме диссертации выполнялись в соответствии с координационными планами научных исследований РАН по комплексной программе "Кибернетика", поддержаны грантами Российского фонда фундаментальных исследований (проект 96-01-01428) и Госкомитета по ВО РФ (95.2.4-16). Материал диссертации использован в учебном процессе кафедры Информатики и автоматизации производственных процессов Волжской государственной академии водного транспорта и кафедры Информатики и автоматизации научных исследований Нижегородского государственного университета им. Н.И. Лобачевского.
Ряд созданных в рамках диссертационной работы алгоритмов синтеза оптимальных расписаний передан для использования в специализированных компьютерных системах управления ресурсами на транспортно-техно-логических объектах в портах Казани и Уфы.
ДпроС. у,:я результатов работы. Основные положения и результаты диссертационной работы представлялись и
докладывались на следующих научных конференциях и семинарах.
ХІ-й Международной конференции по проблемам теоретической кибернетики (Ульяновск, 1996} .
IV-й конференции "Нелинейные колебания механических систем".(Нижний Новгород, 1996).
Всероссийских совещаниях-семинарах "Математическое обеспечекие информационных технологий б технике,, образовании и медицине" (Воронеж, 1996, 1997).
- Международной конференции "Нечеткая логика,
интеллектуальные системы и технологии" (Владимир,
1S97).
- Международном семинаре "Нелинейное моделирова
ние и управление"1 (Самара, 1997).
~ Х-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1997).
Третьей международной научно-технической конференции "Новые информационные технологии d региональной инфраструктуре" (Астрахань,, 1997).
2-і; кзхедукародиой научно-технической конференция: Г5Ш;терак?изныг система: Проблемы человеко-компь-гатерногс ьзашюдействик1 (Ульяновск, 1997) .
3-й международной конференции "Дискретные модели е теории управляющих систем", (Москва-Краснови-дозо, 1993).
Публикации. По теьсэ исследования опубликовано 15 работ; основное содержание диссертации отрадно и работах [3.-11].
Структура и объем работы. Диссертация состой; из ведения, пяти глав и заключения. О.ча со.перзчт Z2l> страниц текста, 26 рисунков, список литература а- 5/ наименований и 3 приложения.
