Характеристика и основные задачи подсистемы технической подготовки производства

Лекция 4.1 Характеристика и основные задачи подсистемы технической подготовки производства страница 1 4.1.1. Назначение, характеристика и основные задачи подсистемы 4.1.1.1. Назначение подсистемы ТПП Под технической подготовкой производства (ТПП) понимается комплекс взаимосвязанных научно-исследовательских, конструкторских, технологических, экспериментальных и инструментальных работ по подготовке к производству новой продукции, а также мероприятия, направленные на повышение качества, надежности, долговечности изделий, находящихся в производстве. Типовой процесс разработки нового изделия в машиностроении включает в себя обычно следующие этапы: -       научно-исследовательская работа; -       конструкторская подготовка производства; -       технологическая подготовка производства; -       изготовление и испытание опытных образцов разрабатываемого изделия; -       освоение производства новых изделий;   Все эти работы выполняются однократно. Но, кроме того, в состав ТПП включается также организационная подготовка производства, охватывающая циклически повторяющийся комплекс мероприятий, связанных с регулярным обеспечением и обслуживанием действующего производства.  Управление этими работами и составляет содержание подсистемы ТПП АСУП. Так как техническая подготовка производства представляет собой длительный процесс сложной структуры, состоящий из множества взаимосвязанных и взаимозависимых работ, требующих своевременного использования многообразных ресурсов, то наиболее удобной математической моделью этого процесса являются сетевые модели. Изучению сетевых моделей и будут посвящены последующие лекции. Однако необходимо отметить, что такие модели составляют лишь основу подсистемы. Сетевую модель дополняют большим числом различных сервисных, информационных и других алгоритмов и программ, образующих вместе весьма сложный комплекс. 4.1.2. Основные понятия и определения сетевого планирования 4.1.2.1. Постановка задачи оптимального управления техническим процессом подготовки производства Сетевая модель представляет собой ориентированный граф G(X,U), где задано множество вершин – событий: X={0,1,2,i,...,j,...}, каждая из которых соответствует началу i или завершению j работы uij, и множество дуг, соответствующих отдельным работам uij. Каждая работа uijєU характеризуется длительностью τij, стоимостью выполнения cij, интенсивностью потребления ресурсов rijm или требуемым объемом ресурса Rijm, где m=1,...,M – виды потребляемых ресурсов. К ресурсам относятся рабочая сила, материалы, полуфабрикаты, оборудование, деньги и т.д. На практике техническая подготовка производства ведется обычно не по одному, а по нескольким взаимосвязанным изделиям k=1,...,N. В этом случае в качестве математической модели процесса удобно использовать многосетевой граф G, состоящий из автономных подграфов G1, G2,..., GN. Известно, что множество автономных подграфов с помощью фиктивных дуг, не усложняя постановки задачи, можно преобразовать в односвязный граф. При описании работ такого графа к описанию его параметров добавляется индекс k, соответствующий номеру нового изделия. Задача оптимального управления техническим процессом подготовки ставится обычно в одной из следующих разновидностей. Найти 1)   минимальный срок выполнения комплекса мероприятий ТПП при ограничениях на уровень наличных ресурсов; 2)   минимальную стоимость выполнения комплекса мероприятий подготовки производства при ограничениях на сроки его выполнения и на уровень наличных ресурсов; 3)   минимальный уровень потребления ресурсов или дефицитных ресурсов при ограничениях на стоимость и на сроки выполнения мероприятий технической подготовки производства. В значительной степени осложняет решение этой задачи вероятностный характер значений таких основных параметров модели, как длительность выполнения работ и интенсивность потребления ресурсов. 4.1.2.2. Основные понятия сетевой модели: работы Перед рассмотрением некоторых задач сетевого планирования введем основные понятия и определения. Графическое изображение сетевой модели в виде ориентированного графа называется сетевым графиком. Любой процесс, происходящий во времени, называется работой. Все работы могут быть разделены на действительные работы, ожидания, фиктивные работы (зависимости). Под действительными работами понимают трудовой процесс, требующий ресурсов и имеющий некоторую продолжительность. Основной характеристикой действительной работы является объем работы, который может быть выражен трудоемкостью в человеко-днях, физическим объемом, стоимостью и т.д. Ожидание – это некоторый процесс, не требующий ресурсов, но имеющий некоторую продолжительность. Фиктивные работы (зависимости) не требуют ресурсов и имеют нулевую продолжительность. Они используются для обозначения логических связей между действительными работами. На графике они обозначаются штриховыми линиями. 4.1.2.3. Основные понятия сетевой модели: события Событие – это результат выполнения работ, оно не имеет продолжительности и не потребляет ресурсов. Формулировка события записывается в совершенной форме (т.е. что-то сделано, выполнено, закончено). На сетевом графике выделяют исходное, промежуточные и завершающее события. Исходное событие указывает на факт начала выполнения всего комплекса работ, описываемого сетевой моделью. Оно не имеет предшествующих работ. Промежуточное событие представляет собой результат окончания одной или нескольких работ, который обеспечивает возможность начать одну или несколько последующих. Завершающее событие указывает на факт окончания всего комплекса работ. Оно не имеет следующих за ним работ. Рис. 4.1 Сетевой график В сетевой модели может быть одно или несколько целевых событий, означающих достижение целей, основных или промежуточных. Число целевых событий характеризует комплекс либо как одноцелевой, либо как многоцелевой. Кроме того, в целевой модели могут быть выделены контрольные события, выполнение которых является существенным для задач планирования. Для этих событий может планироваться и дата свершения. 4.1.2.4. Основные понятия сетевой модели: пути Любая последовательность работ u12, u23,...,un-1n, в которой конечное событие предыдущей работы является начальным событием последующей работы, называется путем и обозначается L  с перечислением всех событий, входящих в данный путь L (1,2,3,...,n). Различают: -       полный путь; -       путь, предшествующий событию; -       путь, следующий за событием; -       путь между событиями; Полный путь – это последовательность работ, соединяющих исходное и завершающее события. На рис. 4.1 полные пути L(0,1,4,6), L(0,2,4,6), L(0,2,6), L(0,3,5,6). Путь, предшествующий событию – это последовательность работ, соединяющих исходное и рассматриваемое события. Так у события 4 два предшествующих пути: L(0,1,4) и L(0,2,4). Путь, следующий за событием – это последовательность работ, соединяющих рассматриваемое и завершающее события. У события 2 два следующих за событием пути: L(2,4,6) и L(2,6). Путь между событиями – это последовательность работ, соединяющих два события, из которых ни одно не является не исходным, не завершающим. На рис. 4.1 пути между событиями: L(1,4), L(2,4), L(3,5). 4.1.2.5. Правила построения сетевой модели При построении сетевой модели необходимо пользоваться некоторыми правилами. Приведем наиболее нетривиальные. 1)    Если работы A1, A2,...,An начинаются и заканчиваются одними и теми же событиями, то для установления однозначного соответствия между работами и их обозначениями вводится n-1 фиктивная работа. 2)    Если работа C следует за двумя параллельно ведущимися работами A и B, а работа D только за работой В, то вводится одна фиктивная работа. Рис. 4.3 Логическое следование работ 3)    В сетевых моделях не должно быть «хвостов», «тупиков» и «контуров». Рис. 4.4 Ошибки в построении сетевых графиков 4)    В сетевых моделях следует соблюдать определенную последовательность в нумерации событий от исходного к завершающему. Наибольшее распространение при этом получил алгоритм введения порядковой функции на графе. 4.1.3. Временные, стоимостные и ресурсные параметры сетевой модели 4.1.3.1. Временные параметры сетевой модели Продолжительность выполнения работы непосредственно связана с ресурсами, необходимыми для ее выполнения. Чем больше ресурсов отпущено на выполнение работы, тем меньше ее длительность. Если при выполнении какого-либо комплекса работ ресурсы практически не ограничены, то для решения таких задач используют сетевые модели без учета ресурсов. Метод решения таких задач наиболее прост. Наряду с продолжительностью выполнения работ к временным параметрам сетевой модели относят: -       момент начала выполнения комплекса работ – это минимальный из моментов начала работ комплекса; -       момент завершения комплекса работ – максимальный из моментов  окончания работ комплекса; -       продолжительность выполнения комплекса работ – промежуток между моментами начала и завершения комплекса; -       продолжительность пути – сумма продолжительностей выполнения всех работ пути; -       директивные сроки – верхние ограничения моментов свершения целевых или контрольных событий; -       ранние и поздние сроки свершения отдельных событий; -       ранние и поздние сроки начала и окончание работ комплекса; -       резервы работ и событий. 4.1.3.2. Стоимостные параметры сетевой модели К стоимостным параметрам сетевой модели относят информацию о затратах, которые связаны с количеством используемых на работе ресурсов. Денежное выражение этих затрат и называется стоимостью работы. Обычно учитывают прямые и косвенные затраты. Прямые затраты – это затраты материальных и трудовых ресурсов, предназначенных для выполнения данной работы. Косвенные – это затраты, предусмотренные на содержание и организацию работы управленческого персонала, потери от замораживания средств от момента вложения их в проект до сдачи выполненного проекта в эксплуатацию. Иногда в сетевых моделях используют зависимость стоимость-время, учитывающую влияние условий выполнения работы на ее продолжительность и стоимость, причем обычно стоимость работ убывает с возрастанием продолжительности. 4.1.3.3. Ресурсные параметры сетевой модели Ресурсы, используемые для выполнения работ, включают материалы, полуфабрикаты, различное технологическое оборудование, топливо, трудовые ресурсы (различных специалистов). Все ресурсы делятся на два типа: -       складируемые; -       нескладируемые; Складируемые ресурсы (или ресурсы типа материалов) – это такие ресурсы, которые, будучи недоиспользованными в данный момент времени, могут быть использованы в любой последующий момент времени (материалы, полуфабрикаты, топливо, сырье, финансовые ресурсы и т.д.). Нескладируемые ресурсы (или ресурсы типа мощности) – это такие ресурсы, которые, будучи недоиспользованными в данный момент времени, не могут быть использованы в дальнейшем (трудовые ресурсы, технологическое оборудование, производственные площади и т.д.). В качестве количественной характеристики потребности складируемого ресурса для выполнения работы чаще всего используется число, характеризующее общее количество данного вида ресурса в натуральном выражении, обеспечивающее всю работу целиком. Однако в связи с тем, что для одних работ ресурс может потребоваться сразу в момент их начала, а для других – равномерно в течение их выполнения, иногда в качестве количественной характеристики потребности в складируемом ресурсе используется зависимость потребного количества Rij от объема выполнения работы Qij (рис. 4.5а). Рис. 4.5 График потребления ресурса (а) и график интенсивности потребления ресурса (б) Потребность какого-либо вида складируемого ресурса для выполнения всего комплекса работ определяется сложением потребностей отдельных работ сетевой модели, использующих данный вид ресурса. Этой потребности соответствует потребный график поставок данного вида ресурса, в котором указываются моменты поступления и соответствующие размеры поставок. Потребность работы в нескладируемом ресурсе чаще всего задается количеством единиц ресурса, используемых в единицу времени, т.е. интенсивностью потребления ресурса на работе uij - rij. Такая потребность описывается функцией потребления ресурса во времени (рис. 4.5б). В случае если на работе используется один вид ресурса, то объем работы можно выразить через интенсивность потребления и продолжительность работы в виде площади под графиком интенсивности потребления ресурса  Qij = rij tij. Потребность какого-либо вида нескладируемого ресурса для всего комплекса работ определяется графиком общей интенсивности потребления ресурса в каждый момент времени. Лекция 4.2. Детерминированная временная сетевая модель страница 1 4.2.1. Ранние и поздние временные характеристики модели 4.2.1.1. Понятие критического пути Рассмотрим простейшую и одновременно основную модель, на которой базируются все остальные типы моделей, одноцелевую детерминированную модель с учетом только времени. Исходными данными в этой модели являются: -       последовательность выполнения работ; -       продолжительность всех работ; Характерный сетевой график модели изображен на рис. 4.6. Продолжительность соответствующих работ проставлена над дугами. Исследование модели начнем с определения ранних и поздних временных характеристик модели. Зная продолжительность каждой работы, можно определить продолжительность всех полных путей модели. Полный путь, имеющий наибольшую продолжительность, называется критическим. Продолжительность критического пути называют критическим временем tкр. Критическое время – это минимальное время, в течение которого может быть выполнен весь комплекс работ: Работы, принадлежащие критическому пути, называют критическими. На графике 4.6 tкр = max (t[L(0,3,5)], t[L(0,1,3,5)], t[L(0,3,4,5)], t[L(0,1,3,4,5)], t[L(0,2,5)]) = t[L(0,2,5)] = 10. 4.2.1.2. Определение раннего срока наступления события Ранним сроком наступления события j Tjp будем называть такой момент времени, раньше которого событие не может произойти. Tjp равен максимальному значению из продолжительностей путей, предшествующих событию j: 4.2.1.3. Определение раннего срока начала и окончания работ Ранним сроком начала работы uij tijрн называется такой момент времени, раньше которого работа не может быть начата. Для работ нулевого ранга (начинающихся в исходном событии) этот параметр равен нулю. Для остальных работ: На рис. 4.6 Ранним сроком окончания работы uij tijро называется такой момент времени, раньше которого работа не может быть окончена. Отсюда может быть получена формула, связывающая ранний срок наступления события j с ранним сроком окончания работ uij. 4.2.1.4. Определение позднего срока наступления события Для расчета позднего срока наступления события Tjп принимается, что для завершающего и исходного событий: а для остальных событий - определяется из условия обеспечения свершения завершающего события в заданный срок, т.е. в tкр: Здесь Lj(j-n) – пути, следующие за событием j. Для событий, принадлежащих критическому пути Tjп = Tjp. На рис. 4.6 T3п = 10 - t[L(3,4,5)] = 10 – 2 = 8. 4.2.1.5. Определение позднего срока  начала и окончания работ Поздним сроком окончания работы uij tijпо называется такой момент времени, к которому должна быть закончена работа, чтобы обеспечить свершение завершающего события в заданный срок: Поздним сроком начала работы uij tijпн называется такой момент времени, в который должна начаться работа, чтобы она могла быть окончена к позднему сроку окончания tijпо: Отсюда также может быть получена формула, связывающая поздний срок наступления события i с поздними сроками начала работ uij: Вычисление ранних сроков производится в направлении от начала сети к ее концу, а поздних сроков – от конца к началу. 4.2.2. Определение резервов времени 4.2.2.1. Определение резерва времени полного пути и резерва времени события Резервы времени существуют в сетевой модели во всех случаях, когда имеется более одного пути разной продолжительности. Резервом времени полного пути P(L) называется разность между критическим временем и продолжительностью данного полного пути: Он показывает, насколько в сумме могут быть увеличены продолжительности всех работ пути без увеличения общего срока выполнения всех работ. На рис. 2.10  P[L(0,3,5)] = 10 – 2 = 8. Все события сети, за исключением событий, принадлежащих критическому пути, обладают резервом времени события. Резерв времени события P(j) определяется резервом времени максимального из полных путей, проходящих через это событие, и показывает на какой предельно допустимый период времени можно задержать наступление события, не вызывая при этом увеличения общей продолжительности проекта: L(j)max – полный путь, проходящий через событие j и имеющий максимальную продолжительность. С другой стороны резерв времени события – это разница между поздним и ранним сроком его наступления: Понятно, что резерв времени событий критического пути равен нулю. На рис. 4.6.  P(3) = P[L(0,1,3,4,5)] = tкр - t[L(0,1,3,4,5)] = 10 – 4 = 6. Или, так как  T3p = 2  и  T3п  = 8, то  P(3) = 8 – 2 = 6. 4.2.2.2. Определение полного резерва времени работы Полный резерв времени работы uij Pп(i,j) показывает, на какой предельно допустимый интервал времени может быть увеличена продолжительность работы без увеличения продолжительности всего комплекса работ. Определяется с одной стороны как: здесь Tjп - Tip – максимально возможное время выполнения работы uij, а с другой стороны, как: Здесь L(i,j)max – полный путь, проходящий через данную работу и имеющий максимальную продолжительность. Полный резерв времени для критических работ равен нулю. При оперативном управлении комплексом работ следует иметь в виду, что если полный резерв времени использован на определенной работе, то это может вызвать изменение сроков наступления некритических событий и уменьшить полные резервы времени для некоторых работ. На рис. 4.6:      Pп(1,3) = P[L(1,3)max] = tкр - t[L(0,1,3,4,5)] = 10 – 4 = 6;                             Pп(4,5)=T5п  - T4p  - τ45 = 10 – 3-1 = 6. Для работ рассматриваются также частные резервы времени 1-го и 2-го видов и независимый резерв времени. 4.2.2.3. Определение независимого резерва времени работы Под независимым резервом времени работы uij Pн(i,j) понимается часть ее полного резерва, которая сохраняется, если начальное событие данной работы наступит в поздний срок Tiп, а конечное - в ранний Tjp: Он показывает, какая часть полного резерва времени работы может быть использована на увеличение ее продолжительности при условии, что это увеличение не вызовет изменения позднего срока свершения ее начального события и раннего срока наступления ее конечного события. И, следовательно, не вызовет сокращения резервов времени ни у одной из работ, предшествующих и последующих за данной работой. Независимым резервом времени обладают не все работы, а только те, в начальных и конечных событиях которых пересекаются полные пути различной продолжительности. Причем необходимо, чтобы работа, принадлежала тому из них, который имеет меньшую продолжительность. 4.2.2.4. Определение частного  резерва времени  1-го вида Введем понятие частных резервов времени работы. Они также образуются в местах пересечения путей различной продолжительности у работ, принадлежащих пути с меньшей продолжительностью. Частный резерв времени 1-го вида  образуется у работ, непосредственно следующих за событием, в котором пересекаются пути различной продолжительности. Частный резерв времени 1-го вида показывает, какая часть полного резерва времени работы может быть использована для увеличения ее продолжительности при условии, что это увеличение не вызовет изменения позднего срока свершения ее начального события. И, следовательно, не вызовет сокращения резервов времени ни у одной из предшествующих этому событию работ. 4.2.2.5. Определение свободного резерва времени  (частного  резерва 2-го вида Частный резерв времени 2-го вида   который часто называют свободным резервом) образуется у работ, непосредственно предшествующих событию, в котором пересекаются пути различной продолжительности. Частный резерв 2-го вида показывает, какая часть полного резерва времени работы может быть использована на увеличение ее продолжительности при условии, что это увеличение не вызовет изменение раннего срока свершения ее конечного события и, следовательно, сокращение резервов времени ни у одной из последующих за этим событием работ. Он есть у всех работ, имеющих независимый резерв, а также у некоторых работ, имеющих полный, но не имеющих независимый резерв. На графике 4.6 такой резерв есть у работы u45. Свободный резерв времени работы можно использовать при оптимизации сетевого графика.  4.2.3. Расчет и исследование сетевой модели 4.2.3.1. Построение линейной диаграммы сетевой модели (графика Ганта) Расчет сетевой модели заключается в определении -       критического времени и критического пути; -       полных, независимых и частных резервов времени работ; -       резервов времени событий. Удобно исследование сетевой модели изображать линейной диаграммой (графиком Ганта), в которой каждая работа – отрезок, параллельный оси времени. Длина этого отрезка равна продолжительности работы в выбранном масштабе. События i и j начала и конца работы uij ставят в начале и конце соответствующего отрезка. Отрезки располагают один над другим, снизу вверх, в порядке возрастания индексации. Момент наступления исходного события равен 0. Каждый отрезок (i,j) размещают на диаграмме таким образом, чтобы его начало совпало с самым правым концом всех отрезков, входящих в событие i. На рис. 4.7 представлена линейная диаграмма сетевого графика, изображенного на рис. 4.6. Не трудно заметить, что исходная линейная диаграмма отражает такой ход ведения работ, при котором все работы начинаются в свои ранние сроки. С помощью линейной диаграммы можно определить критический путь, критическое время, резервы времени всех работ и т.д. Критический путь представляет собой цепочку отрезков-работ, соединяющих завершающее событие самого правого отрезка с исходным. Критическое время равно самой правой координате всех отрезков линейной диаграммы. Полный резерв времени работы равен максимальному сдвигу соответствующего отрезка вправо, который при этом не приведет к увеличению критического времени. Так, Pп(4,5) = 6,  Pп(1,3) = 6. На диаграмме символами н, I, II обозначены работы, имеющие соответственно независимый и частные резервы 1-го и 2-го вида. Жирной рамкой выделены критические работы. Рис. 4.7 Линейная диаграмма сетевой модели 4.2.3.2. Исследование сетевой модели с использованием графика Ганта После расчета сетевой модели переходят к ее исследованию, целью которого является получение такого графика выполнения работ, который наиболее полно удовлетворяет каким-то критериям. Для этого можно увеличивать длительность или задерживать начало выполнения работ, во-первых, на величину их независимых резервов, что не требует пересчета резервов других работ, во-вторых, на величину их свободного резерва (т.е. частного резерва 2-го вида), так как это не влечет за собой пересчет резервов последующих работ и т.д. Тем самым от исходной переходят к другим линейным диаграммам, в которых работы могут либо начинаться не в свои ранние сроки, либо выполняться более начальной продолжительности, однако при этом срок завершения всего комплекса работ не меняется, оставаясь равным критическому. Одними из важнейших операций при анализе сетевого графика являются расчеты коэффициентов напряженности путей. Коэффициент напряженности пути kн – это отношение продолжительности несовпадающих (заключенных между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данные работы, а другим критический путь. Он позволяет определить степень трудности выполнения в срок каждой группы работ некритического пути. Если совпадающую с критическим путем величину отрезка пути обозначить t'(Lкр), а протяженность максимального пути, проходящего через данные работы, t(Lmax), то коэффициент напряженности данного пути В случае последующего оптимизации графика (при прочих равных условиях, например при одинаковой потребности в ресурсах)  в первую очередь используются резервы с путей, имеющих наименьший коэффициент напряженности. Начало формы 4.3.1. Вероятностная временная сетевая модель 4.3.1.1. Две методики задания параметров распределения продолжительности работ в вероятностной сетевой модели Второй также достаточно часто встречающейся сетевой моделью является одноцелевая временная вероятностная модель. Эта модель отличается тем, что продолжительности работ задаются как случайные величины. Такая модель более близка к условиям подсистемы ТПП. В настоящее время существуют две методики задания параметров распределения продолжительности работ: -       трехоценочная; -       двухоценочная. При использовании первой методики эксперт задает 3 оценки продолжительности работы: -       оптимистическую τijmin; -       наиболее вероятную τijнв; -       пессимистическую τijmax. Наиболее вероятная оценка – это время, необходимое для выполнения данной работы при нормальных, чаще всего встречающихся условиях (определяется первой). Оптимистическая оценка – это время, необходимое для выполнения работы при наиболее благоприятном стечении обстоятельств (определяется второй). Пессимистическая оценка – это время, необходимое для выполнения работ при неблагоприятных условиях. Как вы знаете, продолжительность работы связана с количеством ресурсов, выделяемых на ее проведение. Поэтому необходимо отметить, что для определения временных характеристик продолжительности работы эксперты должны руководствоваться максимальными значениями ресурсов. При использовании второй методики исключается наиболее вероятная оценка τijнв, определение которой вызывает у экспертов особые трудности и пользуются только двумя оценками τijmin и τijmax. 4.3.1.2. Оценка математического ожидания и дисперсии продолжительности работ в вероятностной сетевой модели На основе опытных данных установлено, что в большинстве случаев законы распределения продолжительностей работ обладают положительной асимметрией, распределение более круто в области τijmin. Это позволило из множества теоретических законов распределения выбрать закон β-распределения, кривая плотности которого имеет вид, представленный на рис.4.8. При этом оценки математического ожидания и дисперсии β-распределения определяются следующим образом: По второй методике: 1)     ожидаемого времени выполнения работ τijож и оценки дисперсии σ2ij. Первый этап расчета временной вероятности модели заключается в определении: 2)     всех временных параметров модели по тем же алгоритмам, что и у детерминированной временной модели, заменив τij на τijож. 4.3.1.3. Определение вероятности наступления событий сети не позднее директивных сроков Второй этап расчета заключается в определении вероятности наступления каждого события сети не позднее директивных сроков. Обозначим через μi – случайную величину, характеризующую ранний срок наступления события i. Если событие i связано с исходным событием лишь одним путем L(0i), то оценка математического ожидания μiопределяется суммой ожидаемых продолжительностей работ, принадлежащих этому пути tож[L(0i)], а оценка дисперсии σ2(μi) представляет собой сумму дисперсий продолжительностей тех же работ. В случае, если имеется более одного пути, предшествующего i-му событию, то упрощенно предполагается, что в этом случае μi и σ2(μi) вычисляется с использованием характеристик предшествующего пути, имеющего максимальную продолжительность max t[L(0i)]. Если же несколько путей имеют максимальную продолжительность, то для определения дисперсии выбирается путь с максимальной дисперсией продолжительности, так как он характеризуется большой неопределенностью, а, следовательно, дает более надежный результат. Таким образом, где k означает работы, принадлежащие самому длинному пути, предшествующему событию i. При этом предполагается, что величина μi является суммой независимых случайных величин, и, следовательно, согласно центральной предельной теореме, распределение μi близко к нормальному, а величины (4.13) являются оценками математического ожидания и дисперсии. Поскольку μi есть ранний срок наступления события i, то это событие наступит не позднее директивного срока TДi с вероятностью   P( μi ≤ TДi ). Переходя к стандартному нормальному распределению величины Для величины pn существуют вполне определенные границы допустимого риска. При pn >0,65 можно утверждать, что на работах критическоко пути есть избыточные ресурсы, следовательно общая продолжительность работ может быть сокращена. При pn <0,35 Опасность срыва заданного срока наступления завершающего события настолько велика, что необходимо повторное планирование с перераспределением ресурсов, т. е. оптимизация сетевого графика. Обычно в качестве директивных сроков всех событий кроме завершающего используют поздний срок его свершения Tiп. Для завершающего события величина TД определяется лицом, принимающим решение, причем TnPож = tкр. Здесь Ф – стандартное (нормированное) нормальное распределение величины xi, Ki – квантиль данного распределения. 4.3.2. Детерминированная сетевая модель с учетом стоимости. 4.3.2.1. Общая характеристика сетевой модели с учетом стоимости Следующей моделью, которую мы подробно рассмотрим, является детерминированная сетевая модель с учетом стоимости. Эта модель отличается от временной введением зависимости «стоимость (затраты)-продолжительность» для каждой работы. При этом рассматриваются только элементы прямых затрат. Типичная линейная зависимость, используемая для большинства проектов, имеет следующий вид: Точка B соответствует нормальному режиму  выполнения работы. Точка А соответствует максимальной интенсивности использования ресурсов. Использование нелинейной зависимости существенно усложняет вычисления, в этом случае желательно аппроксимировать ее кусочно-линейной, а работу разбить на части, каждая из которой соответствует одному линейному отрезку. Для решения такой задачи обычно пользуются: -       либо эвристическим методом последовательного сжатия плана; -       либо методами линейного программирования. 4.3.2.2. Расчет сетевой модели с учетом стоимости эвристическим методом. В первом случае для всех работ принимается нормальная продолжительность, производится временной расчет сети и фиксируется необходимая сумма затрат. На следующем этапе для сокращения продолжительности проекта при минимально возможных затратах необходимо в максимально допустимой степени сжать ту критическую работу, у которой наклон зависимости “стоимость-продолжительность” наименьший. Величина, на которую можно сжать продолжительность работы, называется пределом сжатия и определяется, с одной стороны, пределом интенсивности, т.е. точкой режима максимальной интенсивности (точка А на рис.4.9), а с другой стороны, пределом резерва времени работы, который определяется моментом превращения какой-либо некритической работы в критическую, что обычно определяется по равенству нулю полного резерва времени работы. Минимальное из этих двух значений и определяет предел сжатия. В результате «сжатия» работы получают новый календарный план, возможно с новыми одним или несколькими критическими путями. Стоимость проекта будет выше стоимости предыдущего календарного плана. Далее этот план вновь подвергается сжатию. Причем, в случае нескольких критических путей необходимо уменьшать длину всех критических путей одновременно. Определяют минимальный предел сжатия всех критических путей и на него сжимают оба пути. Описанная процедура повторяется до тех пор, пока все работы хотя бы одного критического пути не будут сжаты до режима максимальной интенсивности, либо не будет достигнут директивный срок окончания работ. 4.3.2.3. Расчет сетевой модели с учетом стоимости методом линейного программирования Во втором случае составляется математическая модель задачи в следующем виде. Введем дополнительные обозначения: n – число работ на критическом пути; cij – стоимость выполнения работы (cijmax – максимальная, cijmin – минимальная стоимости); τij – продолжительность выполнения работы (τijmax, τijmin – максимальная и минимальная продолжительности работы соответственно); TД – директивно заданный максимальный срок окончания всего комплекса работ. Аналитическое выражение для линейной зависимости “стоимость-продолжительность” будет иметь вид: Общая стоимость выполнения работ критического пути: Задача формулируется так: найти продолжительности работ τij, обращающие в минимум суммарную стоимость работ критического пути. Для решения такой оптимизационной задачи могут быть использованы методы линейного программирования. Однако, следует заметить, что решение задачи сетевого планирования с учетом стоимости данным методом допустимо при небольших изменениях плана, не влекущих за собой изменения критического пути. В случае же такого изменения необходим пересчет критерия оптимальности и ограничений. 4.3.2.4. Учет косвенных затрат в  стоимостной сетевой модели При использовании и одного и другого метода после расчета сетевой модели с учетом только прямых затрат, необходимо добавить к этим затратам косвенные. При этом считается, что косвенные затраты с увеличением продолжительности выполнения проекта должны возрастать. Сумма прямых и косвенных затрат на проект в оптимальном плане должна быть минимальной. Сказанное можно иллюстрировать следующим графиком. Рис. 4.10 Суммарные зависимости «затраты-продолжительность», на графике             суммарные прямые затраты,            суммарные косвенные затраты,  суммарные полные затраты. Начало формы 4.3.3. Основные подходы к расчету сетевых моделей с учетом ресурсов 4.3.3.1.Постановки задачи оптимизации распределения ресурсов в сетевых моделях Расчет сетевых моделей с учетом ресурсов сводится в большинстве случаев к оптимизационной задаче распределения ресурсов. Наибольшее распространение получили следующие две постановки таких задач: 1)   минимизировать время осуществления комплекса работ при выполнении заданных ограничений на используемые ресурсы; 2)   минимизировать уровни потребления дефицитных ресурсов при ограничениях на используемые ресурсы и сроки выполнения комплекса работ. Вторая постановка часто встречается в следующей разновидности: минимизировать максимальные значения потребляемых ресурсов при ограничениях на используемые ресурсы и сроки выполнения проекта. Данный критерий позволяет выровнять потребности в ресурсах на протяжении всего срока выполнения проекта, что особенно важно для нескладируемого ресурса (например, для трудовых ресурсов). 4.3.3.2. Исходные параметры сетевой модели с учетом ресурсов Запишем математическое выражение сетевой модели с учетом ресурсов. Исходными данными являются: -       множество работ комплекса uij, i=1,...,n1; j=2,...,n, представленных в виде сетевой модели (графа) с n+1 событиями (вершинами графа); -       нормативное время выполнения работы uij – τij; -       общее количество s-го вида (s=1,...,m) складируемого ресурса, необходимое для выполнения работы uij -Rsij. Причем, необходимо отметить, что для одних работ конкретный s-ый ресурс может потребоваться сразу в момент их начала, а для других равномерно (или по другому более сложному закону) в течение ее выполнения. Во втором случае  Rsij = rsij τij,  или где rsij(t) – интенсивность потребления складируемого ресурса. -       интенсивность потребления k-го вида k=1,...,L нескладируемого ресурса при выполнении uij работы rkij(t). Эта интенсивность описывается функцией потребления k-го ресурса во времени; -       директивный срок выполнения проекта TД; -       интенсивность поставок s-го вида складируемого ресурса, qs(t) и величина s-го складируемого ресурса в начальный момент времени Qs0. Задается графиком поставок; -       допустимое значение суммарной интенсивности потребления k-го нескладируемого ресурса в каждый момент времени Rk(t).Задается графиком допустимой интенсивности использования ресурсов. Для упрощения задачи можно предположить, что: 1)       для части работ конкретный складируемый ресурс требуется сразу в момент их начала, а для других равномерно в течение ее выполнения. Для первых  вводят Rsij, для вторых – rsij 2)       интенсивность потребления k-го нескладируемого ресурса на работе uij предполагается постоянной rkij(t) = const 3)       поставки s-го складируемого ресурса предполагаются равномерными qs(t) = const 4)       допустимая интенсивность использования ресурса также предполагается постоянной Rk(t) = const. 4.3.3.3. Критерии оптимизации, используемые при расчете сетевых моделей с учетом ресурсов В качестве неизвестных переменных модели можно взять: tнij – момент времени начала работы uij, либо tоij – момент окончания работы uij. Найдя эти неизвестные можно рассчитать остальные временные (в частности, Ti  моменты наступления событий) и ресурсные (в частности, графики расходования складируемых ресурсов и графики интенсивности потребления нескладируемых ресурсов) параметры модели. Можно рассмотреть следующие критерии оптимизации. Для первой постановки: Для второй постановки: Здесь s1  m,  k1 L – количество типов дефицитных ресурсов (складируемых и нескладируемых соответственно). Если используется разновидность второй постановки, то s1 = m, k1 = L, т.е. как бы все ресурсы являются дефицитными. Можно использовать квадратичный критерий: 4.3.3.4. Ограничения при расчете сетевых моделей с учетом ресурсов На задачу распределения ресурсов наложены следующие ограничения: 1.   Соотношения, определяющие топологию сетевой модели, например, следующего типа: 2.    Суммарная потребность всех работ в нескладируемых ресурсах (график интенсивности потребления) не должна превышать их наличия в каждый момент времени (график допустимой интенсивности использования). 3.    Суммарный расход складируемых ресурсов на выполнение всех работ, начатых до момента , не должен превышать общего их количества, запасенного к моменту  в результате поставок с учетом наличия определенного его объема в начальный момент. 4.    Для второй постановки добавляется ограничение на директивное время выполнения проекта: -       методами математического программирования: линейное, целочисленное линейное, нелинейное, динамическое, статистическое (с использованием случайного поиска) программирование и т.п. [5] стр. 110-111, [41]; Задачи распределения ресурсов могут решаться: -       эвристическими методами: метод последовательного фронтального распределения [4] стр. 166-168, метод последовательного растяжения плана [4] стр. 166, метод последовательной корректировки плана [4] стр. 164 и т.п.; -       комбинированными методами, которые основываются на сочетании методов математического программирования и эвристических методов [4] стр. 164. Конец формы Конец формы