SETTING UP OF SCHEDULES IN THE TIME PLANNING TASKS
Authors:
1.
Siberian State Industrial University
(Doctor of Technical Sciences, Professor; Professor of the Department of Automation and Information Systems)
2.
Siberia State Industrial University
3.
Siberia State Industrial University
(Senior Lecturer of the Department of Automation and Information Systems)
Russian Federation
Russian Federation
4.
Siberia State Industrial University
(Senior Lecturer of the Department of Automation and Information Systems; Leading Informatization Specialist of the Department of Systems and Network Technologies)
Type:
Article
Pages:
from 103
to 111
Status:
Published
Received:
05.10.2014
Accepted:
25.10.2014
Published:
25.10.2014
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.02.021
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.02.021
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
labeling, schedule, IT-service, job shop schedule, time constraints, service management
Abstract (English):
The most important condition in the scheduling of the project activity is keeping the set time limits, which are linked to periodic intervals of work time. Classic JSSP (Job Shop Scheduling Problem) tasking did not pay enough attention to periodic intervals schedules of most organizations and enterprises. Formulation and solution of the planning problem presented in this article involves the introduction of a minimum length of time that allows the flexibility to describe the structure of periodic time constraints. The article deals with the time shift algorithm used to obtain a precise schedule in terms of periodic time intervals. Solution of this problem involves two steps: the first step is to set up a continuous schedule (Gantt chart), the second comprises its subsequent periodic adjustment to the time constraints of an arbitrary shape. The second step is used to solve the problem of shift algorithm, the computational complexity of which depends on the minimum amount of time and its dimension (duration of the project). Algorithm testing within the model-algorithmic complex on the graphs shows insignificant increase in computational complexity with a significant increase in the volume of initial data. Thus, the algorithm has a data application prospects in large-scale industrial systems of scheduling. The considered problem of scheduling is urgent for companies and organizations involved in developing and implementing the projects, IT service providers, etc. The submitted mechanisms and techniques can be used in the development of planning subsystems in various branches of science and technology (production, transportation, design-process activities).
The most important condition in the scheduling of the project activity is keeping the set time limits, which are linked to periodic intervals of work time. Classic JSSP (Job Shop Scheduling Problem) tasking did not pay enough attention to periodic intervals schedules of most organizations and enterprises. Formulation and solution of the planning problem presented in this article involves the introduction of a minimum length of time that allows the flexibility to describe the structure of periodic time constraints. The article deals with the time shift algorithm used to obtain a precise schedule in terms of periodic time intervals. Solution of this problem involves two steps: the first step is to set up a continuous schedule (Gantt chart), the second comprises its subsequent periodic adjustment to the time constraints of an arbitrary shape. The second step is used to solve the problem of shift algorithm, the computational complexity of which depends on the minimum amount of time and its dimension (duration of the project). Algorithm testing within the model-algorithmic complex on the graphs shows insignificant increase in computational complexity with a significant increase in the volume of initial data. Thus, the algorithm has a data application prospects in large-scale industrial systems of scheduling. The considered problem of scheduling is urgent for companies and organizations involved in developing and implementing the projects, IT service providers, etc. The submitted mechanisms and techniques can be used in the development of planning subsystems in various branches of science and technology (production, transportation, design-process activities).
Keywords:
labeling, schedule, IT-service, job shop schedule, time constraints, service management
labeling, schedule, IT-service, job shop schedule, time constraints, service management
Введение Составление календарных графиков проведения работ имеет большое прикладное значение в управлении деятельностью человеческих коллективов, организаций и предприятий. Нами рассматриваются механизмы решения на компьютере одной из задач класса 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 (data obrascheniya: 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. Dobrynin A. S. Formalizaciya zadachi sostavleniya raspisaniy dlya stadii vnedreniya IT-servisa / A. S. Dobrynin, S. M. Kulakov, V. V. Zimin // Nauchnoe obozrenie: teoriya i praktika. 2013. № 2. S. 47-52, 110.
5. Dobrynin A. S. O formirovanii kompleksa instrumental'nyh sredstv IT-provaydera dlya postroeniya raspisaniy processa vnedreniya servisa / A. S. Dobrynin, S. M. Kulakov, V. V. Zimin, N. F. Bondar' // Nauchnoe obozrenie. 2013. № 8. S. 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.
