Статья опубликована в рамках: LXXVI Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 08 апреля 2019 г.)
Наука: Математика
Скачать книгу(-и): Сборник статей конференции
СОЗДАНИЕ СЕТЕВОЙ МОДЕЛИ ПРОЕКТА И РАССМОТРЕНИЕ ВОЗМОЖНОСТИ ЕЕ ОПТИМИЗАЦИИ
Введение
На сегодняшний день практически любая коммерчески прикладная задача вызывает трудности при ее планировании. Связано это прежде всего с разнообразием, сложносвязностью и взаимозависимостью различных процессов, которые должны быть завершены для получения итогового результата. Достаточно часто общепринятые методы планирования задач оказываются неэффективными, то есть, не позволяют обеспечить выполнение нужных операций в заданные сроки или установить оптимальный объем используемых ресурсов.
Одними из самых эффективных на данный момент являются сетевые методы и модели, на базе которых созданы методы сетевого планирования и управления (далее – СПУ). СПУ представляет собой метод научного планирования и управления выполнением работ достаточно больших масштабов с высоковероятным соблюдением заданных сроков реализации задач, что и является главным достоинством метода.
Математический аппарат СПУ основан на использовании информационно-динамической модели (сетевой модели логико-математического описания), которая позволяет провести алгоритмизацию расчетов параметров этого процесса. В графическом отображении СПУ указывают логическую последовательность работ, существующие между ними связи, их длительность и другие необходимые параметры.
СПУ позволяет сконцентрировать внимание на самых важных комплексах работ, отводя на задний план второстепенные. Более того, данный метод решает основные задачи, стоящие при выполнении любого крупномасштабного проекта, а именно: обеспечивает возможность непрерывного управления ходом работ, позволяет экономить ресурсы, дает четкую картину взаимодействия исполнителей.
Целью данной исследовательской работы стала разработка сетевой модели создания проекта и практическое применение методов СПУ для анализа и оптимизации.
Создание модели
В качестве нашей коммерческой задачи возьмем задачу разработки программного продукта. Проанализируем все работы, которые придется выполнить для ее реализации, укажем их длительность и взаимосвязь.
Таблица 1.
Таблица работ
|
N |
Название работы (ai) |
Длительность (дней) |
Предшествующие работы |
|
1 |
Создание бизнес-правил |
1 |
- |
|
2 |
Создание модели |
2 |
1 |
|
3 |
Создание проекта |
1 |
2 |
|
4 |
Настройка проекта |
1 |
3 |
|
5 |
Разработка модели |
5 |
4 |
|
6 |
Создание интерфейсов |
3 |
4 |
|
7 |
Создание исключений |
2 |
6 |
|
8 |
Разработка контроллеров |
5 |
5,6 |
|
9 |
Разработка пользовательского интерфейса |
10 |
5,6 |
|
10 |
Обработка исключений |
4 |
7,8,9 |
|
11 |
Тестирование |
5 |
10 |
|
12 |
Подготовка к реализации продукта |
4 |
11 |
На основании таблицы построим граф G:
Основными параметрами сетевых моделей являются критический путь, резервы времени работ, событий и путей. Кроме этих показателей также имеется несколько вспомогательных, которые являются исходными для получения дополнительных характеристик по анализу и оптимизации сетевого плана комплекса работ:
Ранний срок свершения j-гo события — это минимальный из возможных моментов наступления события j при заданной продолжительности работ.
Поздний срок свершения j-гo события — это максимальный из допустимых моментов наступления события j, при котором еще возможно выполнение всех последующих работ в установленный срок.
Резерв времени на свершение j-гo события — это промежуток времени, на который может быть отсрочено наступление события j без нарушения сроков завершения всего комплекса. Резерв времени определяется как разность между поздним и ранним сроками наступления события.
Ранний срок начала работы— это минимальный из возможных моментов начала данной работы при заданной продолжительности работ. Он совпадает с ранним сроком наступления ее начального события.
Ранний срок окончания работы— это минимальный из возможных моментов окончания данной работы при заданной продолжительности работ. Он превышает ранний срок наступления ее события i на величину продолжительности работы.
Поздний срок начала работы— это максимальный из допустимых моментов начала данной работы, при котором еще возможно выполнение всех последующих работ в установленный срок.
Поздний срок окончания работы— это максимальный из допустимых моментов окончания данной работы, при котором еще возможно выполнение последующих работ в установленный срок.
Полный резерв времени работ— максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы без изменения общего срока выполнения комплекса.
Свободный резерв времени работы – максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы при условии, что все события сети наступают в свои ранние сроки.
Полный резерв времени пути показывает, на сколько могут быть увеличены продолжительности всех работ в сумме пути относительно критического пути. Если полный резерв времени равен нулю, то работа считается работой критического пути.
Рассчитаем основные параметры для работ:
Таблица 2.
Таблица основных параметров работ в графе G
|
N |
Работа (i,j) |
Пред шест-вующие работы |
Продол Житель ность работы |
Сроки выполнения |
Резервы времени |
Крити-ческий путь |
|||||
|
Ранние |
Поздние |
Ранние |
Поздние |
|
|||||||
|
Начало |
Окон-чание |
Начало |
Окон-чание |
Полный |
Свобод-ный |
||||||
|
1 |
(1;2) |
- |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
✔ |
|
2 |
(2;3) |
1 |
2 |
1 |
3 |
2 |
3 |
0 |
0 |
0 |
✔ |
|
3 |
(3;4) |
2 |
1 |
2 |
4 |
3 |
4 |
0 |
0 |
0 |
✔ |
|
4 |
(4;5) |
3 |
1 |
3 |
5 |
4 |
5 |
0 |
0 |
0 |
✔ |
|
5 |
(5;6) |
4 |
5 |
5 |
10 |
5 |
10 |
0 |
0 |
0 |
✔ |
|
6 |
(5;7) |
4 |
3 |
5 |
8 |
7 |
10 |
2 |
0 |
2 |
|
|
7 |
(7;9) |
6 |
2 |
8 |
20 |
18 |
20 |
10 |
10 |
0 |
|
|
8 |
(6;9) |
5,6 |
5 |
10 |
25 |
15 |
20 |
5 |
5 |
0 |
|
|
9 |
(8;9) |
5,6 |
10 |
10 |
20 |
10 |
20 |
0 |
0 |
0 |
✔ |
|
10 |
(9;10) |
7,8,9 |
4 |
20 |
24 |
20 |
24 |
0 |
0 |
0 |
✔ |
|
11 |
(10;11) |
10 |
5 |
24 |
29 |
24 |
29 |
0 |
0 |
0 |
✔ |
|
12 |
(11;12) |
11 |
4 |
29 |
33 |
29 |
33 |
0 |
0 |
0 |
✔ |
Срок выполнения проекта оставляет 33 дня. Работы критического пути: 1,2,3,4,5,9,10,11,12
Для оптимизации можно распараллелить работы (1, 2) и (3, 4). Так же для начала работы 9 не обязательно ждать окончания работы 6, а для начала работы 12 не обязательно ждать окончания работ 10 и 11. С учетом внесенных замечаний и предварительного анализа, внесем изменения в связи между работами проекта:
Таблица 3.
Таблица работ после предварительного анализа
|
N |
Название |
Длительность (дней) |
Предшествующие работы |
|
1 |
Создание бизнес-правил |
1 |
- |
|
2 |
Создание модели |
2 |
1 |
|
3 |
Создание проекта |
1 |
- |
|
4 |
Настройка проекта |
1 |
3 |
|
5 |
Разработка модели |
5 |
2,4 |
|
6 |
Создание интерфейсов |
3 |
2,4 |
|
7 |
Создание исключений |
2 |
6 |
|
8 |
Разработка контроллеров |
5 |
5,6 |
|
9 |
Разработка пользовательского интерфейса |
10 |
5 |
|
10 |
Обработка исключений |
4 |
7,8,9 |
|
11 |
Тестирование |
5 |
10 |
|
12 |
Подготовка к реализации продукта |
4 |
7,8,9 |
На основании таблицы построим граф G`:
Рассчитаем основные параметры для работ в новом графе:
Таблица 4.
Таблица основных параметров работ в графе G`
|
N |
Работа (i,j) |
Пред шест-вующие работы |
Продол житель ность работы |
Сроки выполнения |
Резервы времени |
Крити-ческий путь |
|||||
|
Ранние |
Поздние |
Ранние |
Поздние |
||||||||
|
Начало |
Окон-чание |
Начало |
Окон-чание |
Полный |
Свобод-ный |
||||||
|
1 |
(1;2) |
- |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
✔ |
|
2 |
(2;4) |
1 |
2 |
1 |
3 |
1 |
3 |
0 |
0 |
0 |
✔ |
|
3 |
(1;3) |
- |
1 |
0 |
1 |
1 |
2 |
1 |
0 |
1 |
|
|
4 |
(3;4) |
3 |
1 |
1 |
2 |
2 |
3 |
1 |
1 |
0 |
|
|
5 |
(4;5) |
2,4 |
5 |
3 |
8 |
3 |
8 |
0 |
0 |
0 |
✔ |
|
6 |
(4;6) |
2,4 |
3 |
3 |
6 |
13 |
16 |
10 |
0 |
10 |
|
|
7 |
(6;8) |
6 |
2 |
6 |
8 |
16 |
18 |
10 |
10 |
0 |
|
|
8 |
(7;8) |
5,6 |
5 |
8 |
13 |
13 |
18 |
5 |
5 |
0 |
|
|
9 |
(5;8) |
5 |
10 |
8 |
18 |
8 |
18 |
0 |
0 |
0 |
✔ |
|
10 |
(8;9) |
7,8,9 |
4 |
18 |
22 |
18 |
22 |
0 |
0 |
0 |
✔ |
|
11 |
(9;10) |
10 |
5 |
22 |
27 |
22 |
27 |
0 |
0 |
0 |
✔ |
|
12 |
(8;10) |
7,8,9 |
4 |
18 |
22 |
23 |
27 |
5 |
5 |
0 |
|
Срок выполнения проекта после внесенных изменений составляет 27 дней. Работы критического пути: 1,2,5,9,10,11. Результатами предварительной оптимизации стало уменьшение времени выполнения работы и количество работ, входящих в критический путь.
Зададим некоторое исходное количество исполнителей, приходящихся на одну работу. В дальнейшем, именно это распределении будет подвергаться изменению, а значит, оптимизации.
Таблица 5.
Таблица распределения ресурсов по работам.
|
N |
Работа (i,j) |
Ресурсы (исполнители) |
Cij |
|
1 |
(1;2) |
2 |
1/2 |
|
2 |
(2;4) |
2 |
1/2 |
|
3 |
(1;3) |
1 |
1 |
|
4 |
(3;4) |
2 |
1/2 |
|
5 |
(4;5) |
2 |
1/2 |
|
6 |
(4;6) |
4 |
1/4 |
|
7 |
(6;8) |
2 |
1/2 |
|
8 |
(7;8) |
3 |
1/3 |
|
9 |
(5;8) |
2 |
1/2 |
|
10 |
(8;9) |
2 |
1/2 |
|
11 |
(9;10) |
3 |
1/3 |
|
12 |
(8;10) |
3 |
1/3 |
Построим все возможные пути в графе, найдем их длину, работы, на которых имеется резерв и величину этого резерва.
Таблица 6.
Таблица путей в графе G`
|
N |
Путь |
Длина пути |
Резерв |
Величина резерва |
|
1 |
1-2-4-5-8-9-10 |
27 |
- |
0 |
|
2 |
1-2-4-5-8-10 |
22 |
8-10 |
5 |
|
3 |
1-2-4-5-7-8-9-10 |
22 |
7-8 |
5 |
|
4 |
1-2-4-5-7-8-10 |
17 |
7-8,8-10 |
10 |
|
5 |
1-2-4-6-8-9-10 |
17 |
6-8 |
10 |
|
6 |
1-2-4-6-8-10 |
12 |
6-8,8-10 |
15 |
|
7 |
1-2-4-6-7-8-9-10 |
20 |
4-6,7-8 |
7 |
|
8 |
1-2-4-6-7-8-10 |
15 |
4-6,7-8,8-10 |
12 |
|
9 |
1-3-4-5-8-9-10 |
26 |
3-4 |
1 |
|
10 |
1-3-4-5-8-10 |
21 |
3-4,8-10 |
6 |
|
11 |
1-3-4-5-7-8-9-10 |
21 |
3-4,7-8 |
6 |
|
12 |
1-3-4-5-7-8-10 |
16 |
3-4,7-8,8-10 |
11 |
|
13 |
1-3-4-6-8-9-10 |
16 |
3-4,6-8 |
11 |
|
14 |
1-3-4-6-8-10 |
11 |
3-4,6-8,8-10 |
16 |
|
15 |
1-3-4-6-7-8-9-10 |
19 |
3-4,4-6,7-8 |
8 |
|
16 |
1-3-4-6-7-8-10 |
14 |
3-4, 4-6,7-8,8-10 |
13 |
Возьмем путь, ближайший по длине к критическому: 
=27, 
=26 
. Ресурсы с работы 3-4 можно перераспределить на работу 1-2. Решим уравнение:
Проверим возможность перевода одного сотрудника с одной работы на другую: 
Перевод сотрудника возможен, рассчитаем новые длительности работ:
Рассчитаем новую длительность критического пути:
Замечание: согласно правилам оптимизации СПУ, нельзя перераспределять ресурсы внутри одного пути, то есть, переносить резерв на работу, находящуюся в том же пути, что и работа со свободным резервом.
После проведенных операций путь 
так же стал критическим. Далее будем проводить одновременную оптимизацию 
и . Одновременность будет заключаться в том, что в случае улучшения распределения параметров одного из них, аналогичное улучшение должно появиться и во втором. Это возможно только при переброске резервов на работы (4;5), (5;8), (8;9) или (9;10).
Таблица 7.
Таблица процесса оптимизации.
|
Путь |
Работа с резервом |
|
4-5 |
5-8 |
8-9 |
9-10 |
|
2 |
8-10 |
4,5 |
- |
- |
1,35 |
1,5 |
|
3 |
7-8 |
4,5 |
- |
0,6 |
- |
- |
|
10 |
8-10 |
4,5 |
- |
- |
1,35 |
1,83 |
|
11 |
7-8 |
4,5 |
- |
0,66 |
- |
- |
|
7 |
4-6 |
1,5 |
2 |
1,13 |
- |
- |
|
7-8 |
4,5 |
0,624 |
0,312 |
- |
- |
|
|
15 |
4-6 |
1,5 |
2,3 |
1,3 |
- |
- |
|
7-8 |
4,5 |
1,8 |
0,9 |
- |
- |
|
|
4 |
7-8 |
4,5 |
- |
1,14 |
2,59 |
2,85 |
|
5 |
7-8 |
4,5 |
2,28 |
- |
- |
- |
|
12 |
7-8 |
4,5 |
- |
1,26 |
3,5 |
2,85 |
|
8-10 |
4,5 |
- |
1,66 |
3,15 |
3,5 |
|
|
13 |
6-8 |
9,5 |
3 |
1,75 |
- |
- |
|
8 |
4-6 |
1,5 |
1,13 |
2 |
3,45 |
3,83 |
|
7-8 |
4,5 |
2,76 |
3,13 |
3,13 |
3,45 |
|
|
8-10 |
4,5 |
3 |
1,81 |
3,45 |
3,83 |
|
|
16 |
4-6 |
1,5 |
3,85 |
2,17 |
5 |
5,17 |
|
7-8 |
4,5 |
3 |
1,875 |
3,4 |
3,75 |
|
|
8-10 |
4,5 |
3,26 |
1,97 |
3,75 |
5,17 |
|
|
6 |
6-8 |
9,5 |
4,14 |
2,42 |
4,83 |
5,44 |
|
8-10 |
4,5 |
3,78 |
2,3 |
4,35 |
4,83 |
|
|
14 |
6-8 |
9,5 |
4,43 |
2,58 |
5,17 |
5,81 |
|
8-10 |
4,5 |
4,04 |
2,45 |
4,65 |
5,17 |
В ряде случаев выделение резерва невозможно, так как это будет означать полную передачу всех имеющихся ресурсов на другую работу.
Проанализировав все возможные пути и варианты размещения свободных резервов, приходим к выводу, что перерасчет по экспоненциальной зависимости не позволяет оптимизировать проект. Только на первом шаге нашего анализа нам удалось получить некоторое улучшение, в виде уменьшения длины критического пути до 26,5 дней.
Заключение
В ходе проделанной работы была рассмотрена конкретная практическая задача, для которой была построена сетевая модель и произведен анализ возможности ее оптимизации.
Список литературы:
- Фомин Г.П. Математические методы и модели в коммерческой деятельности, 2005. - 616 с. 2-е изд., перераб. и доп.
Комментарии (6)
Оставить комментарий