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

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Об авторе

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

Специалист по исследованию операций, теории расписаний, математическому моделированию и оптимизации. Опубликовал свыше 220 научных статей по этой тематике в центральных международных журналах; автор 8 монографий и книг. Среди последних работ — монографии "Принятие многокритериальных решений" (2011) и "Прикладные задачи теории расписаний и маршрутизации перевозок" (2012). До 1995 г. работал в Киеве в должности заведующего отделом в научно-исследовательских институтах сельскохозяйственного машиностроения, робототехники, а также в Украинском отделении Всемирной лаборатории ("World Lab Ukrainian Branch"). C 1995 г. живет в Германии. Работал в Европейском центре мехатроники. В настоящее время — научный консультант; выполнял проекты для различных частных фирм и университетов.