Задачи расписания являются задачами формирования и оптимизации процесса обслуживания конечного множества требований (заявок) на осуществление действий (работ, событий, операций) в системе с ограниченными ресурсами. Для каждого требования в качестве исходных данных указываются допустимые наборы ресурсов и, при необходимости, требуемые объемы каждого ресурса. Расписание обслуживания требований – это однозначное отображение, в котором каждому требованию в определенный промежуток времени ставится действие с задаваемым или определяемым набором ресурсов.
Многокритериальная природа задач оптимизации расписаний породила множество эвристик для своего решения [9]. Один из способов нахождения эвристических подходов связан с использованием нетривиальных графических представлений [1, 2]. Анализ этих представлений базируется на механизмах наглядно-образного мышления. В статье рассматриваются программно формируемые изображения расписаний, представляющие визуальную информацию о распределении ресурсов системы в интервале расписания.
Целью статьи является представление эвристических подходов к оптимизации расписаний на основе анализа их визуализации.
Программное решение задач расписания использует двухэтапный подход [3] – формирование начального расписания и его последующую оптимизацию. Начальное расписание – любое расписание, удовлетворяющее обязательные ограничения. На обоих этапах необходима визуализация одним изображением всего расписания для его качественного анализа. Изображение расписания представляет распределение ресурсов системы во времени в пределах интервала расписания. Анализ визуализации начального расписания позволяет определить подходы по его оптимизации, а визуализация получаемого расписания дает возможность оценки выдвинутых гипотез.
Рис. 1. Начальное расписание занятий ВУЗ’а
Рассмотрим расписание занятий ВУЗ’а, в котором распределяются три вида ресурсов – группы студентов, преподаватели и аудитории. На рис. 1 представлены результаты программного формирования начального расписания 927 занятий для 50 групп ВУЗ’а [7].
На рис. 1 представлено распределение одного из ресурсов системы – групп студентов в пределах двухнедельного интервала расписания. Занятия каждой группы для одной «пары» обеих недель расписания находятся одно под другим. Цветом представлены различные виды занятий: красный – лекционные, голубой – практические, зеленый – лабораторные. Компактность представления позволяет охватить одним взглядом получаемые результаты и сформировать некоторые выводы.
Главными потребителями расписания занятий являются студенты, поэтому начальное расписание (рис. 1) для них неудобно. Во-первых, количество занятий у групп в разные дни недели колеблется от одного до четырех. Во-вторых, различие во временах начала первого занятия в разные дни. В-третьих, различие в количестве занятий одного и того же дня в разных неделях расписания. Эти соображения позволили сформулировать оценки равномерности занятий групп, на основании которых формируются критерии равномерности занятий расписания и стратегия оптимизации начального расписания [4]. На рис. 2 представлены результаты программной оптимизации начального расписания. Визуальное сопоставление показывает устранение большинства перечисленных недостатков.
Взаимной перестановкой занятий оптимизированного расписания (рис. 2) возможно решение вторичных задач – удовлетворение пожеланий преподавателей и эффективность использования аудиторного фонда. Неоднородность ресурсов – конкретность групп, преподавателей и аудиторий не дает возможности формирования интегральной оценки распределения ресурсов в расписании занятий ВУЗ’а.
Для транспортных систем в отличие от учебных заведений невозможно формирование представлений расписаний всей системы. Движение транспорта порождает несколько видов расписаний для разных видов ресурсов системы. Расписание движения конкретного транспортного средства можно представить вектором времен прибытия/отправления в различных пунктах остановок. Транспортное расписание движения транспорта через конкретный пункт остановки, как правило, является табличным представлением времен прибытия/отправления. Необходимым является расписание движения транспортных средств между отдельными пунктами остановок. Для транспортных систем формируются рабочие графики персонала – экипажей самолета, локомотивных бригад и т.п.
Рис. 2. Оптимизированное расписание занятий ВУЗ’а
Для расписаний пунктов остановок и перегонов между ними использованы спиральные представления (рис. 3), в которых спираль является временной осью, а ее длина равна интервалу расписания. Виток спирали – наименьший период расписания. Пометками на спирали возможно представление прибытия/отправления транспортного средства.
Рис. 3. Начальное расписание станции
На рис. 3 представлено программно полученное начальное расписание пассажирского транспорта через наиболее загруженную станцию железнодорожной сети тестового задания [8]. Показанное расписание является недельным, а каждый виток спирали последовательно представляет суточные расписания. Первый внутренний виток представляет расписание понедельника. Голубым цветом представлены прибытия/отправления на станцию одного поезда, желтым – двух поездов, одновременно находящихся на станции. В правом верхнем углу указана величина среднеквадратичного отклонения от среднего интервала прибытий/отправлений на станцию.
Анализ рис. 3 приводит к выводу о необходимости обеспечения равномерного использования ресурсов станции. Достижение равномерного использования ресурсов станции возможно обеспечением равных интервалов прибытия поездов. Введением среднеквадратичного отклонения от среднего интервала в качестве оценок равномерности станции и критериев равномерности поезда по всем станциям маршрута возможен выбор самого неравномерного поезда [5]. Для этого поезда в пределах суток определяется время отправления с начальной станции с помощью многовекторного ранжирования критериев равномерности по всем станциям и перегонам маршрута. На рис. 4 представлено программно полученное оптимизированное расписание с двукратным уменьшением отклонения.
Рис. 4. Оптимизированное расписание станции
Для представления расписания (календарного графика) в планировании проектов и мультипроектном планировании в большинстве случаев используются диаграммы Гантта, с помощью которых представляют временные последовательности выполнения проектов и работ отдельных проектов. В зависимости от предметной области применяют различные план-графики распределения ресурсов.
Для численных экспериментов мультипроектного планирования использовались случайно выбранные из библиотеки тестовых задач PSPLib [10] 15 проектов. Проекты включают по 30 работ, и им необходимы 4 типа ресурсов. На рис. 5 показаны результаты программного формирования начального календарного графика мультипроектного планирования как расписания для сетевых структур заявок при принятом интервале расписания и принятых агрегациях проектов [6].
В верхней части рисунка находится диаграмма Гантта для 15 выбранных проектов при принятом интервале расписания в 100 тактов планирования. В нижней части рис. 5 показаны диаграммы потребления (синий цвет) и выделения (голубой цвет) каждого из четырех ресурсов на каждом такте планирования. Цифрами в диаграммах ресурсов представлены максимальные значения тактового потребления и выделения ресурса. Третья цифра показывает среднеквадратичное отклонение в % % от среднего значения, показанного красной линией. Выделение запланированных ресурсов каждому проекту осуществлялось в пределах их выполнения, что обусловило ступенчатый характер соответствующих диаграмм (рис. 5).
Рис. 5. Начальный календарный график мультипроектного планирования
Рис. 6. Оптимизированный календарный график
Для принятия решений о стратегии оптимизации начального календарного графика (рис. 5) использован факт значительной неравномерности потребления ресурсов внутри интервала расписания. Соображения экономической эффективности требуют необходимости достижения равномерного потребления ресурсов в интервале расписания. Это приводит к оценкам равномерности календарного графика по каждому из ресурсов – среднеквадратичному отклонению от среднего значения потребления ресурса в интервале расписания. Вектор из четырех оценок по ресурсам образует критерий неравномерности календарного графика. Выявление самого неравномерного проекта и нахождение для него наиболее благоприятного времени начала в пределах интервала расписания путем ранжирования критерия равномерности – такова стратегия каждого цикла оптимизации. На рис. 6 представлен оптимизированный календарный график.
Заключение
Авторы считают, что новыми являются следующие положения и результаты:
- осуществлена визуализация различных видов расписаний;
- сформулированы общие подходы к оптимизации начальных расписаний;
- представлены результаты оптимизации начальных расписаний различных типов.