Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

COMPARATIVE ANALYSIS OF THE SUBCONTRACTING SCHEDULING METHODS

Antonova A.S. 1 Aksenov K.A. 1
1 Ural Federal University named after First President of Russia B.N. Yeltsin
The article presents a comparative analysis of the following scheduling methods: methods of the network scheduling (critical path method, PERT and GERT methods), method of cooperation of the demands-opportunities network agents developed by Kleymenova E.M. and Skobelev P.O., method of the simulation and genetic algorithms integration developed by Kureichik V.V., and multiagent genetic optimization method developed by article authors on the basis of the Kureichik V.V. method. As a result of the analysis the advantage of the multiagent genetic optimisation method was revealed in terms of subcontracting scheduling. The multiagent genetic optimisation method takes into account the non-renewable resources and allows to implement different resource allocation strategies using simulation and multiagent modeling, allows to optimize subcontract resources via analysis of alternative work schedules using genetic algorithms and simulation, reschedules the works using numerical methods of uncertainty removing and simulation.
multi-agent modeling
simulation
genetic algorithms
methods of the network scheduling
subcontracting scheduling

Введение

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

Рассмотрим ряд методов решения задачи планирования работ [2-8] и проведем их сравнительный анализ применительно к решению задачи планирования субподрядных работ.

Сетевые методы планирования

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

Метод критического пути (Critical Path Method – CPM) предназначен для оценки резервного времени работ в случае задания детерминированных длительностей работ. Найденное резервное время применяется для балансировки ресурсов, которая осуществляется с помощью различных эвристических алгоритмов установления приоритета работ [4]. После проведения балансировки ресурсов единственным способом сокращения критического пути является привлечение субподрядных ресурсов. Для оценки целесообразности привлечения субподрядных ресурсов для каждой работы рассчитывается величина средней стоимости сокращения длительности работ на единицу времени и выбирается наиболее выгодная работа с точки зрения ускорения ее выполнения.

Метод PERT (Program Evaluation and Review Technique) предназначен для оценки сроков окончания проекта с учетом вероятностного задания длительности работ с помощью β-распределения [4]. Развитием метода PERT является метод GERT (Graphical Evaluation and Review Technique), предназначенный для анализа стохастического сетевого графика работ [8]. Стохастический сетевой график строится с помощью графического языка моделирования GERT. Каждая дуга стохастической сети (работа) характеризуется длительностью и вероятностью реализации в проекте. Под реализацией сети понимается срез сети, в котором одни дуги сохраняются (реализуются), а другие дуги отбрасываются (не реализуются). Узлы сети реализуются входящими в узлы реализованными дугами. Каждый узел стохастической сети отождествляется с двумя событиями: с событием окончания работы (входным событием) и с событием начала работы (выходным событием). Для описания входного события в языке GERT определены три логические операции: «исключающее ИЛИ» (из всех дуг, входящих в узел, может быть реализована только одна), «включающее ИЛИ» (любая из дуг, входящих в узел, может быть реализована), «И» (все дуги, входящие в узел, должны быть реализованы). Для описания выходного события узла в языке GERT определены два типа выхода: детерминированный выход (все дуги, исходящие из узла, реализуются) и вероятностный выход (только одна дуга из всех дуг, исходящих из узла, реализуется). Пример сетевого графика процессов запуска и маневрирования двух транспортных средств, построенного с помощью языка моделирования GERT, представлен на рис. 1 [8]. На рисунке использованы следующие обозначения: полукруг на входе узла – логическое «И», треугольник на входе узла – «включающее ИЛИ», полукруг на выходе узла – детерминированный выход, треугольник на выходе узла – вероятностный выход.

Рис. 1. Сетевой график, построенный с помощью языка моделирования GERT [8]

Метод планирования Клейменовой Е.М. и Скобелева П.О.

Метод Клейменовой Е.М. и Скобелева П.О. [6-7] предназначен для планирования проектных работ путем построения мультиагентной системы оперативного распределения ресурсов в режиме реального времени с учетом возможности корректировки состава и характеристик планируемых проектов, задач и ресурсов. За основу метода взят метод ПВ-сетей (сетей потребностей-возможностей), предложенный Скобелевым П.О. [7]. ПВ-сеть представляет собой мультиагентную систему, в которой каждый агент характеризуются потребностями (П) и возможностями (В); агенты ПВ-сети ведут переговоры для удовлетворения собственных потребностей с помощью чужих возможностей. ПВ-сеть применяется Клейменовой Е.М. и Скобелева П.О. для представления множества заказов, проектов, задач и ресурсов предприятия, при этом каждому перечисленному элементу ПВ-сети ставится в соответствие свой агент, например, агент-ресурс №1, агент-задача №1, агент-проект №1 и т.д. В ходе переговоров агентов происходит распределение ресурсов по задачам; фрагмент протокола переговоров агентов на уровне отдельной задачи представлен на рис. 2 [6]. Как видно из рисунка, из трех доступных ресурсов агент задача выбирает один, первый в списке, остальные альтернативные ресурсы остаются непроанализированными.

Рис. 2. Протокол переговоров агентов в системе Клейменовой Е.М. и Скобелева П.О. [6]

Данный метод включает фазы начального бесконфликтного и проактивного перепланирования задачи [6]. Фаза бесконфликтного планирования подразумевает распределение ресурсов путем последовательного выбора агентами-задачами необходимого ресурса и генерации временного интервала (слота) занятости ресурса, который записывается в запланированные слоты агента-ресурса. Фаза проактивного планирования предполагает разрешение для каждого агента-ресурса конфликтов запланированных слотов, назначенных агентами-задачами, путем рекурсивных переговоров согласно описанным протоколам взаимодействия агентов ПВ-сети. В случае появления новой задачи (ресурса), в системе создается новый агент-задача (агент-ресурс), который включается в переговоры, заявляя о своих потребностях или возможностях.

Метод планирования Курейчика В.В.

Метод Курейчика В.В. [5] предназначен для моделирования дискретных процессов, протекающих в организационно-технических системах, и оптимизации управляемых параметров процессов с помощью генетических алгоритмов (ГА). Генетические алгоритмы получили широкую известность в качестве алгоритмов решения задач управления сложными системами в короткое время. На рис. 3 представлена схема работы метода Курейчика В.В., согласно которой поставленная задача решается ГА, а имитационная модель применяется для расчета многокритериальной функции пригодности особей очередного поколения. Экспертная система при этом используется для анализа и коррекции параметров работы ГА (вероятностей применения генетических операторов).

Рис. 3. Схема работы метода Курейчика В.В. [5]

Предложенный метод был реализован в среде РДО [5] и с его помощью решена задача планирования работы цеха. Для поставленной задачи целью блока оптимизации являлся подбор оптимальных значений управляемых переменных имитационной модели, в качестве которых выступали приоритеты выполняемых заказов. Функцией пригодности служила функция штрафов за срывы заказов.

Метод мультиагентной генетической оптимизации

Метод мультиагентной генетической оптимизации (МГО) предназначен для планирования субподрядных работ при условии возможной смены мощности портфеля проектов [2-3]. В основе метода МГО лежит метод Курейчика В.В., модифицированный следующими методами и алгоритмами: 1) мультиагентным моделированием в части описания модели распределения собственных и субподрядных ресурсов по работам, 2) численными методами снятия неопределенности в части учета вероятности появления дополнительных проектов, 3) алгоритмами имитации отжига и поиска новизны в части модификации генетического алгоритма с целью повышения качества найденных алгоритмом решений. Метод МГО реализован в системе динамического моделирования ситуаций BPsim.MAS [1], поддерживающей описание модели мультиагентных процессов преобразования ресурсов (МППР) и модели генетической оптимизации задачи субподрядного планирования. Интерфейс модуля обмена данными между моделью МППР и моделью генетической оптимизации представлен на рис. 4.

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

Рис. 4. Интерфейс обмена данными между моделями МППР и генетической оптимизации

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

Сравнительный анализ методов планирования субподрядных работ

Результаты сравнительного анализа представлены в таблице 1.

Таблица 1 – Сравнительный анализ методов субподрядного планирования

Критерий сравнения

Методы CPM, PERT,

GERT

Метод Клейменовой Е.М.

Метод Курейчика В.В.

Метод МГО

Решаемые задачи

Календарное планирование

+

+

+

+

Учет возобновляемых ресурсов

+

+

+

+

Учет невозобновляемых ресурсов

НЕТ

НЕТ

НЕТ

+

Балансировка ресурсов

+

+

НЕТ

+

Учет субподрядных работ

+

+

НЕТ

+

Оптимизация субподряда

НЕТ

НЕТ

НЕТ

+

Перепланирование работ

НЕТ

+

НЕТ

+

Анализ альтернативных планов

НЕТ

НЕТ

+

+

Методы решения задачи планирования

Имитационное моделирование

НЕТ

НЕТ

+

+

Мультиагентное моделирование

+

НЕТ

+

Эволюционное моделирование

НЕТ

+

+

Экспертное моделирование

+

+

+

Эвристические алгоритмы

+

НЕТ

+

+

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

Анализ сетевых методов планирования позволяет выделить следующие недостатки:

  1. Громоздкость и плохая читаемость стохастических сетевых графиков, построенных с помощью языка GERT. Связано это с тем, что метод GERT ориентирован на анализ сети с узлами, входы которых описываются с помощью логической операции «И». В ходе преобразования произвольной стохастической сети к сети подобного вида [8] число дуг и узлов сети увеличивается, что затрудняет восприятие и анализ сети.
  2. Отсутствие методов оптимизации субподрядных работ. Метод CPM позволяет назначать сторонние ресурсы на выполнение работ критического пути и проводить оценку эффективности назначения. Тем не менее, метод CPM не имеет встроенных механизмов оптимизации субподрядных работ.
  3. Отсутствие средств формализации сценариев принятия решений при распределении ресурсов по работам (построения моделей ЛПР, работающих со знаниями).
  4. Отсутствие учета невозобновляемых ресурсов (потребляемых и производимых в результате выполнения работ проекта).

Метод Клейменовой Е.М. и Скобелева П.О. основан на функционировании интеллектуальных агентов, однако агенты ПВ-сети не поддерживают анализ альтернативных решений, отсекая «лишние» возможности в ходе переговоров. К недостаткам данного метода с точки зрения обеспечения субподрядного планирования также относятся следующие.

  1. Отсутствие методов оптимизации субподрядных работ. Метод поддерживает описание агента субподрядного ресурса в ПВ-сети, но не предоставляет механизмов определения оптимального количества подобных агентов.
  2. Отсутствие учета невозобновляемых ресурсов.

Анализ метода Курейчика В.В. позволяет выделить следующие недостатки:

  1. Ориентация метода на широкий класс задач управления ОТС, что приводит к необходимости разработки пользователем онтологии задачи субподрядного планирования и разработки собственного генетического алгоритма.
  2. Отсутствие механизмов учета и оптимизации субподрядных работ, учета невозобновляемых ресурсов; отсутствие средств формализации сценариев принятия решений при распределении ресурсов по работам.
  3. Отсутствие возможности перепланирования работ при появлении дополнительных проектов. В то же время метод Курейчика В.В. предоставляет возможность вероятностного задания длительности и стоимости отдельных работ.

Заключение

При рассмотрении задачи субподрядного планирования был проведен сравнительный анализ сетевых методов планирования, методов Клейменовой Е.М. и Скобелева П.О., Курейчика В.В., метода мультиагентной генетической оптимизации.

В результате проведенного сравнительного анализа был сделан вывод о предпочтительности метода мультиагентной генетической оптимизации с точки зрения поддержки функционала планирования субподрядных работ. Метод МГО позволяет: реализовывать алгоритм распределения возобновляемых и невозобновляемых ресурсов с помощью имитационного, мультиагентного и экспертного моделирования; осуществлять оптимизацию субподрядных ресурсов путем анализа альтернативных календарных планов с помощью интеграции генетических алгоритмов и имитационного моделирования; проводить перепланирование работ в случае появления дополнительных проектов с помощью интеграции имитационного моделирования и численных методов снятия неопределенности. Метод МГО прошел апробацию на задаче планирования проектных работ ЗАО "Телесистемы" [2-3].

Работа выполнена в рамках договора № 02.G25.31.0055 (проект 2012-218-03-167).

Рецензенты:

Поршнев С.В., д.т.н., профессор, заведующий кафедрой Радиоэлектроники информационных систем, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.

Доросинский Л.Г., д.т.н., профессор, заведующий кафедрой Информационных технологий, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.