Моделирование и оптимизация управления обслуживанием детерминированных потоков объектов перемещаемым процессором тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Шеянов, Анатолий Владимирович

• Шеянов, Анатолий Владимирович
• кандидат технических наук
• 1998

Оглавление диссертации кандидат технических наук Шеянов, Анатолий Владимирович

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ПРИЛОЖЕНИЯ

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

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

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

Введение диссертации (часть автореферата) на тему «Моделирование и оптимизация управления обслуживанием детерминированных потоков объектов перемещаемым процессором»

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

Таблица 1.

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

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

10 б, 048 Секунда

15 25,225 Сутки

17 18,798 Год

20 128578 Год

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- Х-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1997).

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

- 2-й международной научно-технической конференции "Интерактивные системы: Проблемы человеко-компьютерного взаимодействия" (Ульяновск, 1997).

- 3-й международной конференции "Дискретные модели в теории управляющих систем" (Москва-Красновидово, 1998) .

Публикации.

По теме диссертации опубликовано 15 работ, в которых отражено ее основное содержание. Автореферат

диссертации в формате PostScript доступен в сети Интернет по адресу

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

Структура и объем работы.

Диссертация состоит из введения, пяти глав и заключения. Она содержит 125 страниц текста, 2 6 рисунков, список литературы из 52 наименований и 3 приложения .

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

В первой главе (Потоковые задачи обслуживания: обзор литературы и проблематика) проведен обзор проблематики в области решения потоковых задач обслуживания. Особое внимание уделено вопросу о NP-трудности данного класса задач. В связи с этим рассмотрены возможные подходы к их решению.

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

В §1.2 рассматривается вопрос трудоемкости задачи синтеза оптимального расписания обслуживания объектов потока как экстремальной задачи переборного типа. В связи с практической нереализуемостью ее решения полным перебором для значимых в приложениях значений размерностей потоков обсуждается проблема построения алгоритмов, решающих эти задачи за приемлемое время. Указывается, что рассматриваемый тип задач относится к классу ЫР-трудных и, таким образом, построение полиномиального алгоритма не представляется возможным.

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

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

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

§2.1 посвящен построению математической модели обслуживания бинарного потока объектов. В п.2.1.1 излагается содержательная постановка задачи и приводятся ее возможные интерпретации, в п.2.1.2 формализуется математическая модель, а в п.2.1.3 ставится экстремальная задача синтеза оптимального расписания обслуживания бинарного потока объектов.

В §2.2 показывается ЫР-трудность задачи и делается вывод о невозможности построения "быстрого" решающего алгоритма, время отработки которого полиномиально зависит от размерности задачи.

Применению метода динамического программирования к решению задачи посвящен §2.3. В п.2.3.1 строятся базовые рекуррентные соотношения ДП и излагается последовательность нахождения оптимального расписания с использованием построенных соотношений. В п.2.3.2 рассматриваются возможные способы модификации алгоритма с целью уменьшения времени решения и требуемого в процессе решения объема оперативной памяти. Описание реализованной модификации алгоритма динамического программирования (алгоритм ДП с одновременной разметкой и вычислением рекурсивной функции) дано в п.2.3.3. Для иллюстрации технологии расчета по описанному алгоритму в п.2.3.4 приведен пример синтеза оптимального расписания обслуживания для тестового примера. В п.2.3.5 приводятся оценки быстродействия реализованного алгоритма по результатам тестирования (таблицы и графики).

В §2.4 рассматривается применение метода ветвей и границ к решению задачи. Соответствующий алгоритм излагается в п.2.4.1. В п.2.4.2 рассматриваются возможные варианты реализации алгоритма, в том числе различные виды верхних и нижних оценок; приводится их сравнение по результатам тестирования. Для иллюстрации технологии расчета п.2.4.3 содержит пример синтеза оптимального расписания по построенному алгоритму на тестовом примере. В п.2.4.4 приводятся результаты тестирования быстродействия реализованного алгоритма. Сравнение с результатами тестирования быстродействия алгоритма ДП показывает преимущество алгоритма ВГ.

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

§3.1 посвящен построению математической модели обслуживания мультипотока объектов. В п.3.1.1 излагается содержательная постановка задачи, в п.3.1.2 формулируется математическая модель, а в п.3.1.3 ставится

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

В §3.2 описываются модификации метода ветвей и границ, необходимые для перехода от случая бинарного потока объектов к мультипотоку.

Результаты тестирования реализованного алгоритма ВГ приводятся в §3.3.

В §3.4 показывается, что свойство полиномиальной разрешимости ряда частных подклассов задачи диспетчеризации, выделяемых в [34] для однопоточной задачи, сохраняется и в случае мультипотока.

§3.5 посвящен двум возможным расширениям задачи оптимизации обслуживания мультипотока объектов. В п. 3.5.1 рассматривается случай учета жестких и мягких директивных сроков, а в п.3.5.2 - учета штрафов за простой процессора. Приводится список изменений в алгоритме ВГ, необходимых для решения описанных задач.

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

В §4.1 излагаются различные алгоритмы синтеза рациональных расписаний. Алгоритмы, основанные на дисци-

плине обслуживания "в порядке прихода", рассматриваются в п.4.1.1. Алгоритм последовательного зондирования описывается в п.4.1.2, (p^q)- алгоритм - в п.4.1.3. Вопросы использования алгоритма ВГ в качестве эвристического рассматриваются в п.4.1.4. В п.4.1.5 излагается алгоритм кристаллизации (simulated annealing).

Результаты тестирования построенных алгоритмов (время отработки и качество получаемого расписания) приводятся в §4.2.

В §4.3 рассматриваются вопросы оценки устойчивости расписания. Различные ее определения (в частности, по функционалу и по структуре) вводятся в п. 4.3.1; в следующем пункте приводится пример исследования устойчивости для модельной задачи.

В пятой главе (Структура программного комплекса) описывается разработанный при выполнении диссертационной работы программный комплекс синтеза оптимального (субоптимального) расписания обслуживания.

В §5.1 дается краткое описание программного комплекса (п.5.1.1), описываются его назначение и возможности (п. 5 .1. 2) .

В §5.2 излагается структура комплекса, состав и назначение его файлов. Описывается штатный режим работы комплекса.

§5.3 описывается интерфейс программного комплекса. В п.5.3.1 возможности, предоставляемые комплексом, привязываются к конкретным окнам и пунктам меню; в п.5.3.2 излагается общая структура меню комплекса; в п. 5.3.3 приводятся копии рабочих экранов программы.

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

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

На защиту выносятся:

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

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

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

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

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Шеянов, Анатолий Владимирович

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

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

2) Комплекс позволяет:

- строить оптимальные и близкие к ним расписания;

- исследовать расписания и влияние на них изменений параметров модели.

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

Заключение

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Шеянов, Анатолий Владимирович, 1998 год

Литература

[1]. Andre Chamard & Annie Fischler (Dassault Aviation), Benopt Guinaudeau & Andre Guillaud (Bull) . CHIC Lessons on CLP Methodology, // World Wide Web, http://www.ecrc.de/eclipse/ html/CHIC_Methodology.html

[2]. Tim Chippington Derrick (Hog) and Mike Pegman (Vine Solutions). Overview of constraint-based scheduling. [Posted 24 June 97] World Wide Web, http://www.cirl.uoregon.edu/constraints/archive/ app-sched.txt

[3] . Greenberg. Mathematical Programming Glossary.

World Wide Web, http://www-math.cudenver.edu/ -hgreenbe/glossary/glossary.html, 199 6-7.

[4].Heitkoetter, Joerg and Beasley, David, eds. (1998) "The Hitch-Hiker's Guide to Evolutionary Computation: A list of Frequently Asked Questions (FAQ)", USENET: comp.ai.genetic. Available via anonymous FTP from rtfm.mit. edu/pub/usenet/news.answers/ai-faq/genetic/ About 110 pages.

[5].Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E., "Equation of state calculations by fast computing machines", Journ. of Chemical Physics 21 (1953) 1087- 1092.

[ 6] . Numerical recipies in C: the art of scientific computing. Cambrige University Press, 1992. World Wide Web, Numerical Recipes books On-Line, http://www.ul.cs.emu.edu/books/numerical_recipes /index.html

[7]. Optimization Technology White Paper, ILOG, Inc. World Wide Web, http:// www.ilog.com/papers/ optimization/optimization_wp.pdf

[8].Dick Pountain. Constraint Logic Programming World Wide Web, http://www.cirl.uoregon.edu/ constraints/archive/byte.html

[9].Reeves, C., Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publications (1993).

[10].Авен О.И., Ловецкий C.E., Моисеенко Г.Е. Оптимизация транспортных потоков. - М.: Наука, 1985. - 316 с.

[11].Агрба Д.Ш., Лытова Л.А., Коган Д.И., Федосенко Ю.С. Сценарии и модели оптимизации при автоматизированном проектировании оперативных планов организационного управления транспортно-технологическими системами. - В сб. тезисов докладов Российской научно-технической конференции "Интерактивные системы".- Ульяновск,1993. С.3-4.

[12].Алюшкевич В.Б., Сотсков Ю.Н. Исследование устойчивости оптимальных по быстродействию расписаний. Препринт - Минск: ИТК АН БССР, 1987. N-9. - 20 с.

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

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

[15].Беленький A.C., Левнер E.B. Применение моделей и методов теории расписаний в задачах оптимального планирования на грузовом транспорте// Автоматика и телемеханика. 1989. N-2 . С. 3-77.

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

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

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

[19].Васильева Е.М., Игудин Р.В., Лившиц В.Н. Оптимизация планирования и управления транспортными системами. - М.: Транспорт, 1987. - 208 с.

[20] .Войчинский А.М., Диденко Н.И., Лузин В. П. Гибкие автоматизированные производства. - М.: Радио и связь, 1987.- 272 с.

[21].Воловой Д.И., Федосенко Ю.С. О компьютерных алгоритмах оптимизации оперативного планирования подачи тоннажа к добывающим земснарядам (на примере Камского грузового района)// Тр. Горьков-ского ин-та инж. водного транспорта. - Горький: ГИИВТ, 1989. Вып.239. С. 114-127.

[22].Воловой Д.И., Федосенко Ю.С., Фейгин М.И. Диалоговая микрокомпьютерная модель оперативного планирования и управления транспортно-технологи-ческими процессами в Камском грузовом районе. -В сб. "Моделирование процессов управления транспортными системами. Тезисы докладов Всесоюзной

школы-семинара. - Владивосток: ИАПУ ДВНЦ АН СССР, 1989. С. 144-145.

[23].Гене Г.В., Левнер Е.В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы (обзор)// Изв. АН СССР. Техническая кибернетика. 1979. N-6. С. 9-20.

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

[25].Гэри М. , Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 416 с.

[26].Захаров В.Н., Федюшин В.М. Оперативное управление работой грузовых судов речного флота на базе АСУ "Пароходство". - Горький: ГИИВТ, 198 9.- 7 6с.

[27].Игудин Р. В. Задачи теории расписаний на транспорте и алгоритмы их решения//Экономика и математические методы. 1975. N-3. С. 491-499.

[28].Клейнрок JI. Теория массового обслуживания. -М.: Машиностроение, 1979.-432 с.

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

[30].Ковалев М.Я., Струсевич В.А., Танаев B.C., Тузиков A.B., Шафранский Я.М. Приближенные алгоритмы в теории расписаний. - В кн. Методы решения экстремальных задач. - Минск, 1989.

[31].Коган Д.И., Федосенко Ю.С. Алгоритм решения общей задачи однопроцессорного обслуживания потока заявок. Вестник ННГУ им. Н.И. Лобачевского. Се-

рия "Математическое моделирование и оптимальное управление". Н.Новгород, 1997.

[32].Коган Д.И., Федосенко Ю.С. Анализ вычислительной сложности и устойчивости решений оптимального упорядочения для однопроцессорной системы обслуживания . - В сб. Информационные технологии и системы. Тезисы докладов конференции международного форума информатизации. - Воронеж, 1993. С. 55.

[33].Коган Д.И., Федосенко Ю.С. Вычислительные модели и сложность задачи оптимального управления транспортно-технологическими процессами в системе пространственно рассредоточенных приборов// Тр. Волжской гос. академии водного транспорта. -Нижний Новгород: ВГАВТ. Вып.270, 1994. С. 21-30.

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

[35].Коган Д.И., Федосенко Ю.С., Шеянов A.B. Синтез оптимальных расписаний однопроцессорного обслуживания мультипотока объектов. В сб. "Моделирование и оптимизация сложных технических систем" . Тр. ВГАВТ, вып. 273. Н.Новгород. 1997.

[36].Коган Д.И., Шеянов A.B. Полиномиальная реализуемость метода ветвей и границ для частных классов задач диспетчеризации. Вестник Нижегородского государственного университета: Мат. моделирование и оптимальное управление. Изд-во нижегородского университета, Нижний Новгород, 1997.

[37].Коган Я.А., Лищинский Л.Ю. Парадизов Н.В. Модели обслуживания станков в гибких производственных системах// Автоматика и телемеханика. 1986. N-6. С. 147-155.

[38].Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю. Метод ветвей и границ. Обзор теории, алгоритмов, программ. Math. Operationforshung und statistics. Ser. Optimization. 1977. V. 8. N-2. P. 253-280.

[39].Королёв С.А., Федосенко Ю.С., Шеянов А. В. Опыт реализации алгоритмов динамического программирования для проектирования расписаний однопроцессорного обслуживания бинарного потока заявок. Сб. Математическое обеспечение информационных технологий в технике, образовании, медицине (тезисы докладов Всероссийского совещания-семинара) . 4.1. Изд. ВГТУ. Воронеж. 1996.

[40].Подчасова Т.П., Португал В.М., Татаров В.А., Шкурба В. В. Эвристические методы календарного планирования. - Киев: Техн1ка, 1980. - 126 с.

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

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

[43].Резер С.М., Ловецкий С.Е., Меламед И.И. Математические методы оптимального планирования в траспортных системах// Итоги науки и техники.

Сер. Организация управления транспортом. Т.9. -М.: ВИНИТИ, 1990. - 172с.

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

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

[46].Танаев B.C., Шкурба В.В. Введение в теорию расписаний.- М.: Наука, 1975. - 256 с.

[47].Taxa X. Введение в исследование операций. T.I. - М.: Мир, 1985. - 364 с.

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

[4 9].Федосенко Ю.С. Модели и алгоритмы управления ресурсами в однофазных системах обслуживания транспортного типа. Автореферат диссертации на соискание ученой степени доктора технических наук. Нижний Новгород: ВГАВТ. 1995. С. 30.

[50].Федосенко Ю.С. Экстремальные задачи в оперативном планировании технологических процессов на водном транспорте. - В сб. тезисов докладов Межгосударственной научной конференции "Экстремальные задачи и их приложения". - Нижний Новгород, 1992. С. 119.

[51].Федосенко Ю.С., Шеянов A.B. Синтез программ управления одностадийного обслуживания бинарного

потока объектов I. Алгоритм ветвей и границ. Сб. научных трудов СПбГУВК. СПб. 1997 (в печати).

[ 52] .Федосенко Ю.С., Шеянов A.B. Синтез программ управления одностадийного обслуживания бинарного потока объектов II. Алгоритмы динамического программирования. Сб. научных трудов СПбГУВК. СПб. 1997 (в печати).