Алгоритм задачи сетевого планирования

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

Алгоритм построения сетевого графика

1. Составляется упорядоченная структурная таблица, например, вида (таб.43):

Таблица 43

№ п/п	Работа ai	Опирается на работы	Время ti
	a 1	–	t 1
	a 2	–	t 2
	a 3	–	t 3
	a 4	a 1, a 2	t 4
	a 5	a 1, a 3, a 4	t 5
	a 6	a 2, a 3	t 6
	a 7	a 4	t 7
	a 8	a 4, a 5	t 8
	a 9	a 4, a 5, a 6	t 9
	a 10	a 8, a 9	t 10

2. Записываются математические зависимости связей, взятых из упорядоченной структурной таблицы. Обозначим:

– минимально возможный срок начала работы (время отсчитывается от начала процесса);

– минимально возможный срок окончания работы .

Тогда

,

(1)

где – время выполнения работы .

Допустим, работа опирается на работы , тогда работа не может начаться раньше, чем кончится самая поздняя работа , т.е. можно записать

.

(2)

Применяя формулу (2) и (1) ко всем работам по сети, находятся времена начала и окончания работ , а следовательно и минимальный срок окончания работ .

Вычислим величины и для показанной таблицы:

Работа : ,

Работа : ,

Работа : .

Работа опирается на работы , т.е. она может начаться тогда, когда закончится наиболее поздно кончающаяся из работ :

,	(3)
.	(4)

Для последующих работ :

.

(5)

Так определяются моменты начала и окончания всех работ. Время окончания всех работ, естесственно, равно максимальному из всех времён окончания , т.е.

.

(6)

3. Находится критический путь. Для этого необходимо:

3.1. Найти работу , для которой время окончания максимально, следовательно, найденная работа будет критической и стоять первой от конца;

3.2. Среди формул (3), (4), (5) найти ту, по которой определяется момент начала – найденной критической работы ;

3.3. Величина выражена в виде максимума каких-то времён , …, необходимо найти то время из них, например , на котором достигается этот максимум (если таких времён будет несколько, то берётся любое из них). Работа , соответствующая времени окончания , будет также критической и стоять второй от конца на критическом пути;

3.4. Далее пункты 3.2 и 3.3 повторяются до тех пор, пока не будет найдена критическая работа, стоящая первой от начала процесса.

3.5. Путь составленный из полученных критических работ будет критическим путём.

Следует отметить, что максимум в каких-нибудь из формул (3)¸(5) может достигаться не на одной, а на нескольких работах, поэтому на сетевых графиках может быть не один, а несколько критических путей.

Аналогично отыскиваются некритические работы и дуги и соответствующие им резервы времени.

Дата добавления: 2015-04-29