Кодирование событий и работ сетевого графа

Расчет параметров сетевого графа на графе

Расчет параметров сетевого графа в табличной форме

I-J
1-2 1-3 1-7 2-4 2-5 3-5 3-6 3-8 4-6 4-7 5-8 6-7 7-8	5 8 9 7 0 0 0 4 0 0 3 1 6	0 0 0 5 5 8 8 8 12 12 8 12 13	5 8 9 12 5 8 8 12 12 12 11 13 19	0 4 4 5 16 16 12 15 12 13 16 12 13	5 12 13 12 16 16 12 19 12 13 19 13 19	0 4 4 0 11 8 4 7 0 1 8 0 0	0 4 4 0 11 4 0 3 0 1 0 0 0	0 0 4 0 3 0 4 7 0 1 8 0 0

= max [ ] = 19, j = 8

: (1-2) → (2-4) → (4-6) → (6-7) → (7-8).

Критический путь на сетевом графе выделяется, например, либо двойной линией, либо более жирной (рис. 13) и т.п.

 

 

Рис. 13. Критический путь сетевого графа ()

 

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

Привязка работ сетевого графа к календарю

 

 

Закрепление работ сетевого графа за имеющимися

Источниками ресурса

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

В качестве критериальных условий были приняты следующие:

1) приоритетность выполнения работ, принадлежащих критическому пути:

(i, j) ,

_{(i, j) GRAF}

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

min ( - ) при ,

_{(i, j) GRAF}

3) приоритетность при прочих равных условиях выполнения работ, требующих наибольших трудозатрат:

max    _{(i, j) GRAF,}

Рассмотрим более подробно процедуру закрепления работ графа за заданными ресурсами.

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

В соответствии с исходными данными для выполнения этой работы требуется пять источников ресурса, которые будут задействованы в течение пяти временных единиц ( = 5) – рис. 14.

Пусть имеется в наличии один вид ресурса, представленный пятью источниками. Претендентами на первоочередное выполнение являются работы, выходящие из события  : (1-2); (1-3); (1-7). Из этого состава работ выбираем работы, принадлежащие критическому пути по первому заданному критериальному условию. Этому критерию отвечает только одна работа (1-2), то есть выбор сделан уже по первому из принятых критериальных условий:

    1 – 2                                                                

    1– 3              (1-2).                  

    1 – 7                                                                                                                                                                

                                                                    

 

Рис. 14. Закрепление работы (1-2) за имеющимися источниками ресурса

После выполнения работы (1-2) появляется возможность выполнения, кроме работ (1-3) и (1-7), еще и работ (2-4) и (2-5), поскольку предшествующая им работа выполнена. Согласно заданным критериальным условиям, в первую очередь выбираем работу, принадлежащую критическому пути. Такой работой является работа (2-4):

Для выполнения этой работы требуется два источника ресурса в течение семи единиц ( = 7)

1-3   

1-7                      (2-4).

2-4                          

2-5

Присоединим работу (2-4) к первому и второму источникам ресурса, следуя правилу: начальное событие данной работы соответствует конечному событию непосредственно предшествующей по времени выполнения. Тогда эпюра загрузки ресурсов сетевого графа будет выглядеть следующим образом (рис.15):

 

 

Рис.15. Закрепление работы (2-4) за имеющимися источниками ресурса

После выполнения работы (2-4) появляется возможность выполнения, кроме работ (1-3), (1-7), (2-5), еще и работ (4-6) и (4-7). Согласно заданным критериальным условиям, в первую очередь выбираем работу, принадлежащую критическому пути. Такой работой является работа (4-6). Все предшествующие ей работы выполнены, следовательно, она может быть включена в график загрузки ресурсов сетевого графа:

1-3                                    

1-7                     

     2-5                              (4-6)

     4-6                                                                           

4-7                                         

 

 

Поскольку работа (4-6) фиктивная ее представление на эпюре будет выглядеть следующим образом (рис. 16).

 

 

 

Рис. 16. Закрепление работы (4-6) за имеющимися источниками ресурса

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

После выполнения работы (4-6) дополнительные работы не открываются, так как единственная работа, выходящая из события  , (6-7), не может быть выполнена без наступления этого события, а оно наступит только после выполнения работы (3-6).

Таким образом, к настоящему моменту в очереди на выполнение стоят следующие, оставшиеся от предыдущей операции работы – (1-3), (1-7), (2-5), (4-7). Из этих работ выбираем, последовательно перебирая заданные критериальные условия, ту, которая будет им соответствовать.

1-3        нет    

1) 1-7                  такой

2-5                 работы            

    4-7                                                                                                         

                                                            

Переходим ко второму критериальному условию:

(min _{(i, j) GRAF}( - ) при ).

Свободный ресурс имеется на шестой момент времени и составляет три источника. Среди работ-претендентов на очередность выполнения выберем ту, которая соответствует второму критериальному условию.

1-3    min _{(i, j) GRAF}( - ) при     

2) 1-7                                                                            (1-3).

2-5

4-7

Работа (1-3) не имеет предшествующих работ, следовательно, она может начинаться в любой момент времени, когда имеются свободные источники ресурса. В нашем случае три источника ресурса освободились на шестой временной единице. В этот момент и начнем выполнение данной работы (рис. 17):

 

              

 

 

Рис. 17. Закрепление работы (1-3) за имеющимися источниками ресурса

После выполнения работы (1-3) появляется возможность выполнения, кроме оставшихся в очереди работ (1-7), (2-5), (4-7), еще и работ (3-5), (3-6) и (3-8). Это альтернативные претенденты для установления очередности выполнения работ сетевого графа. Согласно заданным критериальным условиям, в первую очередь выбираем работу, принадлежащую критическому пути:

 1-7            

1)  2-5                                    

 3-5                         нет

      3-6                       такой

      3-8                    работы

      4-7                                              

Переходим ко второму критерию:

(min _{(i, j) GRAF}( - ) при ).

Свободный ресурс имеется на тринадцатый момент времени и составляет два источника. Среди работ-претендентов на очередность выполнения выберем ту, которая соответствует второму критериальному условию.

1-7    min _{(i, j) GRAF}( - )при     

2) 2-5                                                                        (1-7), (3-8). Имеем

3-5                                                                    альтернативные

    3-6                                                            варианты, так как обе

    3-8                                                        работы требуют для своего

4-7                                                     выполнения по два источника

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

3) 1-7          max

                                        _{(i, j) GRAF}

3-8                                       (1-7).

 

В результате перебора всех критериальных условий выбрана работа (1-7). Она не имеет предшествующих ей работ, следовательно, она может быть включена в график загрузки ресурсов сетевого графа в тот момент, когда окажутся свободными два источника ресурса, то есть на тринадцатой временной единице. Эпюра загрузки источников ресурса всеми выбранными работами представлена рис. 18.

 

Рис. 18. Закрепление работы (1-7) за имеющимися источниками ресурса

Выполнение работы (1-7) не открывает дополнительных работ-претендентов, включаемых в формируемую очередь. Следовательно, в очереди выполняемых работ остались работы (2-5), (3-5), (3-6), (3-8),   (4-7).

Из этих работ, последовательно перебирая заданные критериальные условия, выбираем ту, которая будет им соответствовать.

 

Переходим ко второму критерию (min (i, j) GRAF ( - ) при ). Свободный ресурс имеется на четырнадцатый момент времени и составляет три источника. Среди работ-претендентов на очередность выполнения выбираем ту, которая соответствует второму критериальному условию.

2-5        нет      

1) 3-5                такой               

3-6               работы             

    3-8                                                                                                             

    4-7                                              

                                         

 

 

 

2-5    min _{(i, j) GRAF}( - )при           

2) 3-5                                                                         (3-8)

3-6   

3-8

4-7

 

Такой работой является работа (3-8). Она не имеет незакрепленных за источниками ресурса предшествующих работ, поэтому может быть включена в составляемый график (эпюру) на четырнадцатом временном интервале (рис.19):

Рис.19. Закрепление работы (3-8) за имеющимися источниками ресурса

 

Выполнение работы (3-8) не открывает дополнительных работ-претендентов, включаемых в формируемую очередь, так как она входит в завершающее событие, из которого не выходит ни одной работы. Следовательно, в очереди на выполнение остались работы (2-5), (3-5), (3-6), (4-7).

Из этих работ выбираем, последовательно перебирая заданные критериальные условия, ту, которая будет соответствовать этим критериям в наибольшей степени.

Переходим ко второму критерию (min (i, j) GRAF ( - ) при ). Свободный ресурс имеется на четырнадцатый момент времени и составляет один источник. Среди работ-претендентов на очередность выполнения выбираем ту, которая соответствует второму критериальному условию.

2-5     нет   

1) 3-5               такой            

3-6             работы                 

    4-7                                          

                                                          

 

 

 

     

   

2-5    min _{(i, j) GRAF}( - ) при            нет

2) 3-5                                                                                 такой

3-6                                                                               работы

4-7

Обратимся к третьему критериальному условию: max _{(i, j) GRAF.}

2-5 max _{(i, j) GRAF} (2-5),

3)  3-5                                (3-5),                                                          

3-6                                (3-6),                                               

4-7                                (4-7).

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

Таким образом, закрепление выполнения фиктивных работ за источниками ресурса можно начинать как руководствуясь наличием свободных источников ресурса, так и общим правилом загрузки ресурсов, суть которого сводится к следующему: данную (i, j) – ю работу можно выполнять после выполнения всех непосредственно предшествующих работ. Рассмотрим альтернативные варианты построения эпюр в обоих случаях.

При учете свободных источников ресурса, которые появляются после выполнения работ (1-3), (3-8) и (1-7), включение рассматриваемых фиктивных работ в эпюру загрузки источников ресурса можно начинать после выполнения работы как (1 - 3), (3 - 8), так и (1 - 7). Включим в график очередности выполнения работ работы (2-5) после работы (1-3) на четырнадцатом моменте времени, работы (3-5), (3-6) - после выполнения работы (3-8) на восемнадцатой временной единице, а (4-7) - после выполнения работы (1-7). Такая очередность включения фиктивных работ в разрабатываемую эпюру загрузки источников ресурса продиктована эстетическими соображениями общего вида эпюры (рис. 20).

Рис. 20. Закрепление работ (2-5), (3-5), (3-6), (4-7) за имеющимися

источниками ресурса

При втором подходе, то есть при включении в эпюру фиктивных работ, руководствуясь признаком непосредственного предшествования (непосредственного следования), фиктивную работу (2-5) можно приформировать к окончанию пятой временной единице, то есть после завершения работы (1-2), непосредственно ей предшествующей. Работы (3-5) и (3-6) логично приформировать к окончанию тринадцатой временной единице, поскольку в этот момент заканчивается выполнение непосредственно предшествующей им работы (1-3). Фиктивную работу (4-7) можно построить на уровне работы (4-6), то есть после окончания работы (2-4). Тогда эпюра закрепления этих работ за имеющимися источниками ресурсов будет выглядеть следующим образом (рис. 21):

Рис. 21. Закрепление работ (2-5), (3-5), (3-6), (4-7) за имеющимися

источниками ресурса

Несмотря на альтернативность построенных эпюр, суть использования источников ресурсов остается неизменной: свободные источники ресурсов и в одном, и в другом случае появляются в одном и том же количестве в одно и то же время.

Включение в эпюру фиктивных работ (2-5) и (3-5) открыло возможность выполнения работы (5-8), а (3-6) и (4-6) – работы (6-7).

Выбор очередной работы осуществляется по правилам, изложенным ранее, с ориентацией на методические приемы, используемые при построении графика загрузки источников ресурса решаемого иллюстративного примера. Процедуры выбора работ для их закрепления за источниками ресурса ведутся до тех пор, пока не будут рассмотрены все работы сетевого графа. Наш вариант закрепления работ за источниками ресурса будет выглядеть следующим образом: рис. 22 – продолжение рис. 20, а рис. 23 – продолжение рис. 21.

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

Рис. 22. Закрепление всех работ сетевого графа за

имеющимися источниками ресурса

Рис. 23. Закрепление всех работ сетевого графа за

имеющимися источниками ресурса

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

Закрепление работ сетевого графа за источниками ресурса завершено, эпюра их загрузки построена. Следующим шагом является расчет коэффициентов загрузки и простоя имеющихся источников ресурса при выполнении всех работ рассматриваемого сетевого графа:

=

= 1 – 0,857 = 0,143.