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

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

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

Специальность 05 13.18 - «Математическое моделирование, численные методы и комплексы программ» (технические науки)

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

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

003449457

003449457

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

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

профессор Федосенко Юрий Семенович

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

профессор Коган Дмитрий Израилевич

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

доктор технических наук,

профессор Прилуцкий Михаил Хаимович

кандидат физико-математических наук, доцент Шапошников Дмитрий Евгеньевич

Ведущая организация:

Вычислительный центр им. Л.А.Дородницына РАН

Защита состоится «13» ноября 2008 г в / 3 часов на заседании диссертационного совета Д212.16613 при Нижегородском государственном университете им Н И Лобачевского по адресу 603950, г Нижний Новгород, пр Гагарина, 23

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного университета им Н И Лобачевского

Автореферат разослан «_

2008 г

Ученый секретарь диссертационного совета кандидат физико-математических наук, доцент

В.П. Савельев

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

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

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

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

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

Научные исследования по данному направлению базируются на фундаментальных работах по теории расписаний, в том числе M Garey, D Johnson, E G Coffman, R L Graham, W L Maxwell, В С Гордона, M Я Ковалева, В С Танаева, Я M Шафранского, В В Шкурбы Применительно к различным задачам управления ресурсами, и в частности оптимизации ТТО, дискретные математические модели и решающие алгоритмы исследовались в работах Д И Батищева, А С Беленького, В H Буркова, Э X Гимади, Р В Игудина, Д И Когана и Ю С Федосенко, А В Кононова, А А Корбута, А А Лазарева, С Е Ловецкого, Т П Подчасовой, M X Прилуцкого, И X Сигала, M В Ульянова, Ю Ю Финкельштейна, В Р Хачатурова и других авторов Ряд математических моделей обслуживания потоков объектов в системе независимых процессоров изучался А В Шеяновым и А В Курановым

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

A.B. Синего, H. Shen и Р. Tsiotras, посвященные моделированию технологий обслуживания группировок объектов подвижным процессором. Однако указанные модели покрывают лишь отдельные случаи возможных производственных ситуаций. В частности, в работах A.B. Синего рассматриваются модели однопроцессорного двухрейсового 1 обслуживания объектов в одномерной зоне с запретом возвратных движений, а в публикациях Н. Shen и Р. Tsiotras для дискретной модели обслуживания объектов в кольцевом одномерном участке решается оптимизационная задача дозаправки орбитальной группировки спутников.

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

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

Рис. 1. Пример расположения группировки ПДК в КГР

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

Целью работы является построение и исследование базовых математических моделей и вычислительных алгоритмов, а также разработка комплекса программных средств синтеза оптимальных и субоптимальных стратегий однопроцессорного обслуживания пространственно рассредоточенной группировки стационарных объектов Решение данных задач создает теоретическую основу для создания систем поддержки оперативного планирования и диспетчеризации ТТО В диссертационной работе - там, где целесообразна содержательная интерпретация изучаемых задач, рассматриваются процессы снабжения дизельным топливом группировки ПДК, пространственно рассредоточенной в КГР

В основе моделирования ТТО лежит идеология описания транспортно-технологических процессов на языке обслуживания подвижным процессором Р совокупности 0„ объектов, расположенных в вершинах односвязного неориентированного взвешенного графа С Рассмотрены следующие конфигурации и технологии

1 Граф О имеет произвольную структуру, и на технологию обслуживания объектов группировки 0„ процессором Р не налагается каких-либо специальных ограничений (модель 91^епет/)

2 Граф С? имеет древовидную структуру, а обслуживание всех объектов группировки 0„ осуществляется в процессе реализации двух рейсов между выделенными концевыми вершинами - прямого и обратного (модель 91с/гег)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация результатов работы Диссертационная работа выполнялась в соответствии с Федеральной целевой программой "Электронная Россия" (2002-2010 гг) Ее результаты послужили

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

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

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

-Нижегородские сессии молодых ученых Технические науки (Нижний Новгород, 2006,2007,2008),

- Нижегородские сессии молодых ученых Математические науки (Нижний Новгород, 2006, 2007),

- Международные научно-технические конференции «Информационные системы и технологии - ИСТ» (Нижний Новгород, 2006, 2007, 2008),

- Научные конференции «Технологии Microsoft в теории и практике программирования» (Нижний Новгород, 2006,2007,2008),

-Международные конференции «Идентификация систем и задачи управления - SICPRO» (Москва, 2007,2008),

- V Московская международная конференция по исследованию операций - ORM'2007 (Москва, 2007),

- 9-й Международный научно-промышленный форум «Великие реки'2007 / ICEF» (Нижний Новгород, 2007),

- XV Международная конференция «Проблемы теоретической кибернетики» (г Казань, 2008 г),

- Восьмой международный симпозиум «Интеллектуальные системы» - INTELS'2008 (Нижний Новгород, 2008),

- 22nd European Conference on Operational Research - EURO 2007 (Prague, Czech republic, 2007)

Публикации. Основное содержание диссертационной работы и ее результаты полностью отражены в 20 работах [1-20], опубликованных соискателем лично или в соавторстве в научных изданиях, в том числе в двух статьях [5, 15], представленных в ведущих рецензируемых изданиях, из перечня ВАК РФ1

' http //vak ed gov rWcommon/img/uploaded/VAK/files_help_desk/per-04-2008 doc

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и 6 приложений, содержит 202 страницы текста и 65 рисунков, библиографический список включает 116 источников

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

В первой главе (Дискретные математические модели и методы решения задач однопроцессорного обслуживания) рассматриваются классические задачи однопроцессорного обслуживания и приводится обзор методов их решения

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

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

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

2

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

3 Меламед ИИ, Сергеев СИ, Сигал И.Х Задача коммивояжера Вопросы теории //Автоматика и телемеханика - 1989 - №9 - С 3-33

4 Абайылданов КН, Астахов НД, Сигал ШС Задача определения оптимальной очередности обслуживания объектов с учетом замены оборудования // Известия АН СССР Технич. кибернетика - 1986 -№4 -С 37-39

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

§ 2 I посвящен описанию содержательной постановки задачи (п 2 1 1) и построению общей математической модели Ш^пет/(п 2 1 2) В п 2 1 3 ставится экстремальная задача синтеза оптимальной стратегии однократного одностадийного обслуживания пространственно рассредоточенной группировки объектов подвижным процессором

Основными элементами дискретных моделей процессов обслуживания, рассматриваемых в диссертационной работе, являются п-элементная совокупность Оп независимых стационарных объектов, расположенных в вершинах связного неориентированного графа G с базисной вершиной 0, и обслуживающий их подвижный процессор Р, в начальный момент времени находящийся в вершине О в качестве иллюстрации граф G для схемы на рис 1 представлен на рис 2

Считается известной матрица К={у(/,7)} размерности (н+1)(и+1), где v{l,j) - продолжительность перемещения процессора из вершины I в вершину ] графа С непосредственно (1'0,у) = со, если такое перемещение недопустимо) Также известны элементы матрицы 1={/(г,у)} -продолжительностей перемещений по кратчайшему пути между каждой парой вершин и матрицы предшествования Я={7г(;,у)}, необходимой для построения кратчайших путей (матрицы ¿и П получаются из матрицы V путем применения алгоритма Флойда)

Для каждого объекта 0(1) (¡=],п) известен момент времени /(г), начиная с которого осуществимо его обслуживание, заданы функции т(/, () - продолжительности обслуживания, если оно начинается в момент I, и </^1, О - индивидуального штрафа за обслуживание, завершающееся в момент г Указанные функции являются монотонно возрастающими по

Рис 2 Графовая модель расположения группировки объектов

<Р(Ь 0 =

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

0 при /< /</(/),

а{г) (} - /¿(0) при />/¿/(0

Здесь £Й(г) - продолжительность обслуживания объекта о(г), га?(/) - момент времени, начиная с которого начисляется штраф (/<з?(;) > /(/) + сЛ(/)), я(') -величина штрафа в единицу времени На содержательном уровне td.ii) соответствует моменту начала непроизводительного простоя 1-го ПДК по причине исчерпания запаса топлива, /(¡) соответствует моменту возникновения потребности в бункеровке, а а(() - эксплуатационные расходы на содержание ПДК в единицу времени (удельная величина штрафа)

Под стратегией обслуживания процессором Р объектов совокупности Оп понимается перестановка р= (¡¡, ¡2, ,1п) элементов множества {1,2, . ,и}; объект совокупности 0„ с номером 1к согласно

стратегии р обслуживается к-м по очереди (к = 1, п)

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

образуемую ими совокупность х(р) = {[?„ач(л /*), {{р, ¡¿)], к = 1, п } интервалов будем называть реализацией стратегии р Считается, что допустимая реализация стратегии р удовлетворяет следующим условиям

1) реализация стратегии р компактна,

2) все перемещения процессора Р между вершинами графа О осуществляются по кратчайшему пути,

3) запрещены прерывания при обслуживании объектов,

4) в единицу времени осуществимо обслуживание не более одного объекта

Таким образом, имеют место соотношения ?!) = шах{/(0, (1), г((|)}, ЦР, 1к) = ¿иач(А 1к) + Фк, /нач(А ¡к)), к = 1, 2, , Я, 4ач(А 1к) = шах{гV, 1к-\) + /(/*-1, 1к), /('к)}, к = 2,3, ,п

Совокупный штраф по всем объектам совокупности Оп,

п ^

обслуживаемым согласно стратегии р, есть (2(р) = XI 1 (Р><?))

4 = 1

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

гшп <2(р).

В заключении § 2 I доказано, что задача (1) относится к классу ЫР-трудных в сильном смысле (п 2 1 4).

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

Ц0, 0, 0) = О

X(/,z,S) = шш {Zp{D\i,t)-l(j,1)lj,S\{o(j)}) + ф, /)}

OjbS

В формуле (2)

(2)

S (D*0, t) - /О, i) j, S \ {£>(/)}), при D*(j, 0 > t(i), I.P{t,iS,j)= -j min {Z{tp,j,S\{o{j)})}, приD*0, 0 = <('),

где через Тр обозначен целочисленный отрезок [*(/)+!(/, t(j)), D\i, t)-I(}, j)] Через Ц/, i, S) обозначена минимально возможная величина суммарного штрафа за обслуживание объектов совокупности 5и{о(г)} при условии, что в момент времени t завершено обслуживание объекта o(i), a S-совокупность тех объектов из Оп, которые были обслужены раньше, чем

Ф)

Оптимальное значение Qopt критерия Q(p), соответствующее решению задачи (1), есть

öopt~ min SO, /, О„\{о(0}).

(6{ 1,2, ,п}

В п 2 2 2 излагается алгоритм ®<? синтеза оптимальных стратегий, а пункт 2 2 3 посвящен описанию условий и результатов вычислительных экспериментов, целью которых являлось определение средней продолжительности tc отработки и расходуемого объема памяти V алгоритма DÎP

В табл I приведены статистические значения указанных показателей для значений размерности группировки Оп из диапазона ле[8, 12] минимальное и максимальное значения (указаны в квадратных скобках), среднее значение в тестовом наборе задач приведено через запятую после квадратных скобок

Числовые характеристики решаемых задач генерировались случайным образом по равномерному закону распределения из следующих диапазонов значений (типовых значений параметров КГР)

t(i) е [20,180], dt(i) е [1,10], td(i) е [t(i) + dt(i) +1, t(i) + dt(i) +10],

a(0e[2,10], v(i,j) e [4, 20] При проведении вычислительных экспериментов использовалась компьютерная рабочая станция, имеющая х8б-совместимую аппаратную архитектуру, с процессором Celeron 1700 Mhz и оперативной памятью объемом 512 Mb

Таблица I

_;_Статистические значения tc и V_

п t„ с V, Kb

8 [0 078,0 656], 0 334 [5 273,24 416], 13 839

9 [0 892,5 498], 2 256 [27 685,78 799], 48 610

10 [5 919, 82 929], 29 199 [79 664,231 730], 139 807

11 [66 957, 1168 51], 307 59 [204 38, 858 16], 407 77

12 [993 48,9209 08], 2867 И Г818 64, 2446 53], 1186 45

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

В п 2 2 4 введено понятие элементарной стратегии обслуживания подвижным процессором группировки 0„ стационарных объектов, нередко используемой на практике опытными диспетчерами, и приведены сравнительные результаты оценки эффективности оптимальной и элементарной стратегий обслуживания

На примерах показано, что при реализации оптимальной стратегии обслуживания снижение суммарного штрафа может достигать 60% (от его значения на элементарной статегии обслуживания), а в сравнении с «патологически плохими» стратегиями уменьшение суммарного штрафа может происходить на 2-3 порядка

§ 2 3 посвящен решению экстремальной задачи на основе идеологии метода ветвей и границ В п 2 3 1 излагается алгоритм Й5.95 синтеза оптимальных стратегий, а в пункте 2 3 2 приводятся полученные в ходе вычислительных экспериментов статистические значения средней продолжительности 1С отработки, расходуемого объема памяти К а также средней продолжительности от момента начала работы до момента последнего улучшения значения рекорда алгоритма Э»ЕВ

Согласно полученным статистическим данным, максимальная размерность группировки, при которой синтез решения алгоритмом 35,35

укладывается в 15-минутный регламент отработки, составляет 15 объектов, т е. на 4 единицы больше, чем у алгоритма Ф^Р В то же время при 16 < п < 40 время последнего улучшения значения рекорда в среднем не превосходит 8 мин, те. в течение примерно половины времени отработки алгоритма дальнейшего улучшения значения рекорда не происходит Поэтому при 16 < и < 40 алгоритм £М8 (с ограничением на максимальную длительность отработки) может использоваться в качестве эвристической процедуры синтеза решения Соответствующая оценка качества приближения оптимума в сравнении с другими эвристиками приводится в §§ 3 1-3 3

§ 2 4 посвящен решению экстремальной задачи на основе совместного применения методов динамического программирования и ветвей и границ5 В п 2 4 1 излагается комбинированный алгоритм ®{ЖВ«£В синтеза оптимальных стратегий, а в пункте 2 4 2 приводятся •полученные в ходе вычислительных экспериментов статистические значения /с и V алгоритма Ф^Р+ЗЗ»®

Из полуденных статистических данных следует, что введение в алгоритм ЪЗ" дополнительного отсечения бесперспективных вариантов на основе нижней и верхней оценок значения 0{р) позволило увеличить максимальную размерность задачи (при которой синтез оптимальной стратегии укладывается в 15-минутный регламент) до 15 объектов, те на 4 единицы больше, чем алгоритм ■£)£? Также оказалось, что при л <15 средняя продолжительность синтеза алгоритмом ФбЧ-йи® существенно меньше, чем алгоритмом Й5*£В Поэтому с точки зрения практического применения для синтеза оптимальной стратегии обслуживания наиболее предпочтительным является алгоритм ©{Р+Зкй

§ 2 5 посвящен оценке устойчивости по структуре стратегий обслуживания пространственно рассредоточенной группировки объектов В п 2 51 введено понятие устойчивости по структуре стратегии обслуживания, в п 2 5 2 изложена процедура построения карт устойчивости по структуре, а в п 2 5 3 построены примеры плоских сечений карт устойчивости по структуре оптимальных стратегий в пространстве параметров модели

Ниже в табличной форме представлен пример сечения карты устойчивости оптимальных стратегий__

р, = (4, 5,7,8, 6, 2, 3, 1) р1 = (4, 5, 7, 8, 2, 3, 6,1) Рз =(4, 5, 7, 8, 2, 6, 3, 1)

А = (5, 7, 4, 8, 6, 2,3,1) р5 = (5, 7, 4, 8, 2, 6, 3, 1) д =(5,7, 4, 8, 2,3, 6, 1)

5 Алексеев О Г Комплексное применение методов дискретной оптимизации -М Наука Гл ред физ-мат лит, 1987 - 248 с

в плоскости изменений Д/0 и Д4 продолжительностей перемещений процессора из точек дислокации объектов о(0) и о(6) (табл 2), границы областей устойчивости выделены утолщенными линиями, при этом в каждой ячейке таблицы приведены соответствующие оптимальной стратегии значения суммарного штрафа

Таблица 2

Д/о\ 0 1 . 2 3 4 5 6 7 8 9 10 и 12

0 818 829 838 846 854 863 871 874 875 876 877 878 879

1 818 829 838 846 854 863 871 874 875 876 877 878 879

2 818 829 838 846 854 863 871 874 875 876 877 878 879

3 Р> 829 838 863 871 874 875 878 879

4 829 838 Иг 863 871 874 875 Р> 878 879

5 833 844 853 861 869 878 886 889 890 891 892 893 894

6 847 858 867 875 883 892 900 903 904 905 906 907 908

7 865 876 885 893 901 910 918 921 922 923 924 925 926

8 878 889 898 906 914 923 931 934 935 936 937 938 939

9 889 898 923 931 934 935 938 939

10 Р> 889 898 А 923 931 934 935 А 938 939

11 899 908 933 941 944 945 948 949

12 897 908 917 925 933 942 950 953 954 955 956 957 958

В § 2 6 данные о значимых с точки зрения практического применения характеристиках алгоритмов Ф{?, ЙШ, Ф9Ч-£В»£В сведены в единую таблицу (табл 3) В столбцах этой таблицы для каждого алгоритма приведены тип отыскиваемой стратегии (оптимальная или субоптимальная) и максимальная размерность группировки, при которой синтез решения укладывается в 15-минутный регламент отработки.

Таблица 3

Вычислительные характеристики алгоритмов_

Алгоритм Тип стратегии Максимальная размерность группировки

-АЗ1 оптимальная И

йШ оптимальная / субоптимальная 15/40

оптимальная 15

На основе представленной в табл 3 информации, даны следующие рекомендации по выбору алгоритмов из числа ©!?, £В«£В и Ф^+ЗШ в зависимости от оперативной обстановки принятия решений

1 При и < 15 оптимальная стратегия может быть найдена либо при помощи алгоритма ЗШ, либо ©9Ч-£В.£В Однако поскольку при п <15 средняя продолжительность синтеза алгоритмом ©З'+ЙШ меньше, чем алгоритмом для синтеза оптимальной стратегии обслуживания предпочтительным является алгоритм ФЗЧ-ЗШ

2 При я >15 алгоритм £В.З с ограничением максимальной продолжительности синтеза может использоваться в качестве эвристической процедуры синтеза субоптимальных стратегий обслуживания

В третьей главе (Алгоритмы синтеза субоптимальных стратегий обслуживания) рассматриваются алгоритмы синтеза субоптимальных стратегий обслуживания пространственно рассредоточенной группировки объектов, позволяющие в рамках ограничений на максимальное время отработки осуществить синтез стратегий обслуживания для задач повышенной размерности Для каждого алгоритма приводятся полученные статистические значения продолжительности /с отработки и расходуемого объема V оперативной памяти Также приводятся статистические значения относительного отклонения е суммарного штрафа от оптимума либо рекорда метода ветвей и границ, а также процент со вычислительных экспериментов, в которых значение штрафа совпало с оптимумом (рекордом)

В § 3 1 приводится описание и результаты вычислительного тестирования эвристического алгоритма ЧЮ2, основанного на совместном применении совокупности алгоритмов «жадного» типа и алгоритма локального поиска Согласно полученным статистическим данным при 16 < и < 40 погрешность приближенных решений, получаемых алгоритмом 416, относительно рекорда алгоритма £В»35 в среднем не превышала 7% и в более чем 80% экспериментов не превышала 10% Также показывается, как общая идея локального поиска может быть использована для «улучшения» начальных решений, задаваемых лицом, принимающим решения (ЛПР)

§ 3 2 посвящен описанию и результатам вычислительного тестирования алгоритма Ф£Р® синтеза субоптимальных стратегий обслуживания, основанного на концепции (¡-расписания6, при этом в

6 Коган, Д И, Федосенко Ю С Задача диспетчеризации анализ вычислительной сложности и полиномиально разрешимые подклассы // Дискретная математика -1996 -Т 8 -ЛЬЗ -с 135-147

качестве начальной нумерации объектов использовались стратегии, отыскиваемые алгоритмом 916. Временная вычислительная сложность процедуры синтеза (1-расписаний оценивается величиной (0(п2)) Поэтому построенный на этой концепции алгоритм ©£РФ оказался приемлемым по быстродействию для практических приложений Согласно данным вычислительных экспериментов предельное значение размерности задачи, при которой синтез решения укладывается в 15-минутный регламент отработки, находится в пределах интервала [25,30] Что же касается оценки относительного отклонения штрафа от оптимума (либо рекорда метода ветвей и границ), то по крайней мере в 90% случаев оно не превышает 10%, а в среднем - 6%

В § 3 3 излагается алгоритм синтеза субоптимальных стратегий обслуживания §<?, построенный в рамках идеологии эволюционно-генетического поиска, и приводятся результаты его тестирования В число особей начальной популяции алгоритма 33 включались стратегии, отыскиваемые в процессе работы эвристического алгоритма 01(2.

Согласно данным вычислительных экспериментов среднее относительное отклонение штрафа от оптимума (рекорда) не превышает 5% и в более чем в 94% случаев максимальное относительное отклонение не превышает 10% Кроме того, отыскиваемые алгоритмом 33 стратегии имеют в среднем на 1,0-1,5% меньший штраф по сравнению со стратегиями, синтезируемыми алгоритмом 91С

Учитывая эти данные, а также то обстоятельство, что максимальная продолжительность синтеза алгоритмом Ш вплоть до п = 40 не превышает 196 с, алгоритм 9$ может быть рекомендован для оперативного синтеза субоптимальных стратегий обслуживания во всем диапазоне практически значимых размерностей группировки

§ 3 4 посвящен оценке возможности синтеза стратегий обслуживания с помощью реализации нейросетевого подхода7 В п 3 4 1 приводится описание искусственной нейронной сети (однослойного персептрона), способной осуществить синтез стратегий обслуживания

В п 3 4 2 описывается процедура формирования эталонных значений выходных сигналов, необходимых для осуществления процедуры обучения персептрона (п 3 4 3)

В п 3 4 4 дается оценка быстродействия компьютерной реализации искусственной нейронной сети, а в п 3 4 5 на примере выполнения процедуры обучения персептрона для п = 5, п = 6 и п= 7 показывается принципиальная возможность использования модели однослойного

7 Галушкин А И Теория нейронных сетей - М ИПРЖР, 2000 - 416 с

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

В § 3 5 данные о значимых с точки зрения практического применения характеристиках алгоритмов 916,3(2, 9к£В и ©ЗЧ-ЗШ сведены в единую таблицу (табл 4) и даны рекомендации по выбору того или иного алгоритма

Таблица 4

Вычислительные характеристики алгоритмов

Алгоритм Максимальная размерность группировки Среднее относительное отклонение от оптимума (рекорда) Максимальное относительное отклонение от оптимума (рекорда) Процент совпадений с оптимумом (рекордом)

Ж 40 [0 70, 6 44] [8 11, 19 88] [0, 78]

m-d 30 [0 63,5 51] [8 89, 19 02] [0, 85]

SS 40 [0 22,4 70] [И 13, 18 85] [0, 96]

Как следует из данных табл 4, обеспечиваемая алгоритмом SiS точность приближения оптимального решения выше, чем у алгоритмов 91С и $34/

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

1 При я <15 целесообразным является применение алгоритма ФЗ'+ЙШ синтеза оптимальных стратегий обслуживания

2 При 16<«<40 для синтеза субоптимальных стратегий обслуживания могут применяться либо алгоритм S(i, либо алгоритм ökffi в режиме ограничения максимальной продолжительности синтеза Алгоритм M целесообразно использовать в тех случаях, когда синтез решения выполняется в сжатом временном регламенте, а качество приближения оптимума не имеет первостепенного значения - например, при построении карты устойчивости по структуре Алгоритм же йШ следует применять в случаях, когда от получаемого решения требуется как можно большая его близость к оптимальному согласно результатам вычислительных экспериментов никакой из эвристических алгоритмов SIC, W-d, Se? не позволяет получить «лучшего» решения, чем соответствующего рекорду метода ветвей и границ

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

§ 41 посвящен построению математической модели Ш,пе и постановке экстремальной задачи двухрейсового обслуживания пространственно рассредоточенной группировки объектов в рабочей зоне древовидной структуры (4 1 1-4 12) В п 4 1 3 доказана №-трудность задач данного класса, а для его подкласса ЭС|', характеризующегося

условием ф)=0 0= 1 ,п)), установлено существование псевдополиномиального решающего алгоритма

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

Пункт 4 16 посвящен описанию условий и результатов вычислительного тестирования (по параметрам ¡с п V) алгоритма ФЭ^ Полученные результаты свидетельствуют о том, что алгоритм практически полностью покрывает диапазон возможных в рамках модели Шаче производственных ситуаций при соблюдении 15-минутйого регламента отработки алгоритм ФС?,^ способен осуществить синтез оптимальных стратегий обслуживания для группировок, включающих до 25 объектов (в то время как на практике максимальное количество ПДК в КГР не превышает 25-30)

На рис 3 приведен пример стратегии обслуживания объектов в рабочей зоне древовидной структуры - номера объектов указаны в левых секторах, а порядковые номера их обслуживания обозначены курсивом в правых секторах графовой модели

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

Пп 4 2 1-4 2 2 § 4 2 посвящены построению математической модели 2Ж,„- и постановке экстремальной задачи двухрейсового обслуживания пространственно рассредоточенной группировки объектов

в рабочей зоне типа w+ (протяженная главная магистраль с простирающимися на относительно небольшие расстояния боковыми ответвлениями).

Решение сформулированной в § 4.2 экстремальной задачи сводится к решению последовательности задач, ранее исследованных в рамках моделей 9Кgenerai и в п. 4.2.3 выводятся обобщающие рекуррентные соотношения динамического программирования, а в п. 4.2.4 излагается алгоритм синтеза оптимальной стратегии обслуживания. Также в

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

Пункт 4.2.5 посвящен описанию условий и результатов вычислительного тестирования (по параметрам tc и V) алгоритма ФЗ^. Полученные результаты свидетельствуют о том, что алгоритм DSV с запасом покрывает диапазон возможных в рамках модели производственных ситуаций: уже в пределах 8 мин алгоритм способен осуществить синтез оптимальных стратегий обслуживания для группировок, включающих до 48 объектов.

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

в рабочей зоне типа ин-

В пятой главе (Интерактивный визуальный программный комплекс поддержки оперативного управления обслуживанием пространственно рассредоточенной группировки ПДК) описывается

разработанный программный комплекс [19-20] синтеза стратегий обслуживания пространственно рассредоточенной группировки объектов, основу математического обеспечения которого составили модели 91 9К)гее, <Ш,„+ и алгоритмы ©9»+®,®, йВ.йв, <№,ке и Ф£РИ,+

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

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

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

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

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

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

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

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

-трудность этих задач

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

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

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

1 Шлюгаев, А Ю Алгоритмы синтеза оптимального обслуживания группы пространственно рассредоточенных объектов mobile-процессором / А Ю Шлюгаев // XI нижегородская сессия молодых ученых Технические науки Материалы докладов Н Новгород, 12-16 февр 2006 г - Н Новгород Изд-во Гладкова О В, 2006 - С 34

2 Шлюгаев, А Ю Модели обслуживания группы пространственно рассредоточенных объектов тоМе-процессором и проблема синтеза оптимальных расписаний при наличии двух оценочных критериев / А Ю Шлюгаев // Тезисы докладов Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2006)» Н Новгород, 21 апр 2006 г -Н Новгород НГТУ, 2006 -С 165-166

3 Федосенко, Ю С Идея и программная реализация эвристического алгоритма бикритериапьного синтеза расписаний обслуживания mobile-процессором пространственно рассредоточенной группы объектов / Ю С Федосенко, А Ю Шлюгаев // Технологии Microsoft в теории и практике программирования Материалы конференции Н Новгород, 21-22 мар 2006 г -Н Новгород. Изд-во Нижегородского госуниверситета, 2006 - С 318-321

4 Шлюгаев, А Ю Реализация синтеза расписаний обслуживания группы пространственно рассредоточенных объектов тоЫ1е-процессором методом динамического программирования / А Ю Шлюгаев // XI нижегородская сессия молодых ученых Математические науки Материалы докладов Н Новгород, 22-25 мая 2006 г-Н Новгород Изд-во Гладкова О В , 2006 - С 26

5 Федосенко, Ю.С. Общая задача однопроцессорного обслуживания пространственно рассредоточенной группы стационарных объектов / ЮС Федосечко, А Ю. Шлюгаев // Математическое моделирование и оптимальное управление: Вестник ННГУ (индекс-88053).-2007. - №3 -С 119-123.

6 Шлюгаев, А Ю Оптимизация обслуживания пространственно рассредоточенной группы стационарных объектов тоЫ1е-процессором в условиях концепции d-расписаний'/ АЮ Шлюгаев //(Труды НГТУ Системы обработки информации и управления - Н Новгород НГТУ - 2007 - Т 65 - Вып 14 -С 42-50

7 Коган, Д И Математическая модель и алгоритм синтеза субоптимальных расписаний однопроцессорного обслуживания пространственно рассредоточенной группы стационарных объектов / Д И Коган, Ю С Федосенко, А Ю Шлюгаев // Труды VI Международной конференции SICPRO'07 М , 29 янв - 1 февр 2007 г -М ИПУ им В А Трапезникова РАН, 2007 - С 1026-1038

8 Шлюгаев, А Ю Оптимизация процесса снабжения топливом плавучих добывающих комплексов в крупномасштабном районе с существенно разветвленной русловой топологией / АЮ Шлюгаев // XII нижегородская сессия

молодых ученых Технические науки Материалы докладов Н Новгород, 26 февр -2 мар 2007 г -Н Новгород Изд-во Гладкова О В , 2007 - С 12-13

9 Федосенко, Ю С Комбинированный алгоритм синтеза расписаний двухрейсового обслуживания группы стационарных объектов в древовидной рабочей зоне /ЮС Федосенко, А Ю Шлюгаев // Технологии Microsoft в теории и практике программирования Материалы конференции Н Новгород, 3-4 апр 2007 г -Н Новгород Изд-во Нижегородского госуниверситета, 2007 — С 309-313

10 Коган, ДИ Задача одностадийного обслуживания добывающих комплексов в крупномасштабной акватории / Д И Коган, Ю С Федосенко, А Ю Шлюгаев II Труды V Московской международной конференции по исследованию операций (ORM2007) М, 10-14 апр 2007 г -М МАКС Пресс, 2007 - С 60-62

11 Шлюгаев, А Ю Модель двухрейсового обслуживания mobile-процессором группы стационарных объектов в древовидной рабочей зоне с учетом индивидуальных предпочтений I АЮ Шлюгаев II Тезисы докладов Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2007)» Н Новгород, 20 апр 2007 г - Н Новгород НГТУ, 2007 -С 222

12 Федосенко, Ю С Модели и алгоритмы оптимизации стратегий снабжения топливом плавучих добывающих комплексов в крупномасштабных районах со сложной русловой топологией /ЮС Федосенко, А Ю Шлюгаев // 9-й Международный научно-промышленный форум «Великие реки'2007 / ICEF» генеральные доклады, тезисы докладов Н Новгород, 15-19 мая 2007 г

13 Федосенко, Ю С Обобщение задачи коммивояжера для модели одностадийного обслуживания пространственно рассредоточенной группировки стационарных объектов / ЮС Федосенко, АЮ Шлюгаев // Проблемы теоретической кибернетики Тезисы докладов XV международной конференции (Казань, 2-7 июня 2008 г) Под редакцией Ю И Журавлева - Казань Отечество, 2008 -С 116-117

14 Shlyugaev, A Yu Mathematical models and algonthms of synthesizing servicing schedules of a group of spatially distributed fixed objects by a mobile processor / A Yu Shlyugaev // EURO 2007 - 22nd European Conference on Operational Research, Prague, Czech republic, July 8-11, 2007 Book of abstracts, p 217

15 Федосенко, Ю С Нейросетевая методика синтеза расписаний обслуживания группировки стационарных объектов / Ю С. Федосенко, А Ю. Шлюгаев // Нейрокомпьютеры разработка и применение (индекс -79241) -М-Радиотехника -2007 -№11 -С 46-53

16 Шлюгаев А Ю Модели и алгоритмы синтеза стратегий одностадийного обслуживания группировки стационарных объектцв / А Ю Шлюгаев // Технологии Microsoft в теории и практике программирования Материалы конференции Н Новгород, 19-20 мар 2008 г - Н Новгород Изд-во Нижегородского госуниверситета, 2008 — С 359-361

17 Шлюгаев, АЮ Интерактивный визуальный программный комплекс поддержки оперативного управления снабжением топливом группировки плавучих добывающих комплексов / А Ю Шлюгаев // Тезисы докладов Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2008)» Н Новгород, 18 апр 2008 г -Н Новгород НГТУ, 2008 -С 49

18 Федосенко, ЮС О рациональной архитектуре интеллектуальной программной системы оперативного управления снабжением топливом группировки плавучих добывающих комплексов / ЮС Федосенко, А Ю Шлюгаев // Интеллектуальные системы Труды 8-го международного симпозиума -М РУСАКИ, 2008 -С 576-579

19 Шлюгаев, А Ю Интерактивный визуальный программный комплекс поддержки оперативного управления снабжением топливом группировки плавучих добывающих комплексов / А Ю Шлюгаев II Инновации в науке и образовании / Телеграф отраслевого фонда алгоритмов и программ - ФГНУ «Государственный координационный центр информационных технологий» -2008 - Февраль -№2(37)

20 Свидетельство №2008611757 РФ Интерактивный визуальный программный комплекс поддержки оперативного управления снабжением топливом группировки плавучих добывающих комплексов / А Ю Шлюгаев, заявитель и правообладатель - Заявл 21 02 08, зарег 02 04 08 - Федеральная служба по интеллектуальной собственности, патентам и товарным знакам РФ, Реестр программ для ЭВМ

Формат 60><84 '/)6 Гарнитура «Тайме» Ризография Уел печ л 1,37 Уч-изд л 1,41 Тираж 100 экз Заказ 195

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

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

ВВЕДЕНИЕ.

ГЛАВА 1. ДИСКРЕТНЫЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ

РЕШЕНИЯ ЗАДАЧ ОДНОПРОЦЕССОРНОГО ОБСЛУЖИВАНИЯ.

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

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

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

1.1.3. Каноническая задача однопроцессорного обслуживания потока объектов.

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

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

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

§ 1.2. Общие методы решения задач однопроцессорного обслуживания.

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

1.2.2. Метод ветвей и границ.

1.2.3. Приближенные и эвристические методы.

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

ГЛАВА 2. ОБЩАЯ МАТЕМАТИЧЕСКАЯ МОДЕЛЬ И ВЫЧИСЛИТЕЛЬНЫЕ

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

СТАЦИОНАРНЫХ ОБЪЕКТОВ.

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

2.1.1. Содержательное описание технологии однопроцессорного обслуживания.

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

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

2.1.4. Оценка вычислительной сложности экстремальной задачи.

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

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

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

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

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

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

2.3.1. Описание алгоритма синтеза £Вг£В.

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

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

2.4.1. Описание алгоритма синтеза ФбЧ-бкй}.

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

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

2.5.1. Понятие устойчивости стратегий обслуживания по структуре.

2.5.2. Построение карт устойчивости стратегий обслуживания по структуре.

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

§ 2.6. Рекомендации по применению алгоритмов ЗДР, ffiiffi, ©SM-Qkffi.

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

ГЛАВА 3. АЛГОРИТМЫ СИНТЕЗА СУБОПТИМАЛЬНЫХ СТРАТЕГИЙ

ОБСЛУЖИВАНИЯ.

§3.1. Синтез субоптимальных стратегий эвристическим алгоритмом

3.1.1. Исходные предпосылки.

3.1.2. Описание алгоритма ©1(2.

3.1.3. Оценка вычислительной сложности.

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

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

3.2.1. Предварительные замечания.

3.2.2. Описание концепции d-расписаний.

3.2.3. Модификация рекуррентных соотношений динамического программирования в рамках концепции d-расписаний.

3.2.4. Описание алгоритма ИЗ1-© синтеза субоптимальных стратегий обслуживания.

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

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

3.3.1. Описание алгоритма синтеза

§&.

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

§ 3.4. Синтез стратегий обслуживания на основе нейросетевого подхода.

3.4.1. Предварительные замечания.

3.4.2. Описание искусственной нейронной сети для решения задачи синтеза стратегий обслуживания.

3.4.3. Описание процедуры формирования эталонных значений выходных сигналов.

3.4.4. Описание процедуры обучения нейронной сети.

3.4.5. Оценка быстродействия нейронной сети.

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

§ 3.5. Рекомендации по применению алгоритмов 016, Ф^Р-Ф, Зй.

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

ГЛАВА 4. ЧАСТНЫЕ МОДИФИКАЦИИ ОБЩЕЙ МАТЕМАТИЧЕСКОЙ

МОДЕЛИ И СПЕЦИАЛИЗИРОВАННЫЕ АЛГОРИТМЫ

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

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

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

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

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

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

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

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

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

4.2.1. Описание особенностей рабочей зоны типа и технологии обслуживания.

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

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

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

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

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

ГЛАВА 5. ИНТЕРАКТИВНЫЙ ВИЗУАЛЬНЫЙ ПРОГРАММНЫЙ

КОМПЛЕКС ПОДДЕРЖКИ ОПЕРАТИВНОГО УПРАВЛЕНИЯ

ОБСЛУЖИВАНИЕМ ПРОСТРАНСТВЕННО

РАССРЕДОТОЧЕННОЙ ГРУППИРОВКИ ПДК.

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

§ 5.2. Описание интерфейса пользователя.

§ 5.3. Описание архитектуры программного комплекса.

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

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

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

Как следует из работ, посвященных моделированию и оптимизации ТТО [15,19,25], их адекватное математическое описание для достаточно обширного класса производственных ситуаций может быть выполнено в рамках дискретных моделей обслуживания конечных детерминированных потоков объектов [46, 49], т.е. на традиционном для теории расписаний языке. Точность такого моделирования определяется выбором шага г дискретности пространственных и временных параметров, а синтез оптимальных стратегий — расписаний обслуживания - принципиально осуществим комбинаторными методами дискретного программирования (такими как метод динамического программирования [10], ветвей и границ [42] и др.).

Научные исследования по данному направлению базируются на фундаментальных работах по теории расписаний [37], в том числе М. Garey, D. Johnson [23], E.G. Coffman [97], R.L. Graham [100], W.L. Maxwell [98], B.C. Гордона [20, 21, 22], М.Я.Ковалева [71], B.C. Танаева [70, 69], Я.М. Шафранского [82], В.В. Шкурбы [85]. Применительно к различным задачам управления ресурсами и, в частности оптимизации ТТО, дискретные математические модели и решающие алгоритмы исследовались в работах

Д.И. Батищева [5], А.С. Беленького [8,9], В.Н.Буркова [11,12,13], Э.Х. Гимади [17], Р.В. Игудина [24], Д.И. Когана и Ю.С. Федосенко [27, 28, 29, 30, 33, 34], А.В. Кононова [38, 39, 40], А.А. Корбута [43], А.А. Лазарева [52, 53, 54], С.Е. Ловецкого [64], Т.П. Подчасовой [62], М.Х. Прилуцкого [63], И.Х. Сигала [65], М.В. Ульянова [72, 73], Ю.Ю. Финкелыптейна [79], В.Р. Хачатурова [81] и других авторов.

Ряд математических моделей обслуживания потоков объектов в системах независимых процессоров исследовался в работах А.В. Шеянова [83, 84], А.В. Куранова [50, 51].

В контексте тематики диссертационной работы особо следует упомянуть сравнительно недавно опубликованные работы А.В. Синего [67, 68], а также Н. Shen и P. Tsiotras [112,113], посвященные моделированию технологий обслуживания группировок объектов подвижным процессором. Однако указанные модели покрывают лишь отдельные случаи возможных производственных ситуаций: в работах [67,68] исследуются модели однопроцессорного двухрейсового обслуживания объектов в одномерной зоне с запретом возвратных движений, а в публикациях [112, 113] для дискретной модели обслуживания объектов в кольцевом одномерном участке решается оптимизационная задача дозаправки орбитальной группировки спутников.

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

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

Повышенные требования к качеству реализации ТТО предъявляются в крупномасштабных грузообразующих районах внутреннего водного транспорта (КГР) [14], в которых плавучими дизель-электрическими добывающими комплексами (ПДК) осуществляется массовая русловая разработка нерудных строительных материалов (НСМ).

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

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

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

1. Граф G имеет произвольную структуру, и на технологию обслуживания объектов группировки О,, процессором Р не налагается каких-либо специальных ограничений (модель 91 lgemrai)1.

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

К***).

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

1 Заметим, что Щ.е„ет1 может рассматриваться и как обобщение классической модели коммивояжера [78], в которой дополнительно учитываются продолжительности пребывания в городах и факторы, определяющие приоритетность посещения того или иного города. прямого (в порядке возрастания номеров вершин М) и обратного (в порядке убывания номеров вершин М) с попутным обслуживанием объектов, расположенных в соответствующих боковых ответвлениях (модель ©Недостижение объявленной выше цели диссертационной работы требует рассмотрения следующих задач:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-Нижегородские сессии молодых ученых (Нижегородская область, с. Татинец, 2006 и 2007 г.);

- Международные научно-технические конференции «Информационные системы и технологии - ИСТ» (г. Нижний Новгород, 2006-2008 гг.);

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

- Международные конференции «Идентификация систем и задачи управления - SICPRO» (г. Москва, 2007 г., 2008 г.);

- V Московская международная конференция по исследованию операций - ORM2007 (г. Москва, 2007 г.);

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

- XV международная конференция «Проблемы теоретической кибернетики» (г. Казань, 2008 г.);

- 22-nd European Conference on Operational Research - EURO-2007 (Czech Republic, Prague, 2007).

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и 6 приложений; содержит 202 страницы текста, 65 рисунков и список литературы из 116 наименований.

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

1. Сформулированы функциональные требования к программному комплексу поддержки оперативного управления снабжением топливом группировки ПДК в КГР.

2. Приведено описание функциональных возможностей ИВПК и интерфейса пользователя.

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

Заключение

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

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

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

1.1. Граф G имеет произвольную структуру, и на технологию обслуживания объектов группировки Оп процессором Р не налагается каких-либо специальных ограничений.

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

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

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

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

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

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

1. Абайылданов, К.Н. Задача определения оптимальной очередности обслуживания объектов с учетом замены оборудования / К.Н. Абайылданов, Н.Д. Астахов, И.Х. Сигал // Известия АН СССР. Технич. кибернетика. 1986. - №4. - С. 37-39.

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

3. Алексеев, О.Г. О комплексном применении методов динамического программирования и ветвей и границ в задачах дискретного программирования / О.Г. Алексеев, И.Ф. Володось // Автоматика и телемеханика. 1976. - №4. - С. 92-100.

4. Асанов, М.О. Дискретная математика. Графы, матроиды, алгоритмы / М.О. Асанов, В.А. Баранский, В.В. Расин. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

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

6. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач / Д.И. Батищев. Воронеж: Воронежский гос. техн. ун-т, 1995. -65 с.

7. Батищев, Д.И. Применение генетических алгоритмов к решению задач дискретной оптимизации: Учебное пособие / Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин. Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2006. - 123 с.

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

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

10. Беллман, Р. Динамическое программирование / Р. Беллман, С. Дрейфус. М.: ИЛ., 1960. - 400 с.

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

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

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

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

15. B.А. Легостаев. -М.: Транспорт, 1988. 175 с.

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

17. Гордон, B.C. К вопросу минимизации функций на множестве перестановок частично упорядоченных элементов / B.C. Гордон, Я.М. Шафранский // Изв. АН БССР. Сер. физ.- матем. наук. 1979. - №2.1. C.122-124.

18. Гордон, B.C. О минимаксных задачах теории расписаний с одним прибором / B.C. Гордон, B.C. Танаев // Изв. АН БССР. Сер. физ.-матем. наук. 1982.-№3.

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

20. Игудин, Р.В. Задачи теории расписаний на транспорте и алгоритмы их решения / Р.В. Игудин // Экономика и математические методы. — 1975. -№3. С. 491^499.

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

22. Коган, Д.И. Динамическое программирование и дискретная многокритериальная оптимизация: учебное пособие / Д.И. Коган. -Н. Новгород: Изд-во ННГУ, 2005. 260 с.

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

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

25. Кононов, А.В. Задачи теории расписаний на одной машине с длительностями работ, пропорциональными произвольной функции / А.В. Кононов // Дискретн. анализ и исслед. опер., серия 1. 1998. -Т. 5. - №3. - С. 17-37.

26. Корбут, А.А. Метод ветвей и границ. Обзор теории, алгоритмов, программ и приложений / А.А. Корбут, И.Х. Сигал, Ю.Ю. Финкелъштейн // Math. Operation Forsch. Statist. Ser. Optimization. -1977.-V. 8, №2.-P. 253-280.

27. Корбут, А.А. Приближенные методы дискретного программирования / А.А. Корбут, Ю.Ю. Финкелыптейн // Изв. АН СССР, Техническая кибернетика. 1983. -№ 1. - С. 165-176.

28. Кочетов, Ю.А. Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами / Ю.А. Кочетов, А.А. Столяр // Дискретн. анализ и исслед. опер., серия 2. 2005. - Т. 12. - №1. - С. 12-36.

29. Красовский, Д.В. Псевдополиномиальные алгоритмы упорядочения работ без прерываний по произвольным процессорам / Д.В. Красовский, М.Г. Фуругян // Вестник Московского университета, сер. 15. Вычислительная математика и кибернетика. — 2006. № 4. -С. 25-28.

30. Кулик, В.Т. Алгоритмизация объектов управления: справочник / В.Т. Кулик. Киев: Наукова думка, 1968, - 364 с.

31. Лазарев, А.А. Теория расписаний. Минимизация максимального временного смещения и суммарного взвешенного числа запаздывающих требований. Научное издание / А.А. Лазарев, P.P. Садыков. Вычислительный центр им. А.А. Дородницына РАН, 2007.-180 с.

32. Литл, Д.Ж. Алгоритм для решения задачи коммивояжера / Д.Ж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы.- 1965.-Т. l.-Вып. 1.-С. 90-107.

33. Макконелл, Дж. Основы современных алгоритмов / Дж. Макконелл. М.: РИЦ «Техносфера», 2004. - 366 с.

34. Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и Телемеханика. -1989.-№9.-С. 3-33.

35. Меламед, И.И. Задача коммивояжера. Точные методы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и Телемеханика. -1989.-№Ю.-С. 3-29.

36. Меламед, И.И. Задача коммивояжера. Приближенные методы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и Телемеханика. -1989.-№11.-С. 3-20.

37. Моисеев, Н.Н. Методы оптимизации / Н.Н. Моисеев, Ю.П. Иванилов, Е.М. Столярова. М.: Наука, 1978.-352 с.

38. Пападимитриу, X. Комбинаторная оптимизация. Алгоритмы и сложность / X. Пападимитриу, К. Стайглиц. М.: Мир, 1985. - 510 с.

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

40. Сигал, И.Х. Вычислительная реализация комбинированного алгоритма ветвей и границ для задачи коммивояжера / И.Х. Сигал // ЖВМиМФ. 1986. - Т. 26. - №5. - С. 664-672.

41. Сигал, И.Х. Введение в прикладное дискретное программирование. Модели и вычислительные алгоритмы / И.Х. Сигал, А.П. Иванова. -М.: Физматлит, 2007. 304 с.

42. Танаев, B.C. Введение в теорию расписаний / B.C. Танаев, В.В. Шкурба. М. Наука, 1975.

43. Финкельштейн, Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования / Ю.Ю. Финкельштейн. М.: Наука, 1976.-264 с.

44. Хачатуров, В.Р. Аппроксимационно-комбинаторный метод и некоторые его приложения / ЖВМиМФ. 1974. - Т. 14. - №6. - С. 1464-1487.

45. Хачатуров, В.Р. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / В.Р. Хачатуров и др.. -М.: Наука, 2000.

46. Шафранский, Я.М. Об алгоритме отыскания минимума приоритетопорождающих функций на специальных множествах перестановок. I, П / Я.М. Шафранский // Изв. АН БССР. Сер. физмат, наук. 1982.-№3. - С. 38-42;- 1983.-№ 1.-С. 15-20.

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

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

49. Шкурба, В.В. Расписания, имитационное моделирование и оптимизация / В.В. Шкурба, В.М. Селивончик // Кибернетика. 1981. -№ 1.-С. 91-96.

50. Anikulmar, K.G. Neural network based priority assignment for job scheduler / K.G. Anikulmar, T. Tanprasert //AU Journal of Technology, Assumption University (AMAC) Hua Mak, Bankgkok, Thailand, 2006, Vol. 9, Number 3, pp. 181-186.

51. Coffin an, J.R. Computer and job-shop scheduling theory / J.R. Coffinan et al. John Wiley & Sons, 1976.

52. Conway R. W., Maxwell W. L., Miller L. W. Theoiy of Scheduling.— Reading, Mass.: Addison-Wesley, 1967. Русск. перев.: Копвей P. В., Максвелл В. JL, Миллер JI. В. Теория расписаний.— М.: Наука, 1975.]

53. Feldmann, M. Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches / M. Feldmann, D. Biskup //Comput. Ind. Eng., Vol. 44, No. 2, 2003, pp. 307-323.

54. Graham R.L, Lawler E.L., Lenstra J.K, Rinnooy Kan A.H.G. Optimization and approximation in deterministic sequencing and scheduling: a survey.— Annals of Discrete Math., 1979, 5, p. 287—326.

55. Gantt, H.L. A graphical daily balance in manufacture / H.L. Gantt // Transactions of the American Society of Mechanical Engineers, 1903, Volume XXIV, pp. 1322-1336.

56. Hopfield, J.J. Neural networks and physical systems with emergent collective computational capabilities / J.J. Hopfield // Proc. Nat. Acad. Sci. USA, 1982, Vol.79, pp. 2554-2558.

57. Hopfield, J.J. Neural computation of decisions in optimization problems / J.J. Hopfield, D.W. Tank // Biological Cybernetics, 1985, Vol.52, pp. 141 -152.

58. Liao, C.-J. A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date / C.-J. Liao, C.-C. Cheng // Computers and Industrial Engineering, Vol.52, No.4, 2007, pp.404-413.

59. Liao, C.-J. An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups / C.-J. Liao, H.-C. Juan // Computers & operations research, Vol. 34, No.7, 2007, pp. 1899-1909.

60. Liu, J. A modified genetic algorithm for single machine scheduling / J. Liu, L. Tang // Comput. Ind. Eng., Vol. 37, No. 1-2, 1999, pp. 43-46.

61. M'Hallah, R. Minimizing total earliness and tardiness on a single machine using a hybrid heuristic / R. M'Hallah // Computers and Operations Research, Vol.34, No. 10, 2007, pp.3126-3142.

62. Mittenthal, J. A hybrid simulated annealing approach for single machine scheduling problems with non-regular penalty functions / J. Mittenthal, M. Raghavachari, A.I. Rana // Comput. Oper. Res., Vol. 20, No. 2, 1993, pp. 103-111

63. Morin T.L. Branch-and-bound strategies for dynamic programming / T.L. Morin, R.E. Marsten // Oper. Res., 1976, Vol.24, №4, pp. 611-617.

64. Rumelhart, D.E. Learning internal representations by error propagation / D.E. Rumelhart, G.E. Hinton, R.J. Williams // Parallel Distributed Processing Vol.1 and 2 (Eds D. E. Rumelhart and J. L. McClelland), MIT Press, 1986, pp. 318-362.

65. Shen, H. Optimal Scheduling for Satellite Refueling in Circular Orbits / PhD thesis, School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, Georgia, March 2003.

66. Shen, H. Peer-to-Peer Refueling for Circular Satellite Constellations / H. Shen, P. Tsiotras // AIAA Journal of Guidance, Control, and Dynamics, Vol. 28, No. 6,2005, pp. 1220-1230.

67. Wan, G. Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties / G. Wan, В. P.-C. Yen // European Journal of Operational Research, Vol. 142, Is. 2, No.16, 2002, pp. 271-281.

68. Weiss, H.J. A Greedy Heuristic for Single Machine Sequencing with Precedence Constraints / H.J. Weiss // Management Science, Vol. 27, No.10, 1981, pp. 1209-1216.