Экономические условия эксплуатации ресурсов целого ряда технических систем предъявляют повышенные требования к таким показателям качества управления, как быстродействие и гибкость настройки на изменяющиеся условия функционирования. К числу таких систем относятся, например, ГАП и ГПС для мелкосерийного (единичного) производства [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 128 578 Год.
О такого рода зависимостях принято говорить что они носят характер «комбинаторного взрыва». Порождающие их математические модели СТТ приводят к 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−1 428) и Госкомитета по ВО РФ (95.2.4−16). Материал диссертации использован в учебном процессе кафедры Информатики и автоматизации производственных процессов Волжской государственной академии водного транспорта и кафедры Информатики и автоматизации научных исследований Нижегородского государственного университета им. Н. И. Лобачевского.
Ряд созданных в рамках данной работы алгоритмов синтеза оптимальных расписаний передан для использования в специализированных компьютерных системах управления ресурсами на ряде транспортно-технологических объектах в портах Казани и Уфы (сведения о практическом использовании приведены в приложении).
Апробация результатов работы. Основные положения и результаты диссертационной работы представлялись и докладывались на следующих научных конференциях и семинарах .
— XI-й Международной конференции по проблемам теоретической кибернетики (Ульяновск, 1996).
— 1У-й конференции «Нелинейные колебания механических систем» (Нижний Новгород, 1996).
— Всероссийских совещаниях-семинарах «Математическое обеспечение информационных технологий в технике, образовании и медицине» (Воронеж, 1996, 1997).
— Международной конференции «Нечеткая логика, интеллектуальные системы и технологии» (Владимир, 1997).
— Международном семинаре «Нелинейное моделирование и управление» (Самара, 1997).
— Х-й Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 1997).
— Третьей международной научно-технической конференции «Новые информационные технологии в региональной инфраструктуре» (Астрахань, 1997).
— 2-й международной научно-технической конференции «Интерактивные системы: Проблемы человеко-компьютерного взаимодействия» (Ульяновск, 1997).
— 3-й международной конференции «Дискретные модели в теории управляющих систем» (Москва-Красновидово, 1998) .
Публикации.
По теме диссертации опубликовано 15 работ, в которых отражено ее основное содержание. Автореферат диссертации в формате PostScript доступен в сети Интернет по адресу ftp://ftp.aqua.sci-nnov.ru/math/referat.zip.
Структура и объем работы.
Диссертация состоит из введения, пяти глав и заключения. Она содержит 125 страниц текста, 2 6 рисунков, список литературы из 52 наименований и 3 приложения .
§ 5.4. Основные результаты и выводы по главе.
1) Создан исследовательский программный комплекс, реализующий разработанную модификацию метода ветвей и границ.
2) Комплекс позволяет:
— строить оптимальные и близкие к ним расписания;
— исследовать расписания и влияние на них изменений параметров модели.
3) Комплекс может быть использован для решения практически значимых задач оперативного управления в системах транспортного типа.
Заключение
.
Основным результатом диссертационной работы является постановка и решение задачи, имеющей существенное значение для создания информационных технологий оперативного управления ресурсами сложных технических систем транспортного типа.
Разработка и использование основанных на созданных в работе моделях, алгоритмах и программных средствах систем динамического планирования позволяет эффективно эксплуатировать оборудование и транспортные средства (в частности, внутреннего водного транспорта), сокращать эксплуатационные расходы за счет повышения эффективности их функционирования и снижения уровня неоправданных простоев.
При решении указанной задачи получены следующие научно-технические результаты.
1. Построена базовая математическая модель обслуживания потока объектов перемещаемым процессором и ее обобщающие модификации, адекватно покрывающие представительное многообразие оперативных условий функционирования ряда массовых транспортно-техноло-гических процессов.
2. Сформулированы и теоретически исследованы экстремальные задачи синтеза оптимальных программ управления обслуживанием потока объектов перемещаемым процессором.
3. Разработаны алгоритмы синтеза точных и приближенных решений задачи оптимального управления однофазным обслуживанием потока объектов перемещаемым процессором.
4. Создан исследовательский программный комплекс для решения задач управления одностадийным обслуживанием потоков объектов перемещаемым процессором.
5. Разработанные алгоритмы переданы для реализации в системах управления транспортно-технологичес-кими процессами на предприятиях внутреннего водного транспорта.
