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

• Шлюгаев, Алексей Юрьевич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Шлюгаев, Алексей Юрьевич

ВВЕДЕНИЕ.

ГЛАВА 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) легли в основу компьютерной системы поддержки принятия решений, созданной для Уфимского речного порта. Также результаты диссертационной работы внедрены в учебный процесс Волжской государственной академии водного транспорта и на факультете Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского.

Список литературы диссертационного исследования кандидат технических наук Шлюгаев, Алексей Юрьевич, 2008 год

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.