Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: LXXVI Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 08 апреля 2019 г.)

Наука: Математика

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Сигаев Л.Л., Тихонова В.В. СОЗДАНИЕ СЕТЕВОЙ МОДЕЛИ ПРОЕКТА И РАССМОТРЕНИЕ ВОЗМОЖНОСТИ ЕЕ ОПТИМИЗАЦИИ // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. LXXVI междунар. студ. науч.-практ. конф. № 4(75). URL: https://sibac.info/archive/technic/4(75).pdf (дата обращения: 29.03.2024)
Проголосовать за статью
Конференция завершена
Эта статья набрала 134 голоса
Дипломы участников
Диплом Интернет-голосования

СОЗДАНИЕ СЕТЕВОЙ МОДЕЛИ ПРОЕКТА И РАССМОТРЕНИЕ ВОЗМОЖНОСТИ ЕЕ ОПТИМИЗАЦИИ

Сигаев Леонид Леонидович

студент, факультет информатики, Самарский Университет им. С.П. Королёва,

РФ, г. Самара

Тихонова Виталия Владимировна

студент, факультет информатики, Самарский Университет им. С.П. Королёва,

РФ, г. Самара

Тишин Владимир Викторович

научный руководитель,

доц., кафедра прикладной математики, Самарский Университет им. С.П. Королёва,

РФ, г. Самара

Введение

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

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

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

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

Целью данной исследовательской работы стала разработка сетевой модели создания проекта и практическое применение методов СПУ для анализа и оптимизации.

Создание модели

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

Таблица 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 дней.

Заключение

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

 

Список литературы:

  1. Фомин Г.П. Математические методы и модели в коммерческой деятельности, 2005. - 616 с. 2-е изд., перераб. и доп.
Проголосовать за статью
Конференция завершена
Эта статья набрала 134 голоса
Дипломы участников
Диплом Интернет-голосования

Комментарии (6)

# Елена 16.04.2019 01:36
Очень понравилась статья
# Никита 18.04.2019 22:01
Вперёд юные умы современности! Молодцы, так держать!
# Эльдар 19.04.2019 21:45
Очень порадовала статья. Все продумано и нет ничего лишнего. Молодцы!
# Наталья 19.04.2019 21:58
Молодцы!!!
# Руслан 19.04.2019 23:39
Очень познавательно!
# Полина 19.04.2019 23:40
Вы несомненно лучшие)

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.