Закрепление работ сетевого графа за ресурсами и  формирование расписания их выполнения

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

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

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

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

В качестве критериальных условий могут быть:

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

2) приоритетное выполнение работ, принадлежащих критическому пути;

3) приоритетное выполнение работ, имеющих наибольшую трудоемкость;

4) приоритетное выполнение работ, имеющих наименьшую трудоемкость;

5) приоритетное выполнение работ, требующих наименьшего (наибольшего) количества источников ресурсов;

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

Кроме того, может быть выбрана любая комбинация этих критериев.

В качестве ограничительных условий могут выступать:

1) наличное количество источников ресурсов;

2) последовательность выполнения работ сетевого графа, то есть непосредственно следующие и следующие за данной работы не могут быть выполнены не только ранее этой работы (i, j), но и предшествующих ей (l, i) – х;

3) общая потребность в источниках конкретного ресурса по всем одновременно выполняемым работам в момент времени  не может превышать фактическое наличие источников этого ресурса в данный момент;

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

5) «фиктивные» работы строятся в виде пунктирной перпендикулярной линии, направленной вверх, так как трудоемкость их выполнения и потребность в ресурсе равны нулю;

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

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

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

= 1 –

Пример построения сетевого графа и расчета его параметров

Далее на условном примере выполнены в соответствии с приведенными выше методическими указаниями следующие операции:

· построен сетевой граф;

· закодированы его работы;

· рассчитаны параметры (непосредственно на графе и в табличном варианте);

· осуществлена привязка работ сетевого графа к календарю;

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

Исходные данные для расчета параметров сетевого графа

l - i	i -j	t(i, j)	P(i, j)
-	а	5	5
-	б	9	2
-	в	8	3
в, а	г	3	3
а	д	7	2
в, д	е	1	4
в	ж	4	2
б, д, е	з	6	3

Построение сетевого графа