ФОРМИРОВАНИЕ РАСПИСАНИЙ В ЗАДАЧАХ ВРЕМЕННОГО ПЛАНИРОВАНИЯ
Авторы:
1.
Сибирский государственный индустриальный университет
(д-р техн. наук, профессор; профессор кафедры автоматизации и информационных систем)
2.
Сибирский государственный индустриальный университет
3.
Сибирский государственный индустриальный университет
(старший преподаватель кафедры автоматизации и информационных систем)
Россия
Россия
4.
Сибирский государственный индустриальный университет
(старший преподаватель кафедры автоматизации и информационных систем; ведущий специалист по информатизации отдела системных и сетевых технологий)
Тип:
Статья
Страницы:
с 103
по 111
Статус:
Опубликован
Получено:
05.10.2014
Одобрено:
25.10.2014
Опубликовано:
25.10.2014
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.02.021
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.02.021
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
распределение работ, расписание, ИТ-сервис, планирование работ, временные ограничения, сервисное управление
Аннотация (русский):
Важнейшим условием составления расписаний в проектной деятельности является учет множества временных ограничений, которые привязаны к периодическим интервалам времени проведения работ. В классических постановках задач класса JSSP (Job Shop Scheduling Problem) не уделяется должное внимание периодическим интервалам времени графиков работ большинства организаций и предприятий. Постановка и решение задачи планирования, предлагаемые нами, предполагают введение минимального отрезка времени, что позволяет гибко описывать структуру периодических временных ограничений. Рассматривается алгоритм временного сдвига, используемый для получения точного расписания в условиях периодических временных интервалов. Решение задачи подразумевает два этапа: на первом осуществляется построение непрерывного расписания (диаграмма Ганта), на втором происходит его последующая корректировка с учетом периодических временных ограничений произвольной формы. На втором этапе используется описанный алгоритм сдвига, вычислительная сложность которого зависит от минимального интервала времени и его размерности (длительности проекта). Апробация алгоритма в рамках модельно-алгоритмического комплекса на графах показывает несущественный рост сложности вычислений при значительном увеличении объема исходных данных. Таким образом, данный алгоритм имеет перспективы применения в крупных промышленных системах составления расписаний. Рассматриваемая задача планирования работ актуальна для предприятий и организаций, участвующих в разработке и внедрении проектов, поставщиков ИТ-услуг и т. д. Представленные механизмы и методики могут использоваться при разработке подсистем планирования в различных отраслях науки и техники (производство, транспорт, проектно-процессная деятельность).
Важнейшим условием составления расписаний в проектной деятельности является учет множества временных ограничений, которые привязаны к периодическим интервалам времени проведения работ. В классических постановках задач класса JSSP (Job Shop Scheduling Problem) не уделяется должное внимание периодическим интервалам времени графиков работ большинства организаций и предприятий. Постановка и решение задачи планирования, предлагаемые нами, предполагают введение минимального отрезка времени, что позволяет гибко описывать структуру периодических временных ограничений. Рассматривается алгоритм временного сдвига, используемый для получения точного расписания в условиях периодических временных интервалов. Решение задачи подразумевает два этапа: на первом осуществляется построение непрерывного расписания (диаграмма Ганта), на втором происходит его последующая корректировка с учетом периодических временных ограничений произвольной формы. На втором этапе используется описанный алгоритм сдвига, вычислительная сложность которого зависит от минимального интервала времени и его размерности (длительности проекта). Апробация алгоритма в рамках модельно-алгоритмического комплекса на графах показывает несущественный рост сложности вычислений при значительном увеличении объема исходных данных. Таким образом, данный алгоритм имеет перспективы применения в крупных промышленных системах составления расписаний. Рассматриваемая задача планирования работ актуальна для предприятий и организаций, участвующих в разработке и внедрении проектов, поставщиков ИТ-услуг и т. д. Представленные механизмы и методики могут использоваться при разработке подсистем планирования в различных отраслях науки и техники (производство, транспорт, проектно-процессная деятельность).
Ключевые слова:
распределение работ, расписание, ИТ-сервис, планирование работ, временные ограничения, сервисное управление
распределение работ, расписание, ИТ-сервис, планирование работ, временные ограничения, сервисное управление
Введение Составление календарных графиков проведения работ имеет большое прикладное значение в управлении деятельностью человеческих коллективов, организаций и предприятий. Нами рассматриваются механизмы решения на компьютере одной из задач класса JSSP (Job Shop Scheduling Problem) [1-3], которая заключается в распределении работ во времени при наличии временных ограничений. Временные ограничения формируются естественно - исходя из периодических графиков проведения работ, используемых при организации труда сотрудников. Рассматриваемая задача планирования работ актуальна для предприятий и организаций, участвующих в разработке и внедрении проектов, поставщиков ИТ-услуг и т. д. Представленные механизмы и методики могут использоваться при разработке подсистем планирования в различных отраслях науки и техники (производство, транспорт, проектно-процессная деятельность). Формализация задачи Рассматривается задача, в которой известны перечень работ, длительность и последовательность их выполнения. Базовая задача построения производственных расписаний [4] для непрерывного времени формализуется как задача на графах (сетях), в которой узлы представляют собой события, дуги - отдельные процессы или работы. Особый интерес представляет задача, в которой необходимо учитывать ограничения, связанные с невозможностью распределить работы в определенный интервал времени, что характерно для практических ситуаций на большинстве производств. Сложность заключается в вариативном характере таких ограничений, которые могут изменяться в различных постановках. Рассмотрим частную JSSP-постановку для общего случая, полагая, что на периодических интервалах времени (рабочая неделя, месяц) структура ограничений существенно не меняется. Дано: 1. Вектор работ (процессов) , для которых справедливы принципы: а) композиции или агрегирования, когда отдельная работа (процесс) может включать в себя перечень более простых работ (процессов) ; и наоборот, более мелкие работы или процессы могут укрупняться; б) связности, когда для двух различных процессов и справедливо соотношение (1) 2. Орграф, характеризующий последовательность выполнения работ , и его информационная модель . 3. Нормативная, согласованная минимальная, средняя и максимальная длительность отдельных работ (процессов) Tmin, Tmax, Tavg.. 4. Минимальный нормативный «оконный» интервал времени (временной слот), характеризующий отрезок непрерывного времени , кратный производственным графикам работ. 5. Временные ограничения, связанные с периодичностью выполнения работ трудовым коллективом, представленные в виде матрицы работ и простоев. В задачах построения производственных расписаний целесообразно использовать интерпретацию, когда известно, что производственные процессы четко привязаны к конкретным дням недели: (2) 6. Критерий оптимальности. Минимизация совокупного времени выполнения всех процессов. Пусть ребро орграфа между смежными вершинами связано с отрезком времени , который характеризует продолжительность процесса (работы). Тогда, на основе выражения (1), справедливо выражение . (3) Требуется: 1. Построить расписание работ во времени для непрерывного случая, т. е. фактически получить и визуализировать вектор кортежей каждый элемент которого содержит связанную с работой временную информацию. . 2. Найти наиболее ранние и наиболее поздние моменты времени начала и завершения каждой работы. 3. Определить критический путь в графе. 4. Построить расписание в условиях временных ограничений с использованием критерия (3). Подходы к решению Реализация полноценных инструментов решения представленной задачи на компьютере создает трудности, поскольку необходимы алгоритмы решения в общем виде, в том числе с использованием конструкторов графов (сетей). Для решения задачи используется модельно-алгоритмический комплекс [5], написанный на языке программирования C# - WPF, который предусматривает три уровня взаимодействия моделей и алгоритмов. 1. Базовый уровень моделей, который включает в себя структуры данных графа (узел, дуга, граф и т. д.). 2. Уровень промежуточных алгоритмов, который предусматривает реализацию низкоуровневых алгоритмов, таких как быстрая сортировка узлов графа в зависимости от положения в топологии (алгоритм Форда - Фалкерсона). 3. Уровень алгоритмов, включая алгоритмы визуализации, поиска критического пути на графе, построения расписаний. Все уровни модельно-алгоритмического комплекса связаны друг с другом «слабой» связью посредством интерфейсов, что позволяет при необходимости заменять отдельные компоненты решения другими. Решение представленной задачи включает два основных этапа: 1. Построение расписания работ без учета временных ограничений (получение вектора кортежей работ в привязке к непрерывному времени и его визуализация). 2. Построение расписания, с учетом временных ограничений, представленных выражением (2) в постановке задачи. Механизм решения задачи Комплексное решение задачи на компьютере включает в себя следующие основные этапы. 1. Топологическая сортировка узлов графа (модификация алгоритма Форда - Фалкерсона) , в результате которой вектор узлов сортируется в порядке, определяемом компаратором. Упорядочение вершин бесконтурного ориентированного графа осуществляется согласно частичному порядку, заданному ребрами орграфа на множестве его вершин. 2. Определение начальной и конечной вершины графа как первого и последнего узла , вектора отсортированных узлов графа. 3. Определение «критического» пути в графе. Критический путь определяется с помощью алгоритма, рассмотренного в [5]. 4. Определение раннего срока свершения события как раннего срока, необходимого для выполнения всех работ, предшествующих данному событию : где - ранний срок свершения события ; - продолжительность (вес) работы соответственно между событиями ; - множество работ (направленных дуг), входящих в событие . 5. Определение позднего срока свершения события как наиболее позднего момента времени, после которого остается столько времени до критического срока, сколько необходимо для завершения всех работ, следующих за этим событием: 6. Определение резерва времени события в соответствии с выражением 7. Определение полного резерва времени для работы - по сути, максимального количества времени, на которое можно задержать выполнение работы или увеличить ее продолжительность, не изменяя длительность критического срока. 8. Определение свободного резерва времени для работы - максимального количества времени, на которое можно увеличить продолжительность данной работы, не изменяя при этом начальных сроков последующих работ при условии, что предшествующее событие наступило в свой срок. 9. Построение расписания в условиях временных ограничений (алгоритм сдвига). Сдвиг всех временных характеристик работ в условиях невозможности их размещения на интервалах времени . Ключевые идеи алгоритма временного сдвига Процедура временного сдвига, используемая в алгоритме последовательного распределения работ, позволяет повысить точность построения расписаний при переходе от непрерывного к дискретному времени, когда определенные интервалы времени не могут быть использованы для планирования. Работа крупных технологических агрегатов и производств часто связана с наличием временных интервалов, которые желательны (или нежелательны) для проведения работ проектной деятельности. Например, развертывание программного обеспечения на предприятиях должно осуществляться в интервалы времени, свободные от производственной деятельности, которые формируются как , где - количество минимальных отрезков времени. Рассматриваемый нами механизм временного сдвига позволяет учитывать производственные простои для более точного распределения работ в задачах планирования. Основой для работы алгоритма временного сдвига является непрерывное расписание , которое может быть представлено вектором кортежей (набором записей) . Элемент набора записей (запись) , полученный в ходе решения рассмотренной выше задачи, содержит поля, такие как идентификатор работы (ID), дата начала (beginDate), дата раннего окончания (earlyEndDate), дата позднего окончания (lastEndDate), компонент временного смещения (offsetDate). С точки зрения процедуры составления расписаний отдельный кортеж (запись) представляет набор связанных данных по отношению к некоторому идентификатору работы, часть из которых используется алгоритмом построения расписаний. Важнейшим элементом математической модели является также логическая матрица работ и простоев , формируемая с учетом окна планирования, которая описывает временную сетку интервалов проведения работ такую, что Для случаев описания детальных временных компонент матрица работ и простоев может быть трансформирована в кортеж работ и простоев (преобразована из пространственной в табличную форму). В общем случае структура и вид матрицы или кортежа зависят от размерности времени, требуемой точности задания отрезков времени и динамики процессов. В задачах построения производственных расписаний целесообразно использовать «сжатую» интерпретацию, когда известно, что производственные процессы четко привязаны к конкретным дням недели: Введем понятие левого и правого временного сдвига, которое будет означать единичное приращение минимальной компоненты кортежа в сторону уменьшения или увеличения времени. Таким образом, для кортежа сдвигом будет кортеж . Рассматриваемый нами алгоритм назначения работ (time - labeling) использует модель ограничений, представленных выражением (2). Введем понятия «окрестности слева и справа» для работы , которые означают все работы, входящие в начальное событие (слева), и работы, выходящие из конечного события (справа). Для упрощения понимания сути работы алгоритма в целом выделим несколько ключевых идей: 1. Двухкомпонентный, двунаправленный временной итерационный механизм. Итератор workIterator сдвигает временной кортеж в прямом направлении, итератор durationIterator сдвигает временной кортеж в обратном направлении (рис. 1). 2. Механизм сдвига, с учетом смещения, непосредственно влияющий на окрестность работ , расположенных справа относительно текущей работы . Возможность поиска работ, расположенных в окрестности текущей справа или слева, достигается за счет реализации в информационной модели дуги графа ссылок на стартовый и конечный узел. Рис. 1. Двунаправленная итерация по времени 3. Механизм временной разметки (time-labeling) с использованием списка запретов. Суть итерационного механизма заключается в следующем: если на очередном -шаге итерации элемент кортежа для работы не может быть распределен, происходит сдвиг всех временных характеристик работ окрестности справа , с учетом смещения для следующей работы, на интервал времени , если он отсутствует в списке запретов. В противном случае длительность текущей работы уменьшается на интервал времени , при этом сдвига временных характеристик работ окрестности справа не происходит. Так как имеется -работ окрестности слева для текущей работы , итерирование каждой из которых приводит к сдвигам , целесообразно использовать список запретов, каждый элемент которого представляет собой кортеж . Список запретов создается отдельно для каждой работы wi и содержит даты, которые уже использовались ранее для сдвига работы . Блок-схема алгоритма временного сдвига Представленная в данном разделе блок-схема алгоритма реализована в рамках модельно-алгоритмического комплекса (МАК) построения расписаний [5] (рис. 2). Большой вклад в теорию и практику решения задач составления расписаний внесли российские ученые В. С. Танаев, Ю. Н. Сотсков, В. А. Струсевич, А. В. Куренков, Ю. С. Быков, Г. Б. Рубальский и др. В течение последних лет защищен ряд диссертаций, посвященных задачам разработки производственных и учебных расписаний, среди которых можно выделить работы молодых ученых С. В. Веревкина, К. С. Галузина, С. А. Костина, О. Н. Лопатеевой, Макарцевой, Г. Ф. Назимовой и др. Следует также отметить большой вклад зарубежных специалистов в исследование данной проблематики. Мировую известность получили работы таких ученых, как Р. В. Конвей, В. Л. Максвелл, Л. В. Миллер; М. В. Картер, E. Берк, A. Schaerf, De Werra и др. Рис. 2. Блок-схема алгоритма разметки (labeling) работ Метод последовательного распределения для простейших задач предусматривает сдвиг всех работ, расположенных после текущей, что в значительной мере повышает его вычислительную сложность. Адаптация алгоритма, рассматриваемого нами, предполагает воздействие непосредственно на подмножество работ, следующих за текущей, что позволяет на практике понизить вычислительную сложность предлагаемого алгоритма. Эвристические (метаэвристические) методы, такие как метод обратного хода, ветвей и границ, применяются, как правило, для решения NP-трудных задач, для которых не найдено быстрое и точное решение. В значительной степени большинство эвристических процедур опирается на имитацию человеческого мышления, природные процессы и элементы теории вероятности (генетические алгоритмы [6], методы «муравьиной колонии» [7], имитация «отжига», поиск с запретами [8]). Поскольку большинство эвристических алгоритмов в процессе поиска использует элементы «нечеткой логики», вычислительная сложность их выше, чем у предлагаемого алгоритма (рис. 3). Рис. 3. Вычислительная сложность алгоритма Алгоритм, апробированный на различных модельных структурах графов, позволяет получить точное решение задачи за конечное время (рис. 3). Представленная задача не является NP-трудной, что позволяет получать решения при больших объёмах входных данных (графов большой размерности) без использования эвристических поисковых процедур. При разработке и тестировании использовалось следующее аппаратное обеспечение: Intel Core Quad 1,5 ГГц/ 4 Гб ОЗУ/160 Гб; программное обеспечение: MS Windows 7, MS Dot Net Framework 4.5, WPF C#. Заключение Таким образом, нами рассмотрены постановка и решение одной из задач планирования, которая является актуальной для организаций, осуществляющих проектную деятельность. Приведена структура временных ограничений, которая позволяет уточнять временные интервалы с учётом периодических графиков работ (неделя, месяц и т. д.), используемых в большинстве практических случаев. Предлагаемый подход позволяет решать задачу в общем виде для любых структур исходных данных с использованием конструктора графов. Алгоритм был протестирован; получены результаты для диапазона вершин графа от 10 до 100 при произвольных связях между ними. Предложенный алгоритм показал лучшую производительность по сравнению с другими известными решениями, что открывает перспективы его использования в задачах планирования. Развитие предлагаемых идей подразумевает построение крупных информационных систем управления проектами с возможностью ресурсно-ролевого управления активами на всех стадиях жизненного цикла систем.
1. Job shop scheduling // URL: http://en.wikipedia.org/wiki/Job_shop_scheduling (дата обращения: 03.05.2014).
2. Karger D. A Better Algorithm for an Ancient Scheduling Problem / D. Karger, S. Phillips, E. Torng // Proc. Fifth ACM Symp. Discrete Algorithms. 1994.
3. Garey M. R. The Complexity of Flowshop and Jobshop Scheduling / M. R. Garey // Mathematics of Operations Research. 1976. 1 (2). P. 117-129. doihttps://doi.org/10.1287/moor.1.2.117. JSTOR 3689278.
4. Добрынин А. С. Формализация задачи составления расписаний для стадии внедрения ИТ-сервиса / А. С. Добрынин, С. М. Кулаков, В. В. Зимин // Научное обозрение: теория и практика. 2013. № 2. С. 47-52, 110.
5. Добрынин А. С. О формировании комплекса инструментальных средств ИТ-провайдера для построения расписаний процесса внедрения сервиса / А. С. Добрынин, С. М. Кулаков, В. В. Зимин, Н. Ф. Бондарь // Научное обозрение. 2013. № 8. С. 93-101.
6. Burke E. A Genetic Algorithm for University Timetabling / E. Burke, D. Elliman, R. Weare // Proceedings of the AISB workshop on Evolutionary Computing, University of Leeds, 1994.
7. Colorni A. Distributed Optimization by Ant Colonies / A. Colorni, M. Dorigo, V. Maniezzo // Actes de la première conférence européenne sur la vie artificielle. Paris, France, Elsevier Publishing, 1991. P. 134-142.
8. Glover F. Tabu search // Modern Heuristics Techniques for Combinatorial Problem. C. R. Reeves (ed.), Scientific Publications, Oxford, 1989.
