Содержание к диссертации
ВВЕДЕНИЕ 4
ГЛАВА 1. УПРАВЛЕНИЕ ОБСЛУЖИВАНИЕМ ЛИНЕЙНО РАССРЕДОТОЧЕННОЙ
ГРУППЫ СТАЦИОНАРНЫХ ОБЪЕКТОВ ОДНИМ MOBILE-ПРОЦЕССОРОМ 19
1.1. Построение математической модели 19
-
Содержательная постановка задачи 19
-
Математическая модель обслуживания линейно рассредоточенной группы
стационарных объектов 20
1.1.3. Постановка задачи синтеза оптимальной стратегии управления обслуживанием 23
1.2. Синтез оптимальной стратегии на основе идеологии динамического программирования 24
-
Построение соотношений динамического программирования 24
-
Описание алгоритма синтеза оптимальной стратегии обслуживания 27
-
Пример реализации технологии расчета 28
-
Результаты вычислительных экспериментов 31
-
Сравнение оптимальных и элементарных стратегией обслуживания 33
ВЫВОДЫ ПО ГЛАВЕ 1 40
ГЛАВА 2. УПРАВЛЕНИЕ ОБСЛУЖИВАНИЕМ ЛИНЕЙНО РАССРЕДОТОЧЕННОЙ ГРУППЫ
ОБЪЕКТОВ ДВУМЯ MOBILE-ПРОЦЕССОРАМИ ПРИ ПОПУТНОМ ДВИЖЕНИИ 42
2.1. Построение математической модели 42 "
-
Содержательная постановка задачи 42
-
Математическая модель обслуживания 43
-
Постановка задачи синтеза оптимальной стратегии управления 45 *
2.2. Синтез оптимальной стратегии обслуживания на основе идеологии
динамического программирования 46
-
Построение соотношений динамического программирования 46
-
Описание алгоритма синтеза оптимальной стратегии обслуживания 48
-
Пример реализации технологии расчета 50
2.3. Синтез оптимальной стратегии обслуживания в случае идентичных mobile-процессоров 55
-
Построение соотношений динамического программирования 55
-
Описание алгоритма синтеза оптимальной стратегии обслуживания 57
-
Пример технологии расчета 58
-
Результаты вычислительных экспериментов 61
2.4. Оценка устойчивости стратегий по структуре 65
-
Понятие устойчивости стратегий по структуре 65
-
Построение карт устойчивости по структуре 66
2.4.3 Примеры карт устойчивости по структуре оптимальных стратегий обслуживания 70
ВЫВОДЫ ПО ГЛАВЕ 2 72
ГЛАВА 3. УПРАВЛЕНИЕ ОБСЛУЖИВАНИЕМ ЛИНЕЙНО РАССРЕДОТОЧЕННОЙ ГРУППЫ
ОБЪЕКТОВ ДВУМЯ MOBILE-ПРОЦЕССОРАМИ ПРИ ВСТРЕЧНОМ ДВИЖЕНИИ 74
3.1. Математическая модель обслуживания и постановка задачи синтеза оптимальной стратегии 74
-
Построение математической модели 74
-
Постановка задачи синтеза оптимальной стратегии 75
3.2. Синтез оптимальной стратегии обслуживания 76
-
Построение соотношений динамического программирования 76
-
Описание алгоритма синтеза оптимальной стратегии обслуживания 78
-
Пример реализации технологии расчета 80
-
Результаты вычислительных экспериментов 85
3.3. Оценка устойчивости стратегий по структуре 88
-
Построение карт устойчивости по структуре 88
-
Примеры карт устойчивости по структуре оптимальных стратегий обслуживания 91
Выводы по главе 3 94
ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС СИНТЕЗА, ВИЗУАЛИЗАЦИИ И ОЦЕНКИ
УСТОЙЧИВОСТИ ПО СТРУКТУРЕ СТРАТЕГИЙ ОБСЛУЖИВАНИЯ ЛИНЕЙНО
РАССРЕДОТОЧЕННОЙ ГРУППЫ СТАЦИОНАРНЫХ ОБЪЕКТОВ
MOBILE-ПРОЦЕССОРАМИ 95
4.1. Назначение и возможности программного комплекса 95
4.2. Структура и интерфейс программного модуля «Бункеровка» 96
4.3. Программный модуль анимации стратегий обслуживания 100
Выводы по главе 4 104
ЗАКЛЮЧЕНИЕ 105
ЛИТЕРАТУРА 107
ПРИЛОЖЕНИЯ 116
Приложение 1. Исходные тексты программных модулей 117
Приложение 2. Акт внедрения результатов результатов диссертационной работы
в Уфимском речном порту 159
Приложение 3. Акт внедрения результатов диссертационной работы в учебный процесс ВГАВТ 160
Приложение 4. Акт внедрения результатов диссертационной работы в учебный процесс ННГУ
им. Н.И.Лобачевского 161
Введение к работе
Русловая добыча нерудных строительных материалов (НСМ), осуществляемая плавучими добывающими комплексами, является одной из основных видов деятельности предприятий внутреннего водного транспорта
РФ [13] .
Промышленно значимые полигоны русловой добычи НСМ обычно простираются на несколько сот километров и в период навигации на них работает до 2 0-30 единиц добывающих комплексов [10] . Объемы добычи НСМ на таких полигонах бассейнов судоходных систем РФ измеряются десятками миллионов тонн за навигацию. Примером таких полигонов является Камский грузовой район (КГР) [14, 55]: протяженность КГР достигает 400 км и он простирается от устья реки Камы до устья реки Белой (Рис. 1).
КАЗАНЬ НАжмилЦйпы 1 Берсуг л пнчитвчоти #
Рыбная Спобсэда с^ ^ ^% ^ь р.Кама
Чистополь
Рис. 1. Камский грузовой район
На рис.1, использованы следующие пиктограммы: mm, і л, -^» - добывающие комплексы различных типов, в том числе, типа «Прага», типа «Эжекторный» и т. д. ; ^ЕЕЗЕЕз, cdczzxzd - грузовые суда и составы, обеспечивающие вывоз НСМ к потребителям приволжского региона.
НСМ поставляется различным предприятиям, осуществляющим выпуск железобетонных изделий для промышленного и гражданского строительства, реконструкции существующих и прокладки новых автомагистралей, мостового строительства и т.п. [43].
Энергетические установки плавучих добывающих комплексов (ПДК) работают на дизельном топливе, снабжение которым, как правило, осуществляется одним или двумя закрепленными специализированными танкерами-заправщиками в зависимости от условий и возможностей конкретного предприятия, а также судами транзитного (обычно нефтеналивного) флота.
Суточное потребление дизельного топлива одним ПДК в рабочем режиме составляет от двух до десяти тонн и находится в прямой связи с его типом, производительностью и техническим состоянием [50] . А это значит, что общее потребление топлива на полигоне может достигать нескольких сот тонн в сутки. При этом соответствующая финансовая составляющая покрывает до 33%всех расходов на содержание и эксплуатацию ПДК.
Резкое повышение цен на нефтепродукты, произошедшее в РФ за последние годы, и, как следствие, сокращение возможностей добывающе-транспортных предприятий внутреннего водного транспорта по созданию оперативных запасов топлива вынуждает последних изыскивать и реализовывать такие технологии управления снабжением дизельным топливом, которые бы обеспечивали максимально возможное сокращение непроизводительных простоев плавучих добывающих комплексов по причине отсутствия дизельного топлива [47, 48, 4 9] .
Как показал анализ, типовыми технологическими схемами снабжения дизельным топливом плавучих добывающих комплексов являются следующие. а) В границах руслового полигона работает один специализированный танкер; обслуживание (бункеровка дизельным топливом) всех ПДК осуществляется при совершении танкером кругового рейса [42]. б) Все ПДК обслуживаются двумя бункеровщиками, движущимися на полигоне русловой добычи НСМ с временным сдвигом в одном направлении (попутное движение). в) Обслуживание всех добывающих комплексов выполняется на полигоне двумя движущимися во встречных направлениях танкерами.
В схемах б) ив) в качестве бункеровщиков могут выступать как закрепленные за полигоном танкеры-заправщики, так и суда, проходящие полигон транзитом; возможен и смешанный вариант снабжения ПДК дизельным топливом, осуществляется одним закрепленным танкером-бункеровщиком и транзитным судном.
При формировании оперативного план-графика (расписания) бункеровок требуется учет целого ряда факторов [11, 15, 41], к числу которых, прежде всего, относятся: запас дизельного топлива на борту каждого ПДК, его производительность и координаты расположения на полигоне; планы проведения ремонтных и профилактических работ; выполнение договорных обязательств воднотранспортного предприятия перед клиентами; принятые на конкретном предприятии технологические схемы снабжения дизельным топливом.
Естественно, что при традиционном подходе к разработке оперативного плана снабжения добывающих комплексов дизельным топливом количественно учесть и оценить вышеуказанные факторы невозможно даже опытному диспетчеру - лицу, принимающему решения (ЛПР). При этом следует иметь в виду, что штатным регламентом работы диспетчера на формирование и согласование оперативного плана-графика снабжения отводится от 15 до 30 минут.
В силу указанных обстоятельств практически разработка план-графика бункеровок осуществляется ЛПР на основе личного опыта, индивидуальных представлений и предпочтений и, как показывает анализ, такие план-графики обычно содержат значительные резервы ' для улучшения и повышения эффективности использования добывающей техники всего полигона [22].
Очевидно, что при должной формализации вышеописанная проблема может быть эффективно решена на базе применения современных IP-технологий путем создания компьютерных систем поддержки организационного управления [20, 21, 4 6] процессами снабжения ПДК дизельным топливом [52].
Как следует из работ, посвященных моделированию и исследованию процессов управления транспортно-технологическими процессами [12, 24], в том числе в крупномасштабных грузообразующих районах [17, 57, 58], адекватное математическое описание моделей снабжения топливом плавучих добывающих комплексов может быть выполнено в дискретном времени [2, 16] на языке однофазного обслуживания объектов (потоков объектов) [35, 38] . При таком подходе синтез оптимальных план-графиков (расписаний, стратегий) бункеровок может быть осуществлен на основе идеологии дискретного динамического программирования[7], ветвей и границ[37].
Научные исследования по данному направлению базируются на фундаментальных работах по теории расписаний [36], в том числе М. Garey, D. Johnson [1] , B.C. Танаева [54, 55], В.В. Шкурбы [55]. Применительно к различным задачам управления ресурсами и, в частности транспортно-технологических систем, дискретные динамические модели исследовались в работах Д.И. Батищева [3], А.С. Беленького [5, 6], В.Н. Бурков [8], Д.И. Когана и Ю.С. Федосенко [29 - 34], Т.П. Подчасовои [44], М.Х. Прилуцкого [45], И.Х. Сигала [37]. Ряд моделей управления обслуживанием потоков объектов транспортного типа в системе независимых процессоров исследовался в работах А.В. Шеянова [59, 60], А.В. Куранова [39, 40]. Частной задаче бункеровки группы объектов посвящена статья Д.И. Когана, Ю.С. Федосенко, А.В. Ершова [19].
Как следует из вышеупомянутых работ, практическая применимость алгоритмов синтеза оптимальных решений в задачах управления ресурсами систем транспортного типа [23, 2 6] непосредственно определяется вычислительной сложностью решающих алгоритмов [1, 4, 9] и, как следствие, допускаемой рабочим регламентом продолжительностью нахождения оптимизированного решения.
Именно алгоритмы синтеза оптимальных решений, приемлемых по своим характеристикам для практического использования, наряду с задачами моделирования процессов транспортно-технологического обслуживания добывающих, лесоразрабатывающих и им функционально подобных линейно рассредоточенных производственных комплексов, а также систем коммунального хозяйства образуют объект исследования данной диссертационной работы.
Целью работы является разработка моделей, алгоритмов, а также программных средств для решения задач синтеза оптимальных стратегий снабжения дизельным топливом линейно рассредоточенной в крупномасштабном грузообразующем районе группы плавучих добывающих комплексов для совокупности Є всех известных технологических схем бункеровок. В основе моделирования последних лежит идеология представления транспортно-технологических процессов как обслуживание линейно рассредоточенной группы 0п стационарных объектов в линейной рабочей зоне S mobile-процессоров, а именно: - обслуживание всех объектов группы 0п осуществляется одним mobile-процессором Р, совершающим в зоне S круговой рейс; обслуживание всех объектов группы 0п осуществляется двумя независимыми взаимозаменяемыми mobile-процессорами Pi и Р2, поступательно перемещающимися в зоне S в одном направлении с временным начальным сдвигом относительно друг друга; обслуживание всех объектов группы 0П осуществляется двумя независимыми взаимозаменяемыми mobile-процессорами Pi и Р2, поступательно перемещающимися в зоне S в противоположных направлениях.
Достижение поставленной цели требует рассмотрения следующих задач: обзор литературы по теме исследования; разработка для типовых технологических схем 0 адекватных математических моделей обслуживания процессорами транспортного типа (mobile-процессорами линейно рассредоточенной группы стационарных объектов); постановка экстремальных задач синтеза оптимальных стратегий управления для математических моделей однократного однофазного обслуживания линейно рассредоточенной группы объектов mobile-процессорами; разработка и реализация алгоритмов синтеза оптимальных стратегий управления обслуживанием линейно рассредоточенной группы объектов, обладающих достаточными для решения практических задач значениями технических (скоростных и объемных) параметров; создание исследовательского программного комплекса для решения задач управления обслуживанием mobile-процессорами линейно рассредоточенной группы стационарных объектов.
Научная новизна работы состоит в следующих выносимых на защиту результатах.
Разработаны базовые математические модели однофазного однократного обслуживания линейно рассредоточенной группы стационарных объектов mobile-процессорами, адекватно описывающие типовые схемы бункеровок ПДК в крупномасштабных полигонах русловой добычи НСМ.
В рамках моделей (п. 1) сформулированы экстремальные задачи синтеза оптимальных стратегий управления обслуживанием.
Для решения экстремальных задач (п. 2) разработаны алгоритмы синтеза оптимальных стратегий управления обслуживанием, обладающие достаточными для решения практических задач значениями скоростных и объемных параметров.
Изучены особенности разбиения плоскости параметров математических моделей обслуживания . (п. 1) на зоны устойчивости по структуре оптимальных стратегий.
Разработан программный комплекс для решения задач управления обслуживанием линейно рассредоточенной группы стационарных объектов mobile-процессорами.
Апробация работы. Основные положения диссертации докладывались и обсуждались на следующих научно-технических форумах: VI Международном конгрессе по математическому моделированию (г. Нижний Новгород, 2003 г.);
6-м Международном научно-промышленном форуме «Великие реки _ 2004» (г. Нижний Новгород, 2004 г.);
Всероссийской научно-технической конференции «Информационные системы и технологии ИСТ-2005», посвященной 60-летию Победы в Великой Отечественной войне и 110-летию изобретения радио А. С. Поповым (г. Нижний Новгород, 2005 г.);
7-м Международном научно-промышленном форуме «Великие реки _ 2005» (г. Нижний Новгород, 2005 г.);
Всероссийской научно-практической конференции «Актуальные проблемы использования и развития новых информационных технологий в России» (г. Нижний Новгород, 2005 г.);
Научно-методической конференции профессорско-преподавательского состава, аспирантов и специалистов, посвященной 75-летию ВГАВТ (г. Нижний Новгород, 2005 г.) ;
10-й Нижегородской сессии молодых ученых (г. Дзержинск, 2006 г.)
Всероссийской научно-технической конференции «Информационные системы и технологии», посвященной 70-летию факультета информационных систем и технологий (ИСТ-2006) (г. Нижний Новгород, 2006 г.); - Секции "Принятие оптимальных решений в прикладных задачах" конференции "Технологии Microsoft в теории и практике программирования" (Нижний Новгород, 2006 г.).
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и 4 приложений; содержит 161 страницу текста, 25 рисунков и список литературы из 60 наименований.
Во введении выполняется общий системный анализ проблемы, обосновывается актуальность исследований, формулируется цель работы, раскрывается научная и практическая значимость полученных результатов. Проводится обзор научной литературы по темам, примыкающим к проблематике диссертации, и аннотировано по главам излагается обзор содержания диссертации.
В первой главе (Управление обслуживанием линейно рассредоточенной рруппы стационарных объектов одним mobile-процессором) рассматривается задача однофазного однократного обслуживания линейно рассредоточенной группы стационарных объектов, расположенных в одномерной рабочей зоне mobile-процессора: строится математическая модель обслуживания, формулируется экстремальная задача, разрабатывается алгоритм синтеза оптимального управления обслуживанием, приводятся пример его реализации и результаты вычислительных экспериментов.
1.1 посвящен описанию содержательной постановки задачи, построению базовой математической модели МІ (в рамках естественного для задач оперативного управления детерминированного формализма); в заключение 1.1 ставится экстремальная задача синтеза однократного однофазного обслуживания линейно рассредоточенной группы объектов mobile-процессором.
1.2 посвящен решению экстремальной задачи. При этом в п. 1.2.1 выводятся решающие рекуррентные соотношения динамического программирования.
В п.1.2.2 и п.1.2.3 излагается алгоритм А1 синтеза оптимальных стратегий обслуживания линейно рассредоточенной группы объектов одним mobile-процессором и приводится пример технологии расчета.
Пункт 1.2.4 посвящен описанию условий и результатов вычислительных экспериментов, целью которых являлось определение средней продолжительности Тс отработки алгоритма Al.
В п. 1.2.5 введено понятие элементарной стратегии обслуживания mobile-процессором группы 0п стационарных объектов; приведены сравнительные результаты оценки эффективностеи (оптимальной и элементарной стратегий управления обслуживанием).
Во второй главе (Управление обслуживанием линейно рассредоточенной группы объектов двумя mobile-процессорами при попутном движении) рассматривается задача однократного однофазного обслуживания линейно рассредоточенной группы объектов, расположенных в одномерной рабочей зоне двух независимых взаимозаменяемых mobile-процессоров, поступательно перемещающихся в одном направлении.
2.1 посвящен содержательному описанию задачи, построению математической модели M2lf а также постановке экстремальной задачи синтеза однократного однофазного обслуживания линейно рассредоточенной группы объектов 0п двумя независимыми взаимозаменяемыми mobile-процессорами Pi, Р2, поступательно перемещающимися в одном направлении в рабочей зоне.
2.2 посвящен решению экстремальной задачи для сформулированной модели двухпроцессорного обслуживания. При этом в п. 2.2.1 выводятся решающие рекуррентные соотношения динамического программирования.
В п. 2.2.2. излагается алгоритм А2г синтеза оптимальных стратегий обслуживания линейно рассредоточенной группы объектов двумя независимыми взаимозаменяемыми mobile-процессорами, поступательно перемещающимися в одном направлении.
Пример технологии расчета с помощью алгоритма А2г приводится в п. 2.2.3.
В 2.3 рассматривается имеющая отдельное практическое значение модель М22 синтеза оптимальной стратегии обслуживания для системы двух идентичных mobile-процессоров. В п. 2.3.1 выводятся решающие рекуррентные соотношения динамического программирования.
В п. 2.3.2 и п. 2.3.3 излагается алгоритм А22 синтеза оптимальных стратегий обслуживания для данного случая и приводится пример технологии расчета.
Пункт 2.3.4 посвящен описанию условий и результатов вычислительных экспериментов, позволивших установить скоростные параметры алгоритмов А2г и А22, а также определить объемы оперативной памяти, требуемой для их реализации.
В 2.4 введено понятие устойчивости по структуре стратегии обслуживания применительно к задачам синтеза оптимальных стратегий обслуживания линейно рассредоточенной группы объектов двумя независимыми взаимозаменяемыми mobile-процессорами. Построены карты устойчивости по структуре полученных оптимальных стратегий, приведены результаты вычислительных экспериментов.
В третьей главе (Управление обслуживанием линейно рассредоточенной группы объектов двумя mobile-процессорами при встречном движении). Рассматривается синтез оптимальных управлений обслуживанием линейно рассредоточенной группы объектов двумя независимыми взаимозаменяемыми mobile-процессорами, поступательно перемещающимися в противоположных направлениях. Строится математическая модель обслуживания и выводятся решающие соотношения динамического программирования. Описывается алгоритм синтеза оптимальных стратегий обслуживания и приводятся примеры конфигураций карт устойчивости в плоскости параметров модели обслуживания.
3.1 посвящен построению математической модели МЗ и постановке экстремальной задачи однократного однофазного обслуживания линейно рассредоточенной группы объектов двумя независимыми взаимозаменяемыми mobile-процессорами, поступательно перемещающимися в линейной рабочей зоне во встречных направлениях.
Для решения экстремальной задачи в п. 3.2.1 выводятся решающие рекуррентные соотношения динамического программирования.
В п. 3.2.2 излагается алгоритм A3 синтеза оптимальных стратегий обслуживания линейно рассредоточенной группы объектов двумя независимыми взаимозаменяемыми mobile-процессорами, поступательно перемещающимися в одном направлении, а в п. 3.2.3 приводится пример технологии расчета.
Пункт 3.2.4 посвящен описанию условий и результатов вычислительных экспериментов, целью которых являлось определение средней продолжительности Тс отработки алгоритма A3, а также требуемых ресурсов оперативной памяти.
В 3.4 строятся карты устойчивости по структуре полученных оптимальных стратегий.
В четвертой главе (Программный комплекс синтеза, визуализации и оценки устойчивости по структуре стратегий обслуживания линейно рассредоточенной группы стационарных объектов mobile-процессорами) описывается разработанный программный комплекс синтеза оптимальных стратегий обслуживания линейно рассредоточенной группы объектов mobile-процессором (двумя независимыми взаимозаменяемыми mobile-процессорами) . Излагаются назначение и возможности комплекса, его общая структура, пользовательский интерфейс, приводятся копии рабочих экранов программы.
В заключении изложены основные результаты диссертационной работы.
В приложениях приведены: исходный код разработанного программного комплекса; акт внедрения результатов диссертационной работы в Уфимском речном порту; акт внедрения результатов диссертационной работы в учебный процесс Волжской государственной академии водного транспорта; акт внедрения результатов диссертационной работы в учебный процесс факультета Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского.
На защиту выносятся.
Математические модели однофазного однократного обслуживания линейно рассредоточенной группы стационарных объектов mobile-процессорами, адекватно описывающие типовые схемы бункеровок ПДК, а также транспортно-технологическое обслуживание линейно рассредоточенных производственных комплексов и систем муниципального хозяйства.
Экстремальные задачи синтеза оптимальных стратегий управления для математических моделей п. 1.
Алгоритмы синтеза оптимальных стратегий управления в экстремальных задачах (п. 2), обладающие достаточными для решения практических задач значениями скоростных и объемных параметров.
Подход к исследованию устойчивости оптимальных стратегий обслуживания в плоскости параметров математических моделей (п. 1).
Программный комплекс для решения задач управления обслуживанием линейно рассредоточенной группы стационарных объектов mobile-процессорами [53].
Разработанные в диссертации модели и алгоритмы могут быть модифицированы с учетом специфики иных транспортно-технологических процессов и критериев оценки качества их реализации [18, 27]; например, для задач снабжения нефтепродуктами линейных рабочих участков, расположенных в крупномасштабных районах лесозаготовок, а также систем коммунального хозяйства.
