5. СЕТЕВОЕ «ПЛАНИРОВАНИЕ ПРИ СЛУЧАЙНЫХ ВРЕМЕНАХ ВЫПОЛНЕНИЯ РАБОТ. ПРИМЕНЕНИЕ ЭЦВМ

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

Возникают следующие вопросы:

— Какова вероятность того, что фактическое время выполнения комплекса работ Т не превзойдет заданной величины

— Как следует организовать комплекс работ для того, чтобы величина Т не превзошла заданного с достаточно высокой вероятностью?

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

Рассматривается функция этих случайных величин — общее время выполнения всего комплекса работ:

Поставленная задача будет решена, если удастся найти функцию распределения случайной величины Т:

Тогда, подставляя в нее вместо t величину мы найдем искомую вероятность.

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

В дальнейшем нам приходит на помощь сама сложность плана и наличие на критическом пути многих работ. Мы знаем, что при сложении достаточно большого числа независимых случайных величин, распределенных по любым законам и сравнимых по порядку дисперсий, закон распределения суммы оказывается близким к нормальному (центральная предельная теорема). Поэтому, если на критическом пути стоит достаточно большое количество работ (скажем, порядка 5— 6 или более), то на практике можно приближенно считать величину Т распределенной нормально. Ее математическое ожидание будет равно

где — математическое ожидание времени выполнения работы, а ее среднее квадратическое отклонение:

где — среднее квадратическое отклонение времени выполнения работы.

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

где — функция Лапласа (см. приложение, табл. 1).

Пример 1. При выполнении комплекса работ критическими оказываются работы

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

с математическими ожиданиями

и средними квадратическими отклонениями:

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

Решение. Имеем

Вероятность выполнения комплекса работ в срок

По табл. 1 приложения находим: откуда вероятность выполнения комплекса в срок а 0,94.

Если при случайных изменениях времен может меняться и сам критический путь, задача вычисления вероятности затрудняется. При сравнительно малом числе работ в комплексе эта задача может быть решена аналитическим способом, но при большом их числе расчеты становятся чересчур громоздкими, и на практике оказывается удобнее определять эти вероятности методом Монте-Карло на ЭЦВМ (см. гл. 8). При этом разыгрываются значения случайных времен и для каждой совокупности полученных значений определяется время Т выполнения комплекса работ тем способом, который применяется для неслучайных времен. Получив достаточно большое число N таких реализаций, мы можем непосредственно найти математическое ожидание, дисперсию и среднее квадратическое отклонение случайной величины Т.

Рис. 10.6

Что касается закона распределения, то он в большинстве случаев для сложных сетей оказывается близким к нормальному. Поэтому вероятность выполнения плана в срок может быть вычислена по той же формуле (5.1). Если имеются основания считать закон распределения величины Т не нормальным (так, например, бывает, если рассеивание времени выполнения какой-нибудь одной из критических работ резко превышает рассеивание остальных), то в качестве приближенного значения вероятности можно принять частоту этого события в серии реализаций.

Надо заметить, что подобного рода расчеты могут быть только сугубо ориентировочными, так как на практике обычно законы распределения неизвестны, а получение их по статистическим данным затруднительно. В лучшем случае удается указать для каждого времени его наиболее вероятное значение а также грубо оценить наименьшее («оптимистическое») значение и наибольшее («пессимистическое») значение (рис. 10.6). Что касается самого распределения то его приходится задавать достаточно произвольно, исходя из умозрительных соображений. Например, то что кривая на рис. 10.6 имеет положительную асимметрию (более растянута вправо, чем влево) отражает тот общеизвестный факт, что запаздания по сравнению с плановым сроком могут быть значительно больше, чем опережения.

В заключение остановимся еще на одном вопросе, связанном с применением ЭЦВМ при сетевом планировании. Обычно при выполнении сложных комплексов работ первоначально намеченные планы не выполняются, и их приходится по ходу работы пересматривать. При этом чрезвычайно удобно держать все данные о комплексе — как первоначальный план, так и поступающую информацию о его нарушении — в памяти ЭЦВМ, которая время от времени заново просматривает план работ, находит для каждого момента времени новый критический путь «угрожаемые» по срокам работы и оптимизирует план, указывая, какие именно работы и в какой степени следует форсировать.

Плодотворное применение метода сетевого планирования при организации сложных комплексов работ возможно только при условии непрерывного контроля плана и его оптимизации с помощью ЭЦВМ.