Методика определения ресурсоемкости проекта некомбинаторным методом | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 10 октября, печатный экземпляр отправим 14 октября.

Опубликовать статью в журнале

Автор:

Рубрика: Математика

Опубликовано в Молодой учёный №48 (286) ноябрь 2019 г.

Дата публикации: 02.12.2019

Статья просмотрена: 10 раз

Библиографическое описание:

Витязев, Д. В. Методика определения ресурсоемкости проекта некомбинаторным методом / Д. В. Витязев. — Текст : непосредственный // Молодой ученый. — 2019. — № 48 (286). — С. 1-4. — URL: https://moluch.ru/archive/286/64652/ (дата обращения: 27.09.2020).



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

Ключевые слова: управление проектом, теория расписаний, диаграмма Гантта, математическое программирование.

В последние годы всё большую популярность набирают системы позволяющие автоматизировать процессы управления проектом, или осуществляющие поддержку принятия решений. Реализация таких алгоритмов связана с применением теории расписаний. Несмотря на то, что в некоторых случаях задачи теории расписаний являются полиномиальными, многие задачи из теории расписаний относятся к классу NP-полных, что делает их вычислительно трудными. В данной работе рассматривается задача определения количества агентов, необходимых для выполнения полного цикла задач, составляющих проект. Такая оценка может быть полезна для принятия решения при составлении расписаний, или при выборе между несколькими допустимыми расписаниями.

Пусть имеется некий проект, состоящий из N работ, очерёдность и временные промежутки, в которые выполняются работы проиллюстрированы диаграммой Гантта на рисунке 1. Составим алгоритм определения количества сотрудников, необходимых для его выполнения исходя из предположения, что любой работник может быть назначен на любую работу, но только на одну, и для выполнения любой операции достаточно одного работника. Из первого предположения следует, что после завершения любой работы освободившийся сотрудник может быть назначен на любую другую работу, которая начинается не раньше времени завершения этой работы.

Рис. 1. Диаграмма Гантта для проекта, состоящего из 16 задач

Для начала докажем утверждение, о том, что для выполнения всего комплекса работ необходимо и достаточно количества работников, равного максимальному количеству выполняемых работ. Необходимость очевидна, если сотрудников меньше, чем максимальное количество одновременно выполняемых работ, то проект невозможно будет выполнить, так как в определенный момент работ будет больше, чем исполнителей, а по нашему предположению один исполнитель не может выполнять больше одной работы. Докажем достаточность, пусть в момент времени T количество работ максимально, тогда верно следующее утверждение: в любой последующий момент времени t количество работ, завершившихся в промежутке времени [T,t] больше, чем количество работ, начавшихся в этом промежутке. Поскольку завершившихся работ всегда больше, на любую начинающуюся работу всегда можно назначить одного из освободившихся работников. Аналогичные рассуждения можно провести в обратном направлении от T до старта проекта. Достаточность доказана.

Учитывая доказанное утверждение можно предложить алгоритм, определяющий количество работников, необходимых для выполнения совокупности всех работ. Проект в дальнейшем будем представлять в виде сетевой диаграммы в представлении работа — вершина. Матрица связности проекта, представленного диаграммой Гантта на рисунке 1 изображена на рисунке 2.

Рис. 2. Матрица связности для рассматриваемого проекта

Предлагается рассмотреть матрицу связности как оператор, действующий в пространстве расписаний (наборов работ). Компоненты векторов такого пространства означают выполнение или не выполнение агентом с этим расписанием работы, соответствующей номеру компоненты этого вектора. Разумеется, не всякое расписание реально выполнимо. Определим какие действия производит оператор. Действуя оператором на набор работ, получаем новый набор работ — тот, в элементы которого можно перейти из элементов изначального набора. Конструкция вида показывает количество возможных переходов между элементами вектора x.

Учитывая вышеизложенное, предложим алгоритм, определяющий количество работ, выполняемых одновременно с заданной. Листинг такой функции, реализованной в MathCad приведен на рисунке 3.

Рис. 3. Листинг функции, определяющей количество работ, выполняемых одновременно с работой n в проекте G

В листинге, приведенном на рисунке 3 использованы функции inv(x) — инверсия булиевого вектора и sum(x) — сумма всех координат вектора. Алгоритм действует следующим образом: выявляются работы, из которых можно перейти в заданную, и работы, в которые можно перейти из заданной. Остальные работы считаются выполняемыми одновременно с заданной, функция возвращает их количество. Далее достаточно найти работу, для которой количество работ, выполняемых одновременно с ней будет максимальным. Листинг этой функции приведен на рисунке 4

Рис. 4. Листинг функции, определяющей минимальное количество работников, для выполнения проекта G

Число, возвращаемое указанной функцией, и будет минимальным числом работников, необходимых для выполнения всего комплекса работ. Для матрицы связности, приведенной на рисунке 2, функция Minstaff(A) = 6. Действительно, как видно из рисунка 5, наиболее ресурсоемкий момент требует участия 6 работников.

Рис. 5. Диаграмма Гантта рассматриваемого проекта с выделением наиболее ресурсоемкой стадии

Указанный метод может быть использован для уменьшения вычислительной сложности задач оценки эффективности построения расписаний и может применяться для повышения эффективности систем поддержки принятия управленческих решений.

Литература:

  1. Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний. Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1975.
  2. S. M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954) 61–68.
  3. Танаев В. С., Гордон В. С., Шафранский Я. М. Теория расписаний. Одностадийные системы.- М.: Наука, 1984.
  4. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5–8459–0857–4.
Основные термины (генерируются автоматически): работа, матрица связности, набор работ, рисунок, теория расписаний, алгоритм, выполнение, комплекс работ, листинг функции, рассматриваемый проект.


Ключевые слова

управление проектом, теория расписаний, диаграмма Гантта, математическое программирование

Похожие статьи

Применение алгоритмов теории расписаний при разработке...

В этой работе используется идея применения алгоритмов теории расписаний для автоматизации

Основные понятия теории расписаний. Определение : « Теория расписаний (ТР)

Рассматриваемый здесь пример можно определить, как детерминированную задачу...

Матричный способ представления алгоритма | Статья в журнале...

В работе рассмотрен вопрос представления алгоритма в

В работе рассмотрен вопрос представления алгоритма в матрично-предикатном виде в

 условия, определяющие порядок выполнения алгоритма, часто задаются несколькими логическими функциями, например...

Задача теории расписаний с временем поступления и временем...

В данной работе рассматривается применение аппроксимационных алгоритмов с

Пример 1. Задача с количеством работ, равным 7: Рассмотрим некоторую перестановку π. Путь (1, 5)

Таким образом, в данной работе представлены основные аппроксимационные алгоритмы с...

Реализация алгоритма поиска ближайших объектов с помощью...

В данной статье разработан алгоритм поиска ближайших объектов с помощью вспомогательной структуры, основанной на K-D tree, а также рассматривается приложение на языке Java, реализующее данный алгоритм.

Алгоритм статистических испытаний для определения...

Рассмотрим подробно работу алгоритма статистических испытаний по методу Монте-Карло.

При оценке связности сети в качестве исходных данных алгоритм Монте-Карло (программа NET

Блочная схема алгоритма вычислений по методу Монте-Карло изображена на рисунке 1.

Оптимизация сайта с помощью выявления связанных структур

В ряде работ было предложена несколько функций меры связности вершин.

Задачи выявления связанных структур в графах в данной работе решалась с помощью

Данный программный комплекс также был использован для анализа существующих компьютерных...

Алгоритмы планирования масштабируемых заданий кластерной...

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

Методы определения объектов на изображении

В работе рассматриваются некоторые методы распознавания объектов на изображении

Листинг 1(Конец). Использование матричных детекторов границ в OpenCV 3.x на примере матрицы Собеля.

Алгоритм детектора Канни состоит из 5 шагов. Первый шаг — сглаживание.

Использование графов для описания модели предприятия при...

Итак, рассмотрим построение моделей предприятия с применением теории графов

Составим модель работы менеджеров отдела продаж, созданную на

гамильтонов цикл, Теория графов , граф , вершина , ребро , граф Г, вычислительный алгоритм, кубический граф...

Комбинированный алгоритм линейной оптимизации с поиском...

По завершении работы программного комплекса были получены следующие итоговые показатели (для удобства исходные и полученные

Разработанный алгоритм и построенный на его основе программный комплекс позволил решить задачу оптимизации использования...

Похожие статьи

Применение алгоритмов теории расписаний при разработке...

В этой работе используется идея применения алгоритмов теории расписаний для автоматизации

Основные понятия теории расписаний. Определение : « Теория расписаний (ТР)

Рассматриваемый здесь пример можно определить, как детерминированную задачу...

Матричный способ представления алгоритма | Статья в журнале...

В работе рассмотрен вопрос представления алгоритма в

В работе рассмотрен вопрос представления алгоритма в матрично-предикатном виде в

 условия, определяющие порядок выполнения алгоритма, часто задаются несколькими логическими функциями, например...

Задача теории расписаний с временем поступления и временем...

В данной работе рассматривается применение аппроксимационных алгоритмов с

Пример 1. Задача с количеством работ, равным 7: Рассмотрим некоторую перестановку π. Путь (1, 5)

Таким образом, в данной работе представлены основные аппроксимационные алгоритмы с...

Реализация алгоритма поиска ближайших объектов с помощью...

В данной статье разработан алгоритм поиска ближайших объектов с помощью вспомогательной структуры, основанной на K-D tree, а также рассматривается приложение на языке Java, реализующее данный алгоритм.

Алгоритм статистических испытаний для определения...

Рассмотрим подробно работу алгоритма статистических испытаний по методу Монте-Карло.

При оценке связности сети в качестве исходных данных алгоритм Монте-Карло (программа NET

Блочная схема алгоритма вычислений по методу Монте-Карло изображена на рисунке 1.

Оптимизация сайта с помощью выявления связанных структур

В ряде работ было предложена несколько функций меры связности вершин.

Задачи выявления связанных структур в графах в данной работе решалась с помощью

Данный программный комплекс также был использован для анализа существующих компьютерных...

Алгоритмы планирования масштабируемых заданий кластерной...

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

Методы определения объектов на изображении

В работе рассматриваются некоторые методы распознавания объектов на изображении

Листинг 1(Конец). Использование матричных детекторов границ в OpenCV 3.x на примере матрицы Собеля.

Алгоритм детектора Канни состоит из 5 шагов. Первый шаг — сглаживание.

Использование графов для описания модели предприятия при...

Итак, рассмотрим построение моделей предприятия с применением теории графов

Составим модель работы менеджеров отдела продаж, созданную на

гамильтонов цикл, Теория графов , граф , вершина , ребро , граф Г, вычислительный алгоритм, кубический граф...

Комбинированный алгоритм линейной оптимизации с поиском...

По завершении работы программного комплекса были получены следующие итоговые показатели (для удобства исходные и полученные

Разработанный алгоритм и построенный на его основе программный комплекс позволил решить задачу оптимизации использования...

Задать вопрос