URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Зак Ю.А. Прикладные задачи теории расписаний и маршрутизации перевозок
Id: 124844
 
439 руб.

Прикладные задачи теории расписаний и маршрутизации перевозок

URSS. 2012. 394 с. Мягкая обложка. ISBN 978-5-397-02359-7.

 Аннотация

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

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

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


 Оглавление

Введение
Глава 1. Постановки и математические модели задач теории расписаний
 1.1. Основные понятия и определения. Круг решаемых проблем
 1.2. Формы организации производства
 1.3. Критерии оптимальности и ограничения
 1.4. Классификация задач теории расписаний
 1.5. Виды математических моделей задач теории расписаний и маршрутизации перевозок
 1.6. Формы представления расписаний
Глава 2. Математический аппарат описания и общая характеристика методов решения задач теории расписаний
 2.1. Общая характеристика методов и проблемы сложности
 2.2. Графы и деревья
 2.3. Методы целочисленного математического программирования
 2.4. Динамическое программирование
 2.5. Метод ветвей и границ
 2.6. Методы локального и глобального случайного поиска
 2.7. Генетические алгоритмы и эволюционные стратегии
 2.8. Эвристические методы
Глава 3. Математические модели и алгоритмы построения расписаний выполнения работ на одной машине
 3.1. Классификация задач построения расписаний выполнения работ на одной машине
 3.2. Минимизация штрафов за превышение директивных cроков завершения выполнения заданий
 3.3. Минимизация суммарных потерь времени на переналадки оборудования
 3.4. Выполнение расписаний в кратчайшие сроки в  условиях отсутствия ограничений на сроки завершения заданий
 3.5. Построение допустимых и оптимальных по быстродействию расписаний в условиях ограничений на сроки и частичные порядки выполнения заданий
 3.6. Алгоритмы построения допустимых и оптимальных по времени завершения выполнения расписаний в условиях ограничений на частичные порядки и граничные сроки выполнения заданий
 3.7. Иллюстративные примеры построения допустимых и оптимальных по времени завершения выполнения расписаний на одной машине
Глава 4. Распределение заданий и определение оптимальных оче- редностей их выполнения на параллельных машинах
 4.1. Постановки и практические приложения рассматри- ваемых задач
 4.2. Математическая модель задачи. Свойства допустимых и оптимальных расписаний
 4.3. Алгоритмы решения задачи
 4.4. Вычислительная схема метода ветвей и границ
 4.5. Алгоритм решения задачи методами динамического программирования
Глава 5. Flow-Shop-Probleme. Построение расписаний выполнения n заданий на m машинах при установленной и одинаковой для всех заданий очередности выполнения операций
 5.1. Постановки и математические модели задачи
 5.2. Алгоритмы решения задачи Джонсона для случая
 5.3. Свойства допустимых и оптимальных расписаний
 5.4. Точные методы решения задачи
 5.5. Основные эвристики и решающие правила для построения приближенных методов решения
 5.6. Методы локальных вариаций
 5.7. Алгоритмы приближенных методов решения
 5.8. Результаты вычислительных экспериментов
Глава 6. Построение расписаний выполнения N заданий на m машинах при различной и для каждого из заданий очередности следования операций (Job-Shop-Problem)
 6.1. Постановка задачи
 6.2. Математическая модель задачи
 6.3. Математическая модель задачи в виде задачи билинейного булевого программирования
 6.4. Свойства допустимых и оптимальных расписаний
 6.5. Алгоритмы точных методов решения задачи
 6.6. Иллюстративные примеры
 6.7. Приближенные методы решения задачи
Глава 7. Организация и синхронизация работы сборочного и конвейерного производства
 7.1. Прикладные аспекты и классификация проблем балансировки конвейерных линий
 7.2. Постановка и математические модели задачи
 7.3. Свойства допустимых и оптимальных решений задач
 7.4. Алгоритмы решения задач
 7.5. Иллюстративные примеры
 7.6. Методы динамического программирования и эвристические методы решения задачи
Глава 8. Построение расписаний программных движений промышленных роботов
 8.1. Постановка задачи, практические приложения и состояние проблемы
 8.2. Определение времен перехода и параметров рабочих звеньев ПР при переориентации рабочего органа из одной точки в другую
 8.3. Построение и свойства матрицы временных затрат на выполнение технологических операций и пере- ходов ПР с одной рабочей позиции на другую
 8.4. Свойства допустимых и оптимальных расписаний
 8.5. Алгоритм решения задачи
 8.6. Иллюстративный пример
Глава 9. Оптимальное распределение грузопотоков в транспортных сетях
 9.1. Практические приложения рассматриваемых задач
 9.2. Постановка и математические модели рассматриваемых задач
 9.3. Методы декомпозиции и приближенные методы решения общей проблемы
 9.4. Свойства допустимых и оптимальных решений задач
 9.5. Алгоритмы точных методов решения задач
 9.6. Иллюстративный пример решения задачи оптимизации почтовых перевозок
 9.7. Алгоритмы глобального случайного поиска в  задачах оптимизации потоков почтовых перевозок
Глава 10. Математические модели задач теории расписаний в условиях неопределенности
 10.1. Показатели эффективности расписаний в условиях стохастических данных о временах выполнения операций и переналадок оборудования
 10.2. Показатели эффективности расписаний в условиях, если данные о временах выполнения операций и переналадок оборудования представлены Fuzzy-числами
 10.3. Экстремальные допустимые пути в стохастических и Fuzzy-графах
 10.4. Алгоритм решения задачи определения допустимых и оптимальных путей в графах
 10.5. Стохастический анализ работы конвейерных линий Литература

 Введение

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

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

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

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

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

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

-- директивные сроки начала и завершения выполнения каждого задания,.

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

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

В качестве основных мер эффективности наиболее часто рассматриваются следующие показатели:

-- время завершения всего комплекса работ (длина расписания),

-- суммарное средневзвешенное время и (или) стоимость использования ресурсов,

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

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

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

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

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

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

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

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

-- при определении очерёдности и календарных планов обслуживании клиентов,

-- в планировании последовательности выполнения вычислений в многопроцессорных вычислительных системах.

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

Задачи теории расписаний можно разделить на 2 группы:

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

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

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

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

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

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

-- комбинаторные подходы;

-- динамическое программирование и методы анализа и отсева вариантов;

-- методы ветвей и границ;

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

-- генетические алгоритмы и эволюционные стратегии;

-- эвристические методы.

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

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

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

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

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

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

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

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

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

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

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

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

Автор выражает благодарность своей жене Наталье Гейлур за помощь в редактировании и оформлении материала.


 Об авторе

Юрий Александрович ЗАК

Специалист по исследованию операций, математическому моделированию и оптимизации. Автор 8 монографий и книг, более 200 научных статей по этой тематике, в том числе более 25 публикаций в центральных международных журналах по теории расписаний. Среди последних работ автора -- монография "Принятие многокритериальных решений" (2011). Работал в Киеве в должности заведующего отделом научно-исследовательских институтов целлюлозно-бумажной промышленности, сельскохозяйственного машиностроения, робототехники, в украинском отделении Всемирной лаборатории "World. Lab. Ukrainen Branch". Преподавал в высших учебных заведениях. С 1995 г. живет в Германии. Работал в "Европейском центре по мехатронике", выполнял на договорных условиях проекты для различных частных фирм и университетов.

 
© URSS 2016.

Информация о Продавце