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

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

Синий Андрей Валентинович

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

Специальность 05.13.01 - «Системный анализ, управление и обработка

информации» (технические науки)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Нижний Новгород 2006

Работа выполнена на кафедре Информатики, систем управления и телекоммуникаций Федерального государственного образовательного учреждения высшего профессионального образования «Волжская государственная акадёмия водного транспорта».

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

доктор технических наук, профессор Федосенко Ю.С. Научный консультант:

доктор технических наук, профессор Коган Д.И.

Официальные оппоненты:

доктор технических наук, профессор Ломакина Л.С.

кандидат физико-математических наук, доцент Гришагин В.А.

Ведущая организация: Институт проблем управления

им. В.А.Трапезникова РАН

Защита диссертации состоится « 15 » июня 2006 г. в /3 часов на заседании диссертационного совета Д212.165.05 при Нижегородском государственном техническом университете по адресу: 603600, г. Нижний Новгород, ГСП-41, ул. Минина, 24, корпус 1, аудитория

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

Автореферат разослан « ^ » МАЯ__2006 г.

Ученый секретарь Лу/ /

диссертационного совета к.т.н., доцент д.п Иванов

40675*

Общая характеристика работы

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

К числу таких систем относятся, например, гибкие автоматизированные производства, вычислительные и телекоммуникационные комплексы, а в наибольшей степени - технологические системы транспортного типа. Среди последних особой значимостью указанных обстоятельств отличаются крупномасштабные грузообразующие районы внутреннего водного транспорта (КГР), в которых плавучими дизель-электрическими добывающими комплексами (ПДК) осуществляется массовая русловая добыча нерудных строительных материалов (НСМ). Количество ПДК, задействованных в пределах одного КГР, может достигать 25-30 единиц, а его линейная протяженность колеблется от 200 до 400 километров. Вывоз НСМ из районов русловой добычи, как правило, осуществляется судами и составами грузоподъемностью от 2 до 20 тысяч тонн.

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

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

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

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

Адекватность такого формализма реальным производственным процессам достаточно очевидна; при этом обеспечиваемая им точность моделирования динамического поведения объектов КГР может быть повышена до необходимого уровня за счет выбора шага дискретности пространственно-временных координат и параметров.

рос. национальная библиотека

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

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

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

Применительно к различным задачам управления ресурсами дискретные оптимизационные модели исследовались в работах Д.И. Батищева, A.C. Беленького, В.Н. Буркова, B.C. Гордона, Д.И. Когана, Е.В. Левнера, С.Е. Ловецкого, Т.П. Подчасовой, М.Х. Прилуцкого, И.Х. Сигала, Р.Г. Стронгина, B.C. Танаева, Ю.С. Федосенко, В.В. Шкурбы, Д.Б. Юдина, R. Bellman, R. Conway М. Garey, D. Johnson, R. Karp, A. Land и других авторов.

Ряд динамических моделей оптимизации управления ресурсами объектов внутреннего водного транспорта рассматривался в работах A.B. Куранова, В.И. Савина, A.B. Шеянова, Е.В. Ширяева, а соответствующие программно-технические комплексы поддержки управления были созданы для Камского грузового района и некоторых других воднотранспортных полигонов.

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

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

лежит идеология представления транспортно-технологических процессов как обслуживание группы О,, объектов в линейной рабочей зоне Е тоЫ1е-процессоров, а именно:

- обслуживание всех объектов группы О,, осуществляется одним шо-ЬПе-процессором Р, совершающим в зоне Е круговой рейс;

- обслуживание всех объектов группы Оп осуществляется двумя независимыми взаимозаменяемыми тоЬНе-процессорами Р\ и Р2, поступательно перемещающимися в зоне Е в одном направлении с временным начальным сдвигом относительно друг друга;

- обслуживание всех объектов группы Оп осуществляется двумя независимыми взаимозаменяемыми тоЬПе-процессорами Р\ и Р2, поступательно перемещающимися в зоне Е в противоположных направлениях.

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

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

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

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

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

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

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

1. Разработаны математические модели однофазного однократного обслуживания линейно рассредоточенной группы стационарных объектов тоЬНе-процессорами, адекватно описывающие типовые схемы бункеровок ПДК в крупномасштабных полигонах русловой добычи НСМ.

2. В рамках моделей (п. 1) сформулированы экстремальные задачи синтеза оптимальных стратегий обслуживания.

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

4. Изучены особенности разбиения плоскости параметров математических моделей обслуживания (п. 1) на зоны устойчивости по структуре оптимальных стратегий.

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

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

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

Реализация результатов работы. Работы по теме диссертации выполнялись в соответствии с координационными планами исследований РАН по комплексной программе «Кибернетика», а также Федеральной целевой научно-технической программой "Исследования и разработки по приоритетным направлениям развития науки и техники" (2002-2006 гг.).

Разработанные алгоритмы и программные средства переданы для использования в производственной деятельности Уфимского речного порта, а также внедрены в учебный процесс Волжской государственной академии водного транспорта и на факультете Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского.

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

- VI Международном конгрессе по математическому моделированию (Нижний Новгород, 2003 г.);

- 6-м Международном научно-промышленном форуме «Великие реки

- 2004» (Нижний Новгород, 2004 г.);

- Всероссийской научно-технической конференции, посвященной 60-летию Победы в Великой Отечественной войне и 110-летию изобретения радио A.C. Поповым, «Информационные системы и технологии ИСТ-2005» (Нижний Новгород, 2005 г.);

- 7-м Международном научно-промышленном форуме «Великие реки

- 2005» (Нижний Новгород, 2005 г.);

- Всероссийской научно-практической конференции «Актуальные проблемы использования и развития новых информационных технологий в России» (Нижний Новгород, 2005 г.);

- Научно-методической конференции профессорско-преподавательского состава, аспирантов и специалистов, посвященной 75-летию ВГАВТ, (Нижний Новгород, 2005 г.);

- 10-й Нижегородской сессии молодых ученых (Дзержинск, 2006 г.);

-Секции "Принятие оптимальных решений в прикладных задачах"

конференции "Технологии Microsoft в теории и практике программирования" (Нижний Новгород, 2006 г.);

-Всероссийской научно-технической конференции «Информационные системы и технологии», посвященной 70-летию факультета информационных систем и технологий (ИСТ-2006) (Нижний Новгород, 2006 г.).

Публикации. Основное содержание диссертации отражено в 15 печатных работах [1-15].

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и 4 приложений; содержит 161 страницу текста и 25 рисунков; библиографический список включает 60 источников.

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

В первой главе (Управление обслуживанием линейно рассредоточенной группы стационарных объектов одним тоЬПе-процессором) рассматривается задача оптимизации обслуживания линейно рассредоточенной группы стационарных объектов, расположенных в одномерной рабочей зоне Е тоЬПе-процессора. Строится математическая модель однофазного однократного обслуживания, формулируется экстремальная задача, разрабатывается алгоритм синтеза оптимальной стратегии обслуживания, приводятся пример реализации алгоритма и результаты вычислительных экспериментов.

§ 1.1 посвящен описанию содержательной постановки задачи, построению математической модели Ml; в заключение §1.1 ставится экстремальная задача синтеза однопроцессорного обслуживания линейно рассредоточенной группы объектов.

Основными элементами дискретных моделей процессов обслуживания, рассматриваемых в диссертационной работе в целях синтеза оптимальных управлений, являются «-элементная группа 0„ независимых стационарных объектов и обслуживающие их тоЬПе-процессоры, для которых область расположения группы О,, является рабочей зоной Е.

Зона Е представляет собой направленный отрезок L, в фиксированных точках которого расположены объекты оь о2,...,о„..., о„ группы О,,. Начальную и граничную точки для отрезка L обозначаем соответственно через А и В.

Считаются известными расстояния /ь 1ъ ■■■, Iп {А<1\<]г< ...< /„., < /„ = В) между точками расположения объектов о, (г = 1, и) на отрезке Ь (11 + 12 + /3 +...+ /, +...+ /„ = £). Здесь и везде в работе параметры моделей обслуживания считаются неотрицательными целочисленными величинами.

С каждым объектом о, (/ = 1,и) связана монотонно возрастающая в нестрогом смысле функция индивидуального штрафа если обслуживание объекта тоЬПе-процессором Р\ завершается в момент времени I, то значение (£>,</) есть величина потерь, связанных с обслуживанием объекта

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

\aXt-TJ при/>Ги, [О при /<70Г

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

Процесс обслуживания /-го объекта может быть начат непосредственно в момент подхода к нему тоЫ1е-процессора.

Начальная точка А является стартовой для процессора Ри от которой он сначала поступательно перемещается к граничной точке В отрезка Ь (движение в прямом направлении - рейс А+), а затем, достигнув ее, процессор поступательно возвращается к стартовой точке (движение в обратном направлении - рейс А_). Таким образом, с учетом особенностей расположения стационарных объектов в КГР модель не предполагает возвратных движений как в процессе выполнения рейса Я+, так и в рейсе А..

При реализации кругового рейса (цикл А+Я ) процессор Р\ должен выполнить однократное обслуживание каждого объекта группы Ол. Осуществляемое процессором обслуживание — однофазное, без прерываний. Неоправданные простои процессора запрещены. Затраты времени на обслуживание каждого объекта и перемещения процессора между объектами группы Оп, а также штрафы за задержки в их обслуживании характеризуются известными параметрами и функциональными зависимостями в том числе.

/ = 0 - момент времени, в который начинается движение процессора в рейсе Я+;

у,,.] - затраты времени на поступательное перемещение процессора Р1 между соседними точками расположения объектов при движении в рейсах Я+ и Я. соответственно. При этом > 0 и Уи-\ > 0 для всех / =

1, и, а параметры /0,1 и /1,0 определяют затраты времени на поступательные перемещения процессора Р} между стартовой точкой А и точкой о, соответственно при движениях в рейсах А* и 2_;

г, - продолжительность обслуживания процессором объекта о, (I = 1, п).

Стратегией обслуживания группы объектов Оп будем называть произвольное подмножество V элементов из совокупности /У= (1,2, ..., п}\

объекты о„ где / £ Г, в реализации данной стратегии должны обслуживаться процессором Р} в рейсе Л+, остальные объекты - в рейсе Для определенности полагаем, что объект о„ обслуживается процессором при завершении им рейса Х+, т.е. и е V.

Каждая стратегия V однозначно определяет временные интервалы, в

течение которых обслуживаются объекты. Для объекта о, (/ = 1,и) через 1*,{У) обозначим момент завершения его обслуживания при реализации

I

стратегии V, а для выражения , к + введем обозначение 8,.

*=1 ¿еГ(')

{5,, если ¿еК; 5,+ Л/(/), если / г V. Здесь М(г) - сумма трех величин:

- суммарных затрат времени на перемещение процессора от точки /, к точке В,

- суммарных затрат времени на перемещение процессора от точки В к точке //,

- суммарной продолжительности обслуживания объектов о„ ..., о„. Таким образом,

Величины Л/(/) (/ = 1,«) не зависят от выбираемой стратегии обслуживания, т. е. от того, какие объекты совокупности о,+о,+2, ..., о„.\ обслуживаются в прямом, а какие в обратном рейсе процессора Р]. При реализации стратегии V величина индивидуального штрафа по объекту о, равна <р^*,{У)).

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

7»/|»1>(/;(Г)). (1)

■С »

§ 1.2 посвящен решению экстремальной задачи (1). При этом в п. 1.2.1 выводятся решающие рекуррентные соотношения динамического программирования:

5(1, 0) = (р,(7ол + М( 1)), 5(1,ГО « ç,(ro,i + г,), 5(1, D) = + оо при De {0, г,};

, m . \B{i, D - т, J +<pM (y0t+yi2+...+yIM + D),

B(i+\,D)-min{ (2)

\ЩП)+9М(У„ +-..+V. +-D+M041));

B{n, D) = 5(я-1, D-rn)+<p„(y0 ] +ПЛ + - + Упал + £)- (3)

В соотношении (2) слагаемое 5(/, £>) - минимально возможная величина суммарного штрафа по объектам совокупности ои о, при условии, что в рейсе 1+ суммарное время, потраченное на их обслуживание, равно D.

Аналогично 5(и, D) - минимально возможный суммарный штраф по всем объектам, если при реализации рейса А+ на обслуживание объектов затрачивается время D.

В п. 1.2.2 и п. 1.2.3 излагается алгоритм А1 синтеза оптимальных стратегий обслуживания линейно рассредоточенной группы объектов одним тоЫ1е-процессором и приводится пример технологии расчета.

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

На рис. 1, а кривая 1 отражает зависимость характеристики Гс от размерности группы Оп, полученная для практически значимых интервалов допустимых значений параметров модели yh]J, y,U\, г„ а„ T0l. Для сравнения - кривая 2 отображает зависимость 7"с от п при решении экстремальной задачи (1) переборным алгоритмом на множестве допустимых стратегий обслуживания при идентичных условия проведения вычислительных экспериментов (в этом и во всех рассматриваемых ниже задачах автором использовалась компьютерная рабочая станция с центральным процессором Celeron 1700 Mhz и оперативной памятью объемом 512 Mb).

Зависимость характеристики ДоП от размерности группы Оп представлена на рис. 16.

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

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

tob On и приведены примеры сравнения эффективностей элементарной и оптимальной стратегий обслуживания.

Ä«, Mb

2-

4-

0

3

1-

10 20 а 30 40 0 20 40 60 6 80 100

Рис 1 Примеры результатов вычислительных экспериментов

Элементарная стратегия ЭС1 для модели М1 подразумевает обслуживание всех объектов группы 0„ подряд, по мере выполнения тоЬПе-процессором Р1 рейса Я+. На примерах показано, что снижение суммарного штрафа за счет реализации оптимальной стратегии обслуживания относительно ЭС1 может достигать 100%.

Во второй главе (Управление обслуживанием линейно рассредоточенной группы объектов двумя шоЬНе-процессорами при попутном движении) рассматривается задача оптимизации обслуживания объектов группы Оп в рабочей зоне Е двух независимых взаимозаменяемых тоЫ1е-процессоров РI и Р2, поступательно перемещающихся в одном направлении с временным сдвигом Г относительно друг друга.

§ 2.1 посвящен содержательному описанию задачи, построению математической модели М2Ь а также постановке задачи синтеза оптимальной стратегии обслуживания.

Начальная точка А отрезка Ь является стартовой для процессоров Я, и Р2, от неё в момент времени г = 0 процессор Р\ перемещается к граничной точке В отрезка I (рейс Л,). Процессор Р2 начинает свое аналогичное движение (рейс в момент времени I = Т(Т> О).

Обслуживание каждого объекта совокупности Оп осуществляется только одним из двух процессоров соответственно при реализации рейса Л+ или При этом процессор Р\ выполняет обслуживание части Ок объектов совокупности 0,„ а процессор Р2 обслуживает оставшуюся часть объектов От (к + т = п, Ок II От = Оп).

Затраты времени на перемещение процессоров Р] и Р2 между соседними точками расположения объектов определяются параметрами ,и Гм-и соответственно (дом,, > 0, д2)м,/ >0); Лио,1 и у(1)0,, определяют затра-

ты времени на перемещения процессоров Р\ и Р2 между стартовой точкой А и точкой О). Продолжительность обслуживания объекта о, (/ = 1,л) процессором Р\ (Р2) определяется параметром т-(1), (г(2),).

Стратегией обслуживания группы объектов Оп будем называть произвольное подмножество К элементов из совокупности N = {1, 2, ..., и};

объекты о„ где i 6 V, в реализации данной стратегии должны обслуживаться процессором Р\ в рейсе Л+, остальные объекты - процессором Р2 в рейсе А_.

Для объекта о, (г = 1 ,п) через г*,(Г) обозначим момент завершения его обслуживания при реализации стратегии V; в этом случае величина индивидуального штрафа по объекту о, определяется как ?>,(/*,( V)).

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

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

5(1, г(1)1, 0)=^(Г(1)о,1+П1)1). 5(1, 0, 7(2)0= <р1{г<гу>,\+Т+т(2)1)\ 5(1, А, А)=<», при Ай{о, г(1)1} или А<г{0, г(2)|};

5(/, А. А) = min

w, + А)+B(i -1, А - r(D-'A).

/-1

<Р, (S rmi-Kj + T + D1) + B(i-l,Dt,Dl- тт,).

В п. 2.2.2. излагается алгоритм A2t синтеза оптимальных стратегий обслуживания, а в п. 2.2.3 приводится пример его реализации.

В § 2.3 рассматривается имеющая отдельное практическое значение модель М22 синтеза оптимальной стратегии обслуживания для случая двух идентичных тоЬПе-процессоров, характеризующегося дополнительными условиями Г(1), = Г(2)/ = т„ У(])1-1,, ~ У(2)1-1,/ = У,-),, и выводимыми в п. 2.3.1 решающими соотношениями динамического программирования:

В( 1,0) = ^(уол + *\ + Т), 5(1, г,) = <Р\{уо,\ + г,);

5(l,D) = + oo при Di {0, Ti};

/.о

ВО>,0)+9м(±Г + +О).

В п. 2.3.2 и п. 2.3.3 излагается алгоритм А22 синтеза оптимальных стратегий обслуживания для данного случая и приводится пример технологии расчета. В п. 2.3.4 приводятся условия и результаты вычислительных экспериментов, позволивших установить технические характеристики алгоритмов А2) и А22.

На рис. 2 кривые 1 и 2 отражают зависимости средней продолжительности синтеза оптимальной стратегии обслуживания от размерности группы Оп, полученные соответственно для случаев идентичных и взаимозаменяемых обслуживающих процессоров. Для сравнения - кривая 3 отображает зависимость Тс от п при решении экстремальной задачи (1) переборным алгоритмом на множестве допустимых стратегий обслуживания.

Результаты оценки среднего значения требуемого объема оперативной памяти Доп в зависимости от размерности группы Оп представлены на рис. 3 соответственно для идентичных - а и взаимозаменяемых - б то-ЬПе-процессоров.

Для моделей М21 и М22 последовательность, при которой объект совокупности О,, обслуживается первым подошедшим к нему процессором (Р\ или Р2), называем элементарной стратегией ЭС2. На примерах показано, что снижение суммарного штрафа за счет реализации оптимальной стратегии обслуживания относительно ЭС2 может достигать 100%.

8а Т"с

п

0"

10 20 30 40 50

Рис 2 Зависимость продолжительности синтеза оптимальной стратегии от размерности группы объектов Оа

А„л, МЬ

^ДмнМЬ

3-

60

0Ц 20 40 а 60 80 ' 1(ЮГ 0 20 40

60 80

п

б

Рис 3 Зависимость Л», от размерности группы объектов 0„

В § 2.4 введено понятие устойчивости по структуре оптимальной стратегии обслуживания линейно рассредоточенной группы объектов Оп и приведены примеры конфигураций карт устойчивости в плоскости параметров Тг\ и Тг2 - запаздывания моментов /П| и /п2 поступления процессоров Р\ и Р2 в рабочую зону соответственно (?п1 = Тги 1п2 = Т + Тг2).

В третьей главе (Управление обслуживанием линейно рассредоточенной группы объектов двумя тоЬПе-процессорами при встречном движении) рассматривается задача оптимизации обслуживания объектов группы Оп в рабочей зоне Е двух независимых взаимозаменяемых тоЫ1е-процессоров Р, и Р2, поступательно перемещающихся во встречных направлениях с временным сдвигом Т относительно друг друга.

§ 3.1 посвящен построению математической модели обслуживания МЗ при условии: процессор Р\ перемещается в направлении от стартовой точки А к граничной точке В отрезка £ (рейс Я+), а процессор Р2 - в противоположном направлении (от стартовой точки В отрезка Ь к граничной точке А - рейс Л-). В модели МЗ введены обозначения:

Ум, - затраты времени на перемещение процессора Р, между соседними точками расположения объектов о, и о,+1 (/ = 1,и-1), у0,\ ~ затраты времени на перемещение Р\ от стартовой точки А к точке расположения объекта 0\,

- затраты времени на перемещение процессора Р2 между точками расположения объектов о,+1 и о, (/ = 1,и-1), /„+! „ - затраты времени на перемещение процессора Р2 из стартовой точки В к точке расположения объекта о„.

Смысл параметров г(])„ г(2), такой же, как и в модели М2.

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

С учетом ранее введенных обозначений V, <*,(Р), /р,{1*,(У)), N задача синтеза оптимальной стратегии однократного однофазного обслуживания группы объектов Оп в рабочей зоне Е процессоров Р/ и Рг при встречном движении последних записывается в виде выражения (1).

Для решения экстремальной задачи (1) в п. 3.2.1 выводятся приводимые ниже решающие рекуррентные соотношения динамического программирования:

В( 1,1(1)1, А) = «^(Го,.+*(„,), В( 1,0, Д>) = срА £уЫ1 +Г(2)1+£>2);

(-1

в{ 1, а,Д.) = 00при ай{0, т(1}1^п2е{0,...,£тт };

,-г

В(1, Д, ) = тт

<р,СЕгм, + Д)+в(г -1, д - г(1)„ д),

/-1

(2>,., , + г, 2 + Д) + 5(/ -1, Д, Д + г(2„).

В п. 3.2.2 рассматривается алгоритм АЗ синтеза оптимальных стратегий обслуживания объектов группы 0„, а в п. 3.2.3 приводится пример технологии его реализации.

В п. 3.2.4 представлены результаты вычислительных экспериментов, целью которых являлось определение технических характеристик Тс и Аоп алгоритма АЗ.

На рис. 4, а кривая 1 отражает зависимость характеристики Тс от размерности группы Оп. Для сравнения - кривая 2 отображает зависимость Тс от п при решении экстремальной задачи (1) переборным алгоритмом на множестве допустимых стратегий обслуживания.

Результаты оценки среднего значения требуемого объема оперативной памяти Доп в зависимости от размерности группы Оп представлены на рис. 4, 6.

Для модели МЗ элементарная стратегия ЭСЗ определяется так же, как и для моделей М2Ь М22, т.е. объект совокупности Оп обслуживается первым подошедшим к нему тоЬНе-процессором Рх или Р2. На примерах продемонстрированы типичные результаты сравнения оптимальной и элементарной стратегий обслуживания.

В §3.3 приводятся примеры конфигураций карт устойчивости по структуре оптимальных стратегий. Так, для и = 10 пример карты устойчивости воспроизведен на рис. 5.

Рис 5 Карта устойчивости по структуре оптимальной стратегии п = 10

Структуры оптимальных стратегий и относительное значение 50 площади области устойчивости по структуре в плоскости параметров Тг\ и Тг2 представлены в таблице.

Характеристики карты устойчивости по структуре

Номер стратегии Стратегия 50, %

1 . 1 1 1 1 1 0 0 0 0 1 , 54,55

2 11 11000000 ■ 45.45 '

Продолжительность расчета карты устойчивости, с | 43,615

В четвертой главе (Программный комплекс синтеза, визуализации и оценки устойчивости по структуре стратегий обслуживания линейно рассредоточенной группы стационарных объектов тоЬНе-процессорами) описывается разработанный программный комплекс синтеза оптимальных стратегий обслуживания линейно рассредоточенной группы стационарных объектов тоЬПе-процессорами. Программный комплекс оформлен как система двух независимых внешних приложений: модуль «Бункеровка» [14]

служит непосредственно для синтеза оптимальных стратегий, модуль «Анимация» (ftp://aqua.sci-nnov.ru/programs/aninie.exe) предназначен для анимационного представления оптимальных стратегий обслуживания линейно рассредоточенной группы объектов.

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

В приложении приведены:

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

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

Основные результаты и выводы

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

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

При решении указанной задачи получены следующие научно-технические результаты.

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

2. Сформулированы экстремальные задачи синтеза оптимальных стратегий обслуживания линейно рассредоточенной группы объектов тоЬПе-процессорами.

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

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

5. Разработанные алгоритмы и программные средства внедрены в Уфимском речном порту и используются в учебном процессе Волжской государственной академии водного транспорта и на факультете Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского.

По исследованной проблеме автором опубликовано 15 работ [1-15], в которых приведены основные научные результаты диссертации.

1. Коган, Д.И. Синтез оптимальной стратегии обслуживания группы стационарных объектов в рабочей зоне шоЬПе-процессора / Д.И. Коган, A.B. Синий, Ю.С. Федосенко // Транспорт - XXI век: сб. матер, научно-тех. конф. профес.-препод. состава, аспирантов и специалистов ВГАВТ, Н.Новгород, 2003 г. - Н.Новгород: Изд-во ФГОУ ВПО ВГАВТ, 2003. - С. 52-56.

2. Синий, A.B. Задача и алгоритм построения оперативного плана обслуживания группы стационарных объектов mobile-процсссором/ A.B. Синий // Проблемы повышения эффективности функционирования и развития транспортного Поволжья: сб. матер, научно-практич. конф., Н.Новгород, 2003 г. - Н.Новгород: Изд-во ФГОУ ВПО ВГАВТ, 2003. -Ч. 1.-С. 160-163.

3. Коган, Д.И. Задачи оптимального обслуживания группы стационарных объектов, расположенных в одномерной зоне / Д.И. Коган, A.B. Синий, Ю.С. Федосенко // Вестник ВГАВТ. Межвузовская серия: Моделирование и оптимизация сложных систем. - Н.Новгород: Изд-во ФГОУ ВПО ВГАВТ. - 2004. - Вып. 9. - С. 27-34.

4. Siniy, A.V. The models and technologies for schedule synthesis of single-stage stationary objects processing by mobile-processors / A.V. Siniy, Yu.S. Fedosenko.// VI International congress on mathematical modeling: book of abstracts,. N.Novgorod, September 20-26, 2004 y. - N.Novgorod: UNN, 2004.-P. 124.

5. Синий, A.B. Базовые математические модели снабжения топливом земснарядов в крупномасштабных районах русловой добычи нерудных строительных материалов / A.B. Синий // Международный научно-промышленный форум «Великие реки - 2004»: генер. доклады, тез. докладов, Н.Новгород, 18-21 мая 2004 г. - Н. Новгород: ННГАСУ, 2004. С. 468-470.

6. Синий, A.B. Оптимизация однофазного обслуживания пространственно рассредоточенной группы объектов двумя mobile-процессорами / A.B. Синий // Информационные системы и технологии ИСТ-2005: тез. докл. Всерос. научно-техн. конф., Н. Новгород, 22 апреля 2005 г. - Н. Новгород: НГТУ, 2005. - С. 132-133.

7. Синий, A.B. Система оперативного планирования и учета снабжения топливом плавучих добычных установок на базе платформы «1С-

Предприятие» / A.B. Синий // Международный научно-промышленный форум «Великие реки - 2005»: генер. доклады, тез. докладов, Н.Новгород, 17-20 мая 2004 г. - Н.Новгород: ННГАСУ, 2005. - С. 294-295.

8. Синий, A.B. Оптимизация обслуживания линейно рассредоточенной группы стационарных объектов двумя тоЬПе-процессорами при встречном движении / A.B. Синий // Актуальные проблемы использования и развития новых информационных технологий в России: сб. научных трудов, Н.Новгород, 3 ноября 2005 г. - Н.Новгород: НГТУ, 2005. - С. 101-103.

9. Синий, A.B. Синтез оптимальной стратегии обслуживания группы стационарных объектов двумя тоЬПе-процессорами / A.B. Синий // Вестник ВГАВТ. Межвузовская серия: Моделирование и оптимизация сложных систем. - Н.Новгород: Изд-во ФГОУ ВПО ВГАВТ. - 2005. - С. 175-182.

10. Синий, A.B. Оптимизация и устойчивость стратегий обслуживания группы стационарных объектов в линейной рабочей зоне mobile-процессоров / A.B. Синий // Информационные системы и технологии ИСТ-2006: тез. докл. Междунар. научно-техн. конф., Н.Новгород, 21 апреля 2006 г. - Н. Новгород: НГТУ, 2006. - С. 164.

11. Синий, A.B. Синтез оптимальных оперативных планов обслуживания группы пространственно рассредоточенных объектов на базе платформы «IC-Предприятие» / A.B. Синий // Конференция посвященная 75-летию ВГАВТ: сб. матер, научно-метод. конф. проф.-препод. состава, аспирантов и специалистов, Н.Новгород, 8-9 декабря 2005 г. - Н.Новгород: Изд-во ФГОУ ВПО ВГАВТ, 2006. - Ч. 2. - С. 61-63.

12. Синий, A.B. Модель и алгоритм синтеза оптимального расписания однофазного обслуживания группы пространственно рассредоточенных стационарных объектов двумя тоЬПе-процессорами / A.B. Синий // 11-я Нижегородская сессия молодых ученых (технические науки): сб. тезис, докладов, 12-16 февраля 2005 г. - Н.Новгород, 2006. - С. 40-42.

13. Синий, A.B. Математические модели и алгоритмы синтеза оптимальных расписаний бункеровки добывающих комплексов в крупномасштабных русловых районах / A.B. Синий, Ю.С. Федосенко // Технологии Microsoft в теории и практике программирования: сб. материалов конф., Н.Новгород, 21-22 марта 2006 г. - Н.Новгород: Изд-во Нижегородского госуниверситета, 2006. - С. 276-279.

14. Синий, A.B. Управление обслуживанием линейно рассредоточенной группы стационарных объектов тоЬПе-процессорами «Бункеровка 1.0» / A.B. Синий // Инновации в науке и образовании / Телеграф отраслевого фонда алгоритмов и программ. - Государственный координационный центр информационных технологий Минобрнауки РФ. - 2006. - Март. - №3(14).

15. Свидетельство №2006611178 РФ. Управление обслуживанием линейно рассредоточенной группы стационарных объектов процессорами транспортного типа / A.B. Синий, заявитель и правообладатель. - Заявл. 26.02.06; зарег. 31.03.06. -Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, Реестр программ для ЭВМ.

itoOGA

ЛО €>75*

Щ10 6 7 5

г

I

Формат бумаги 60x84 */1б. Бумага писчая. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Заказ 327. Тираж 120.

Отпечатано в типографии

издательско-полиграфического комплекса ФГОУ ВПО ВГАВТ_

603950, Нижний Новгород, ул. Нестерова, 5 а

ВВЕДЕНИЕ.

ГЛАВА 1. УПРАВЛЕНИЕ ОБСЛУЖИВАНИЕМ ЛИНЕЙНО РАССРЕДОТОЧЕННОЙ

ГРУППЫ СТАЦИОНАРНЫХ ОБЪЕКТОВ ОДНИМ МОВ1ЬЕ-ПРОЦЕССОРОМ.

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

1.1.1. Содержательная постановка задачи.

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

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

§ 1.2. Синтез оптимальной стратегии на основе идеологии динамического программирования.

1.2.1. Построение соотношений динамического программирования.

1.2.2. Описание алгоритма синтеза оптимальной стратегии обслуживания.

1.2.3. Пример реализации технологии расчета.

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

1.2.5. Сравнение оптимальных и элементарных стратегией обслуживания.

ВЫВОДЫ ПО ГЛАВЕ

ГЛАВА 2. УПРАВЛЕНИЕ ОБСЛУЖИВАНИЕМ ЛИНЕЙНО РАССРЕДОТОЧЕННОЙ ГРУППЫ

ОБЪЕКТОВ ДВУМЯ МОВ1ЬЕ-ПРОЦЕССОРАМИ ПРИ ПОПУТНОМ ДВИЖЕНИИ.

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

2.1.1. Содержательная постановка задачи.

2.1.2. Математическая модель обслуживания.

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

§ 2.2. Синтез оптимальной стратегии обслуживания на основе идеологии динамического программирования.

2.2.1. Построение соотношений динамического программирования.46 (

2.2.2. Описание алгоритма синтеза оптимальной стратегии обслуживания.

2.2.3. Пример реализации технологии расчета.

§ 2.3. Синтез оптимальной стратегии обслуживания в случае идентичных тоЬПе-процессоров.

2.3.1. Построение соотношений динамического программирования.

2.3.2. Описание алгоритма синтеза оптимальной стратегии обслуживания.

9 2.3.3. Пример технологии расчета.

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

§ 2.4. Оценка устойчивости стратегий по структуре.

2.4.1. Понятие устойчивости стратегий по структуре.

2.4.2. Построение карт устойчивости по структуре.

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

ВЫВОДЫ ПО ГЛАВЕ 2.

ГЛАВА 3. УПРАВЛЕНИЕ ОБСЛУЖИВАНИЕМ ЛИНЕЙНО РАССРЕДОТОЧЕННОЙ ГРУППЫ

ОБЪЕКТОВ ДВУМЯ МОВ1ЬЕ-ПРОЦЕССОРАМИ ПРИ ВСТРЕЧНОМ ДВИЖЕНИИ.

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

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

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

§ 3.2. Синтез оптимальной стратегии обслуживания.

3.2.1. Построение соотношений динамического программирования.

3.2.2. Описание алгоритма синтеза оптимальной стратегии обслуживания.

3.2.3. Пример реализации технологии расчета.

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

§ 3.3. Оценка устойчивости стратегий по структуре.

3.3.1. Построение карт устойчивости по структуре.

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

Выводы по главе 3.

ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС СИНТЕЗА, ВИЗУАЛИЗАЦИИ И ОЦЕНКИ

УСТОЙЧИВОСТИ ПО СТРУКТУРЕ СТРАТЕГИЙ ОБСЛУЖИВАНИЯ ЛИНЕЙНО РАССРЕДОТОЧЕННОЙ ГРУППЫ СТАЦИОНАРНЫХ ОБЪЕКТОВ

МОВ1ЬЕ-ПРОЦЕССОРАМИ.

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

§ 4.2. Структура и интерфейс программного модуля «Бункеровка».

§ 4.3. Программный модуль анимации стратегий обслуживания.

Выводы по главе 4.

Русловая добыча нерудных строительных материалов (НСМ), осуществляемая плавучими добывающими комплексами, является одной из основных видов деятельности предприятий внутреннего водного транспорта РФ [13] .

Промышленно значимые полигоны русловой добычи НСМ обычно простираются на несколько сот километров и в период навигации на них работает до 20-30 единиц добывающих комплексов [10]. Объемы добычи НСМ на таких полигонах бассейнов судоходных систем РФ измеряются десятками миллионов тонн за навигацию. Примером таких полигонов является Камский грузовой район {КГР) [14, 55]: протяженность КГР достигает 400 км и он простирается от устья реки Камы до устья реки Белой (Рис. 1). Е

КАЗАНЬ н^Чепь ,

Рыбная Слобода v ^

• CD эь . р.Каиа

Чистополь

Рис.1. Камский грузовой район

На рис.1. использованы следующие пиктограммы: т, CZ3, - добывающие комплексы различных типов, в том числе, типа «Прага», типа «Эжекторный» и т.д.;

C£E3Q, c^zdczd - грузовые суда и составы, обеспечивающие вывоз НСМ к потребителям приволжского региона.

НСМ поставляется различным предприятиям, осуществляющим выпуск железобетонных изделий для промышленного и гражданского строительства, реконструкции существующих и прокладки новых автомагистралей, мостового строительства и т.п. [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, б], В.Н. Бурков [8], Д.И. Когана и Ю.С. Федосенко [29 - 34], Т.П. Подчасовой [44], М.Х. Прилуцкого [45], И.Х. Сигала [37] . Ряд моделей управления обслуживанием потоков объектов транспортного типа в системе независимых процессоров исследовался в работах

А.В. Шеянова [59, 60], А.В. Куранова [39, 40]. Частной задаче бункеровки группы объектов посвящена статья Д.И. Когана, Ю.С. Федосенко, А.В. Ершова [19].

Как следует из вышеупомянутых работ, практическая применимость алгоритмов синтеза оптимальных решений в задачах управления ресурсами систем транспортного типа [23, 26] непосредственно определяется вычислительной сложностью решающих алгоритмов [1, 4, 9] и, как следствие, допускаемой рабочим регламентом продолжительностью нахождения оптимизированного решения.

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

Цельюработы является разработка моделей, алгоритмов, а также программных средств для решения задач синтеза оптимальных стратегий снабжения дизельным топливом линейно рассредоточенной в крупномасштабном грузообразующем районе группы плавучих добывающих комплексов для совокупности © всех известных технологических схем бункеровок. В основе моделирования последних лежит идеология представления транспортно-технологических процессов как обслуживание линейно рассредоточенной группы 0п стационарных объектов в линейной рабочей зоне S тоЫ1е-процессоров, а именно:

- обслуживание всех объектов группы 0п осуществляется одним тоЫ1е-процессором Р, совершающим в зоне Е круговой рейс;

- обслуживание всех объектов группы 0п осуществляется двумя независимыми взаимозаменяемыми mobile-процессорами Pi и Р2, поступательно перемещающимися в г зоне Е в одном направлении с временным начальным сдвигом относительно друг друга;

- обслуживание всех объектов группы 0п осуществляется двумя независимыми взаимозаменяемыми mobile-процессорами Pi и Р2, поступательно перемещающимися в зоне 2 в противоположных направлениях.

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

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

- разработка для типовых технологических схем 0 адекватных математических моделей обслуживания процессорами транспортного типа (тоЫ1е-процессорами линейно рассредоточенной группы стационарных объектов);

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

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

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

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

1. Разработаны базовые математические модели однофазного однократного обслуживания линейно рассредоточенной группы стационарных объектов mobile-процессорами, адекватно описывающие типовые схемы бункеровок ПДК в крупномасштабных полигонах русловой добычи НСМ.

2. В рамках моделей (п. 1) сформулированы экстремальные задачи синтеза оптимальных стратегий управления обслуживанием.

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

4. Изучены особенности разбиения плоскости параметров математических моделей обслуживания . (п. 1) на зоны устойчивости по структуре оптимальных стратегий.

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

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

- VI Международном конгрессе по математическому моделированию (г. Нижний Новгород, 2003 г.);

- б-м Международном научно-промышленном форуме «Великие реки 2004» (г. Нижний Новгород, 2004 г.);

- Всероссийской научно-технической конференции «Информационные системы и технологии ИСТ-2005», посвященной 60-летию Победы в Великой Отечественной войне и 110-летию изобретения радио А. С. Поповым (г. Нижний Новгород, 2005 г.);

- 7-м Международном научно-промышленном форуме «Великие реки 2005» (г. Нижний Новгород, 2005 г.);

- Всероссийской научно-практической конференции «Актуальные проблемы использования и развития новых информационных технологий в России» (г. Нижний Новгород, 2005 г.);

- Научно-методической конференции профессорско-преподавательского состава, аспирантов и специалистов, посвященной 75-летию ВГАВТ (г. Нижний Новгород, 2005 г.) ;

- 10-й Нижегородской сессии молодых ученых (г. Дзержинск, 2006 г.)

- Всероссийской научно-технической конференции «Информационные системы и технологии», посвященной 70-летию факультета информационных систем и технологий (ИСТ-2006) (г. Нижний Новгород, 2006 г.);

- Секции "Принятие оптимальных решений в прикладных задачах" конференции "Технологии Microsoft в теории и практике программирования" (Нижний Новгород, 2006 г.).

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и 4 приложений; содержит 161 страницу текста, 25 рисунков и список литературы из 60 наименований.

Выводы по главе 4

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

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

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

Заключение

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

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

Получены следующие научно-технические результаты.

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

2. Сформулированы экстремальные задачи синтеза оптимальных стратегий управления для математических моделей однократного однофазного обслуживания линейно рассредоточенной группы объектов тоЬНе-процессорами.

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

4. Создан программный комплекс для решения задач оптимизации управления однофазным однократным обслуживанием тоЫ1е-процессорами линейно рассредоточенной группы стационарных объектов.

5. Разработанные алгоритмы и программные средства внедрены в системах управления транспортно-технологическими процессами в Уфимском речном порту, а также используются в учебном процессе Волжской государственной академии водного транспорта и на факультете Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского.

1. Garey, M.R. Computers and 1.tractability. The Guide to the Theory of NP-Completeness/M.R. Garey, D.S. Johnson. -W.H. Freeman, 197 9.

2. Алексеев, О.Г. Комплексное применение методов дискретной оптимизации / О.Г. Алексеев. М.: Наука, 1987. - 274 с.

3. Батищев, Д.И. Задачи и методы векторной оптимизации: уч. пос. / Д.И. Батищев. Горький: Изд-во ГГУ, 1979. -92 с.

4. Батищев, Д.И. Вычислительная сложность экстремальных задач переборного типа: уч. пос. / Д.И. Батищев, Д.И. Коган. Н.Новгород: Изд-во Нижегородского ун-та, 1994. - 114 с.

5. Беленький, А.С. Применение моделей и методов теории расписаний в задачах оптимального планирования на грузовом транспорте/А.С. Беленький, Е.В. Левнер// Автоматика и телемеханика. 1989. - №2. - С. 3-77.

6. Беленький, А.С. Исследование операций в транспортных системах: идеи и схемы методов оптимизации планирования / А.С. Беленький. М.: Мир, 1992. - 582 с.

7. Беллман, Р. Процессы регулирования с адаптацией / Р. Беллман. М.: Наука, 1964. - 359 с.

8. Бурков, В.Н. Эвристический подход к решению динамических задач распределения ресурсов / В.Н. Бурков, С.Е. Ловецкий // Автоматика и телемеханика. 1966. - №5. - С. 89-90.

9. Бурков, В.Н. Методы решения экстремальных задач комбинаторного типа (обзор) / В.Н. Бурков, С.Е. Ловецкий // Автоматика и телемеханика. 1968. - №11. - С. 68-93.

10. Бутов, А.С. Планирование работы флота и портов /

11. A.С. Бутов, В.А. Легостаев. М. : Транспорт, 1988. -175 с.

12. Васильева, Е.М. Оптимизация планирования и управления транспортными системами / Е.М.Васильева, Р.В. Игудин,

13. B.Н. Лившиц. М.: Транспорт, 1987. - 208 с.12 . Войчинский, A.M. Гибкие автоматизированныепроизводства / A.M. Войчинский, Н.И. Диденко, В.П. Лузин. М.: Радио и связь, 1987.- 272 с.

14. Галабурда, В.Г. Оптимальное планирование грузопотоков / В.Г. Галабурда. М.: Транспорт, 1985. - 256 с.

15. Гене, Г.В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы / Г.В. Гене,

16. Е.В. Левнер // Изв. АН СССР. Техническая кибернетика. -1979. №6. - С. 9-20.

17. Гордон, B.C. Минимизация стоимости, связанной с переменными директивными сроками, в задаче теории расписаний с одним прибором/В.С. Гордон//Автоматика и телемеханика. 1992. - N2. - С. 105-112.

18. Захаров, В.Н. Оперативное управление работой грузовых судов речного флота на базе АСУ "Пароходство" / В.Н. Захаров, В.М. Федюшин. Горький: ГИИВТ, 1989.- 76 с.

19. Игудин, Р.В. Задачи теории расписаний на транспорте и алгоритмы их решения / Р.В. Игудин // Экономика и математические методы. 1975. - №3. - С. 4 91-4 99.

20. Калачев, В.Н. Задачи планирования в гибких автоматизированных системах / В.Н. Калачев, В.Е. Кривоноженко, Б.В. Немчинов // 1 АиТ. 1995. - К26. -С.155-164.

21. Кнут, Д. Искусство программирования на ЭВМ. В 3-х т. / Д. Кнут: Пер. англ./Под ред. К.И. Бабенко и B.C. Штаркмана.- М.:Мир, 1976 735 с.

22. Приближенные алгоритмы в теории расписаний / М.Я.Ковалев и др.. Минск, 1989.

23. Коган, Д.И. Дискретные многокритериальные задачи распределительного типа / Д.И. Коган : уч.пос. Н.Новгород: Изд-во Нижегородского ун-та, 1991. 82 с.

24. Коган, Д.И. Задача диспетчеризации: анализ вычислительной сложности и полиномиально разрешимые подклассы. Дискретная математика / Д.И. Коган, Ю.С. Федосенко // РАН. 1996. - Т.8. - №3.

25. Королёв, С.А Опыт реализации алгоритмов динамического программирования для проектирования расписаний однопроцессорного обслуживания бинарного потока заявок / С.А. Королев, Ю.С. Федосенко, А.В. Шеянов //

26. Математическое обеспечение информационных технологий в технике, образовании, медицине: сб. тез. докл. Всероссийского совещания-семинара. Воронеж: Изд-во ВГТУ, 1996. - 4.1.

27. Конвей, Р.В. Теория расписаний / Р.В. Конвей, B.JI. Максвелл, JI.B. Миллер. М. : Наука, 1975. - 360 с.

28. Лехан, Ю.К. Диспетчерское управление работой флота / Ю.К Лехан. : Транспорт, 197 6. - 152 с.

29. Малышкин, А.Г. Организация и планирование работы речного флота/ А.Г. Малышкин. М.: Транспорт, 1985, -215 с.43 . Михалевич, B.C. Экономико-математическое моделирование деятельности флота и портов / B.C. Михалевич. М.: Транспорт, 1986, - 287 с.

30. Подчасова, Т.П. Эвристические методы календарного планирования/ Подчасова, Т.П. и др.. Киев: Технл.ка, 1980. - 126 с.

31. Прилуцкий, М.Х. Детерминированная модель и алгоритм определения оптимальной очередности обработки судов с учетом времени их прибытия / М.Х. Прилуцкий, Ю.С. Федосенко // Тр. ин-та инж. водного транспорта. -Н.Новгород: НИИВТ. 1991. - Вып.257. - С. 55-72.

32. Прокофьев, В.А. Информационные технологии управления перевозками / В.А. Прокофьев. Санкт-Петербург: ГМА им. адм. С.О.Макарова, 1999. - 72с.

33. Пьяных, С.М. Экономико-математические методы оптимального планирования работы речного транспорта / С.М. Пьяных. М.: Транспорт, 1988. - 253 с.

34. Резер, С.М. Математические методы оптимального планирования в траспортных системах / С.М. Резер, С.Е. Ловецкий, И.И. Меламед // Итоги науки и техники. Сер. Организация управления транспортом. М. : ВИНИТИ. -1990. - Т.9. - 172с.

35. Савин, В.И. Определение оптимальной очередности обработки судов / В.И. Савин. Горький: Волго-Вятское книжное изд-во, 1965. - 30 с.

36. Свидетельство № 2006611178 РФ. Управление обслуживанием линейно рассредоточенной группы стационарных объектов процессорами транспортного типа /

37. A.В. Синий, заявитель и правообладатель. Заявл.: 26.02.06; зарег.: 31.03.06. - Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, Реестр программ для ЭВМ.

38. Танаев, B.C. Теория расписаний. Одностадийные системы / B.C. Танаев, B.C. Гордон, Я.М. Шафранский. -М.: Наука, 1984. 384 с.

39. Танаев, B.C. Введение в теорию расписаний /

40. B.C. Танаев, В.В. Шкурба.- М.: Наука, 1975. 256 с

41. Федосенко, Ю.С. Модели и алгоритмы управления ресурсами в однофазных системах обслуживания транспортного типа: автореферат дис. д-тр техн. наук: 05.13.01 / Федосенко Юрий Семенович. Нижний Новгород: ВГАВТ, 1995. - С. 30.

42. Федосенко, Ю.С. Модели теории расписаний в задачах оперативного планирования для АСУ крупномасштабного грузового района/ Ю.С. Федосенко // Всероссийская научно-техническая конференция "ТРАНСКОМ-94": Сб. тез. докл. - СПб., 1994. - С. 25-26.

43. Шеянов, А.В. Влияние времени передвижения процессора на оптимальное расстояние в задаче обслуживания мультипотока движущимся процессором / А.В.Шеянов // Труды ВГАВТ. Н.Новгород: Изд-во ВГАВТ. - 1998. - Вып.275. -4.2.

44. Шеянов, А.В. Моделирование и оптимизация управления обслуживанием детерминированных потоков объектов перемещаемым процессором: дис. канд. техн. наук: 05.13.01; защищена: 17.11.98 / Шеянов Анатолий Владимирович. Н.Новгород, 1998 - 125 с.