Сетевые модели. Тема10_Сетевые модели_net_lec. Тема 10 Сетевые модели
 Скачать 1.35 Mb.
|
|
5.2. Сетевое представление программы (сетевая модель) 5.2.1. Представление операций Сетевая модель отображает взаимосвязи между операциями и порядок их выполнения (отношение упорядочения или следования). Как правило, для представления операции используется стрелка (ориентированная дуга), направление которой соответствует процессу реализации программы во времени. Отношение упорядочения между операциями задается с помощью событий. Событие опре- деляется как момент времени, когда завершаются одни операции и начинаются другие. Начальная и конечная точки любой операции описываются, таким образом, парой событий, которые обычно называют начальным событием и конечным событием. Операции, выходящие из некоторого собы- тия, не могут начаться, пока не будут завершены все операции, входящие в это событие. По принятой в СПУ терминологии каждая операция представляется ориентированной дугой, а каждое событие — узлом (вершиной). Не требуется, чтобы длина дуги была пропорциональна продолжительности опе- рации, а графическое изображение дуг не обязательно должно представлять прямолинейный отрезок. Рис.6. Представление операций На рис.6(а) приведен типичный пример графического изображения операции i, j с начальным собы- тием i и конечным событием j. На рис.6(6) показан другой пример, из которого видно, что для воз- можности начала операции (3, 4) требуется завершение операций (1, 3) и (2,3). Протекание операций во времени задается путем нумерации событий, причем номер начального события всегда меньше номера конечного. Такой способ нумерации особенно удобен при выполнении вычислений на ЭВМ 5.2.2. Правила построения сетевой модели Правило 1. Каждая операция в сети представляется одной , только одной дугой (стрелкой). Ни одна из операций не должнa появляться в модели дважды. При этом следует различать случай, когда какая-либо операция разбивается на части; тогда каждая часть изображается отдельной дугой. Так, например, прокладку трубопровода можно расчленить на прокладку отдельных секций и рассматри- вать прокладку каждой секции как самостоятельную операцию. Правило 2. Ни одна пара операций не должна определяться одинаковыми начальным и конечным событиями. Возможность неоднозначного определения операций через события появляется в случае, когда две или большее число операций допустимо выполнять, одновременно. Чтобы исключить та- кую ―ошибку‖ между A и конечным (начальным) событием или между В и конечным (начальным) Рис.7. Введение фиктивной операции событием вводится фиктивная операция. Рис.7(б) иллюстрирует различные варианты введения такой фиктивной операции D. В результате операции А и В определяются теперь однозначно парой собы- тий, отличающихся либо номером начального, либо номером конечного события. Следует обратить внимание на то, что фиктивные операции не требуют затрат ни времени, ни ресурсов. Правило 3. При включении каждой операции в сетевую модель для обеспечения правильного упорядочения необходимо дать ответы на следующие вопросы. а) Какие операции необходимо завершить непосредственно перед началом рассматриваемой операции? б) Какие операции должны непосредственно следовать после завершения данной операции? в) Какие операции могут выполняться одновременно с рассматриваемой? Это правило не требует пояснений. Оно позволяет проверять (перепроверять) отношения упорядочения в процессе построения сети. 5.2.3. Расчет сетевой модели Применение методов СПУ в конечном счете должно обеспечить получение календарного плана, определяющего сроки начала и окончания каждой операции. Построение сети является лишь первым шагом на пути к достижению этой цели. Вследствие наличия взаимосвязей между различными опера- циями для определения сроков их начала и окончания необходимо проведение специальных расчетов. Эти расчеты можно выполнять непосредственно на сети, пользуясь простыми правилами. В результате вычислений определяются критические и некритические операции программы. Операция считается критической, если задержка ее начала приводит к увеличению срока окон- чания всей программы. Некритическая операция отличается тем, что промежуток времени между ее ранним началом и поздним окончанием (в рамках рассматриваемой программы) больше ее фактической продолжительности. В таком случае говорят, что некритическая операция имеет резерв, или запас, вре- мени. 5.2.3.1. Определение критического пути Критический путь определяет непрерывную последовательность критических операций, свя- зывающих исходное и завершающее события сети. Другими словами, критический путь задает все критические операции программы. Метод определения такого пути иллюстрируется на численном примере. Пример. Рассмотрим сетевую модель, показанную на рис.8, с исходным событием 0 и завершающим событием 6. Рис.8. Сетевая модель календарного плана. Оценки времени, необходимого для выполнения каждой операции, даны у стрелок. Расчет критического пути включает два этапа. Первый этап называетсяпрямым проходом. Вы- числения начинаются с исходного события и продолжаются до тех пор, пока не будет достигнуто за- вершающее событие всей сети. Для каждого события вычисляется одно число, представляющее ранний срок его наступления. Эти числа указаны на рис.8 в квадратах. На втором этапе, называемомобратным проходом, вычисления начинаются с завершающего события сети и продолжаются, пока не будет до- стигнуто исходное событие. Для каждого события вычисляется число, представляющее поздний срок его наступления. Эти числа даны в треугольниках. Рассмотрим теперь прямой проход. Пусть tрн i —ранний срок начала всех операций, выходящих из события i. Таким образом, tрн i , является также ранним сроком наступления cобытия i. Если принять i=0, т. е. считать, что номер исход- ного события сети равен нулю, то при расчете сети tрн o =0. Обозначим символом τ ij продолжительность операции (i, j). Тогда вычисления при прямом проходе выполняются по формуле tрн j =max{tрн i +τ ij } для всех операций (i,j), где tрн o ==0. Следовательно, чтобы вычислить tрнj для события j, нужно сначала определить tрнi начальных событий всех операций (i, j), входящих в событие j. Применительно к рис.8 вычисления при прямом проходе начинаются с tрн o =0, как показано в квадра- те над событием 0. Поскольку в событие 1 входит только одна операция (0, 1) продолжительностью τ o1 =2, tрн i =tрн o +τ o1 ==0+2=2. Этот результат записан в квадрате у события 1. Рассмотрим далее событие 2. [Заметим, что событие 3 пока рассматривать нельзя, так как срок tрн 2 (событие 2) еще неизвестен.] Таким образом, tрн 2 =tрн 0 +τ 02 =0+3=3. Поместим этот результат в квадрат у события 2. Перейдем теперь к событию 3. Поскольку в него входят две операции (1, 3) и (2, 3), tрн 3 = max { tрн i + τ i3 } = max {2 + 2,3 + 3} = 6, i=1,2 Этот результат также записан в квадрате у события 3. Вычисления продолжаются аналогичным образом, пока не будут определены значения tрн j , для всех j. Имеем tрн 4 = max {tрн i + τ i4 } = max {3 + 2,6 + 0} == 6, i=2, 3 tрн 5 = max {tрн I + τ i5 } = max {6 + 3,6 + 7} == 13, i=3,4 tрн 6 = max {tрн i + τ i6 } = max {б + 2,6 + 5,13 + 6} = 19, i=3, 4,6 На этом вычисления прямого прохода заканчиваются. Обратный проход начинается с завершающего события сети. При этом целью является опреде- ление tпо i ; —поздних сроков окончания всех операций, входящих в событие i. Если принять i=n, где n — завершающее событие сети, то tпо n =tрн n является отправной точкой обратного прохода. В общем виде для любого события i tпо i =min{tпо j —τ ij } для всех операций (i, j). Значения tпо (указанные в треугольниках) вычисляются следующим образом: tпо 6 =tрн 6 ==19, tпо 5 =tпо 6 –τ 56 = 19-3=13, tпо 4 =min {tпо j —τ 4j }=min={13—7, 19—5}=6, i = 5,6 tпо 3 =min {tпо j —τ 3j }=min{6—0, 13—3, 19—2} =6, i=4, 5, 6 tпо 2 =min {tпо j —τ 2j }=min{6—3, 6—2}=3, i=3,4 tпо 1 = tпо 3 —τ 13 == 6 — 2 = 4, tпо 0 =min {tпо j —τ 0j }==min{4—2, 3—3}==0, i=1,2 Вычисления при обратном проходе закончены. Используя результаты вычислений при прямом и обратном проходах, определяем операции кри- тического пути. Операция (i,j) принадлежиткритическому пути, если она удовлетворяет следующим трем условиям: tрн i =tпо i (1) tрн j =tпо j (2) tрн j —tрн i =tпо j —tпо i =τ ij (3) По существу, эти условия означают, что между ранним сроком начала (окончания) и поздним сроком начала (окончания) критической операции запас времени отсутствует. В сетевой модели это от- ражается в том, что для критических операций числа, проставленные в квадратах и треугольниках у начальных и конечных событий, совпадают, а разность между числом в квадрате (или треугольнике) у конечного события и числом у начального события равна продолжительности соответствующей опера- ции в квадрате (или треугольнике). На рис.8 критический путь включает операции (0, 2), (2, 3), (3, 4), (4, 5) и (5, 6). Критический путь определяет кратчайшую возможную продолжительность всей программы в целом. Заметим, что операции (2, 4), (3, 5), (3, 6) и (4, 6) удовлетворяют условиям (1) и (2), но не условию (3). Поэтому они не являются критическими. Критический путь представляет собой непрерывную цепочку операций, соединяющую исходные события сети с завершающим. 5.2.3.2. Определение резервов времени При определении критического пути необходимо вычислить резервы времени для некритических операций. Очевидно, что резерв времени критической операции должен быть равен нулю. Поэтому она и называется критической. Прежде чем приступить к вычислению резервов времени, нужно ввести определения еще двух сроков, связанных с каждой операцией. Это срок позднего начала (tпн) и срок раннего окончания (tро), которые для любой операции ( i, j) задаются соотношениями tпн ij =tпо j —τ ij , tро ij =tрн i +τ ij . Различают два основных вида резервов времени: полный резерв (r) и свободный резерв (ρ). Пол- ный резерв времени операции (i,j) представляет собой разность между максимальным отрезком вре- мени, в течение которого может быть выполнена операция (tпоj—tрн J ), и ее продолжительностью τ ij , т. е. r ij =tпо j —tрн j —τ ij =tпо j —tро ij =tпн ij —tрн i Свободный резерв времени определяется в предположении, что все операции в сети начинаются в ранние сроки. При этом условии величина ρ ij для операции {i, j} представляет собой превышение до- пустимого отрезка времени (tрн j —tрн i ) над продолжительностью операции (τ ij }, т. е. ρ ij =tрн j +tрн i -τ ij Результаты расчета критического пути и резервов времени некритических операций можно свести в удобную для пользования таблицу. В столбцах (1),(2),(3) и (6) приведены результаты расчета сети, рассмотренной в примере 1. Остальные данные легко вычислить по приведенным выше формулам. В таблице 14 приведены результаты типичного расчета сетевой модели. Она содержит всю необходимую для построения календарного плана (графика) информацию. Заметим, что только кри- тические операции должны иметь нулевой полный резерв времени. Таблица 14. Резервы времени. В таблице приведены результаты типичного расчета сетевой модели. Она содержит всю необ- ходимую для построения календарного плана (графика) информацию. Заметим, что только критиче- ские операции должны иметь нулевой полный резерв времени. Когда полный резерв равен нулю, сво- бодный резерв также должен быть равен нулю. Однако обратное неверно, поскольку свободный, ре- зерв некритической операции также может быть нулевым. Так, например, в таблице свободный ре- зерв времени некритической операции (0, 1) равен нулю. 5.3. Оптимизация плана по условию равномерной загрузки Конечным результатом выполняемых на сетевой модели расчетов является календарный гра- фик (план). Этот график легко преобразуется в реальную шкалу времени, удобную для реализации процесса выполнения программы. При построении календарного графика необходимо учитывать наличие ресурсов, так как од- новременное (параллельное) выполнение некоторых операций из-за ограничений, связанных с рабо- чей силой, оборудованием и другими видами ресурсов, может оказаться невозможным. Именно в этом отношении представляют ценность полные резервы времени некритических операций. Сдвигая некритическую операцию в том или ином направлении, но в пределах ее полного резерва времени, можно добиться снижения максимальной потребности в ресурсах. Однако даже при отсутствии огра- ничений на ресурсы полные резервы времени обычно используются для выравнивания потребностей в ресурсах на протяжении всего срока реализации программы. По существу, это означает, что про- грамму удается выполнить более или менее постоянным составом рабочей силы по сравнению со случаем, когда потребности в рабочей силе (и других ресурсах) резко меняются при переходе от од- ного интервала времени к другому. Покажем, как можно выровнять потребности в ресурсах на примере сети, представленной на рис.8. Данные, необходимые для построения календарного графика, приведены в итоговой таблице 14 результатов расчетов календарного плана. Рис. 9. Гант - карта календарного плана. Прежде всего, определяются календарные сроки выполнения критических операций. Далее рас- сматриваются некритические операции и указываются их ранние сроки начала tрни поздние сроки окончания tпо. Критические операции изображаются сплошными линиями. Отрезки времени, в пределах которых могут выполняться некритические операции, наносятся пунктирными линиями, показывающими, что календарные сроки этих операций можно выбрать в указанных пределах при условии сохранения отношений следования. На рис. 9 показан календарный график, соответствующий рассматриваемй сетевой модели. Фиктивная операция (3, 4) не требует затрат времени и поэтому показана на графике вертикальным отрезком. Числа, проставленные над некритическими операциями, соответствуют их продолжитель- ностям. Роль полных и свободных резервов времени при выборе календарных сроков выполнения не- критических операций объясняется двумя общими правилами. 1. Если полный резерв равен свободному, то календарные сроки некритической операции можно выбрать в любой точке между ее ранним началом и поздним окончанием (пунктирные отрез- ки на рис. 9). 2. Если свободный резерв меньше полного, то срок начала некритической операции можно сдвинуть по отношению к ее раннему сроку начала не более чем на величину свободного резерва, не влияя при этом на выбор календарных сроков непосредственно следующих операций. В рассматриваемом примере правило 2 применимо только к операции (0, 1), а календарные сроки всех остальных операций выбираются по правилу 1. Это объясняется тем, что у операции (0, 1) свободный резерв времени равен нулю. Таким образом, если срок начала операции (0, 1) совпадает с ее ранним сроком (t=0), то календарные сроки непосредственно следующей операции (1, 3) можно выбрать любыми между ранним началом (t=2) и поздним окончанием (t=6) этой операции. Если же срок начала операции (0, 1) сдвинут по отношению к t=0, то раннее начало операции (1, 3) должно быть сдвинуто, по крайней мере, на ту же величину. Так, например, в случае, когда операция (0, 1) начинается в момент t=1, она закончится в момент t=3, а календарные сроки операции (3, 1) можно выбрать так, чтобы она начиналась в любой момент между t=3 и t=6. Это ограничение не относится к остальным некритическим операциям, так как их полный и свободный резервы времени совпадают. Этот вывод легко сделать из рассмотрения рис. 5.5, так как операции (0, 1) и (1, 2) единственные, до- пустимые интервалы времени которых накладываются друг на друга. Таким образом, если свободный резерв времени операции меньше полного, то это служит признаком того, что окончательные календарные сроки такой операции нельзя фиксировать, не про- верив сначала, как это повлияет на сроки начала непосредственно следующих операций. Столь цен- ную информацию можно получить только на основе расчетов сетевой модели. Предположим, что для выполнения различных операций требуются указанные ниже в таблице 15 ресурсы рабочей силы. Таблица 15. Требуемые ресурсы исполнителей Операция К-во испонителей Операция К-во испонителей (0,1) 0 (3,5) 2 (0,2) 5 (3,6) 1 (1,3) 0 (4,5) 2 (2,3) 7 (4,6) 5 (2,4) 3 (5,6) 6 |