«Информационные Ресурсы России» №4, 2014

Введение
Статья рассматривает вариант реализации алгоритма распределения работ в условиях временных ограничений. В работе [2] рассматривались вопросы реализации модельно-алгоритмического комплекса при построении расписаний планирования работ и операций для непрерывного времени. Создание конструктора графов, реализация базовых алгоритмов поиска путей и визуализации графов позволяет решать более сложные задачи. Рассматриваемый в статье алгоритм предполагает, что задача сетевого планирования для непрерывного времени [1] уже решена на компьютере [2] (технология WPF – C#), для любых, сколь угодно сложных структур орграфа. Однако практические требования чаще всего предполагают невозможность планирования на непрерывных временных интервалах. Длительность смены рабочих коллективов ограничена, деятельность людей на производстве, осуществляется в определенные моменты времени. Необходимость точного планирования, учета графиков рабочего времени людей и других факторов, таких как загруженность эксплуатационной среды, приводят к появлению временных ограничений в постановке задачи временного планирования. Вариант реализации алгоритма построения расписаний (графиков работ) для временных ограничений произвольного вида рассматривается здесь.

Элементы математической модели
Базовая задача построения производственных расписаний [1] для непрерывного времени формализуется как задача на графах, в которой узлы представляют собой события, дуги – отдельные процессы или работы. С каждой дугой ассоциирован двухкомпонентный вес, представленный вещественным числом и временной разницей c возможностью их взаимного отождествления. Этапы решения базовой задачи [1] реализованы в рамках модельно-алгоритмического комплекса (МАК) [2] и дают неплохие результаты на практике.

Особый интерес представляет задача, в которой необходимо учитывать ограничения, связанные с невозможностью выполнять работы в определенные отрезки времени. Сложность заключается в вариативном характере таких ограничений, которые могут изменяться в различных постановках. Рассмотрим элементы математической модели для достаточно общего случая, предполагая, что на периодических интервалах времени t+▲t структура ограничений одинакова.

Ключевые механизмы алгоритма

Для упрощения понимания сути алгоритма выделим несколько ключевых механизмов:
1) Двухкомпонентный, двунаправленный механизм временных итераций (МВИ).
Итератор workIterator сдвигает временной кортеж в прямом направлении, итератор durationIterator сдвигает временной кортеж в обратном направлении, см. рис. 1.

Рис. 1. Схема двунаправленных итераций по времени

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

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

Листинг 1. Информационная модель дуги графа

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

Рис. 2. Подмножества сдвига при итерационном движении

3) Механизм временной разметки – МВР, (time-labeling) c использованием списка запретов.

 

Блок-схема алгоритма

Представленная в данном разделе блок-схема построена с опорой на процесс отладки работающей версии на языке программирования C# в рамках модельно-алгоритмического комплекса (МАК) построения расписаний [2]. Алгоритм был опробован на 10 тестовых структурах графов при произвольной генерации значений для матрицы временных ограничений. Блок схема представлена на рис. 3.

Заключение
В ходе проведенного исследования был разработан и реализован алгоритм построения расписаний для задач календарного планирования работ, учитывающий временные ограничения. Результаты исследования закреплены авторскими свидетельствами и правами на интеллектуальную собственность. Практическая значимость заключается в возможности применения результатов исследования в следующих сферах деятельности:
1) управление проектами и планирование;
2) построение расписаний работ крупных промышленных комплексов и технологических агрегатов;
3) ресурсное–ролевое и рисковое управление.


Рис. 3. Блок–схема алгоритма разметки (labeling) работ


Литература:
1. Добрынин А.С., Кулаков С.М., Зимин В.В. Формализация задачи составления расписаний для стадии внедрения ИТ-сервиса // Научное обозрение: теория и практика. – 2013. - № 2. – С. 47-52, 110.
2. О формировании комплекса инструментальных средств ИТ-провайдера для построения расписаний процесса внедрения сервиса / А.С. Добрынин, С.М. Кулаков, В.В. Зимин, Н.Ф. Бондарь // Научное обозрение. – 2013. - № 8. - С. 93-101.
3. Р.С. Мартин, М. Мартин. Принципы, паттерны и методики быстрой разработки приложений на языке программирования C#. - М.: Символ-Плюс, 2013. - 786 с.
4. OGC-ITIL V3-2 Service Transition, TSO. – 2007.