Оптимизация структуры стохастического графа c переменной интенсивностью выполнения работ (стр. 4 из 6)

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

34. Проверить выполняется ли условие

. Если выполняется, перейти к п. 35; если нет

к п. 40.

35. Исключить из множества

работы множества .

(37)

36. Определить не выполненный объем j - ой работы множества

к моменту .

(38)

если

37. Определить продолжительность j-й работы множества

(39)

38. Определить срок окончания j-й работы множества

(40)

если

39. Включить в множество ресурсных условий окнченную часть j- й работы к моменту

времени

(41)

40. Зафиксировать минимальное значение срока окончания работ множества

(42)

41. Выделить из множества

. подмножество работ со сроком окончания в момент времени .

(43)

42. Запомнить число освободившихся ресурсов с работ множества

(44)

43. Исключить работы множества

из условий других работ, обусловленных технологией проектирования проектов.

(45)

44. Исключить работы множества

из множества работ, обеспеченных ресурсами, а также из общего списка работ.

(46)

(47)

45. Присоединить оконченные работы в момент времени t2 к работам, каждая из которых окончилась ранее.

(48)

46. Включить работы множества

в множество оконченных работ .

(49)

, где .

47. Определить множество работ, каждая из которых на шаге

может быть включена в ресурсный граф.

(50)

, где

48. Пронумеруем работы множества

, =1, 2, . . . , ,

число работ, включенных в ресурсный граф на шаге .

49. Определить код работы в ресурсном графе с учетом разбивки работ на части.

(51)

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

50. Произвести перекодирование условий работ множества

51. Проверить выполняется ли условие

.Если условие выполняется, то принять и перейти к п. 2;

если нет

к п. 52.

52. Конец.

4. Пример.

На разработку, состоящую из 2-х параллельно выполняемых проектов, выделено два различных вида ресурсов по 2 единицы каждого. Исходные данные решения задачи приведены в табл. 1, где код работы

состоит из кода проекта и кода работы в проекте. Первый проект содержит решающий результат с двумя альтернативами: 14,15.

Каждой альтернативе приписана aприорная вероятность: 0,7, 0,3. Требуется в области

определить экстремальный граф, включающий альтернативу 14, вероятность которой равна 0,7. В табл. 2, где код работы с учетом разбивки работ на части, представлен экстремальный ресурсный граф, полученный алгоритмом, основные идеи которого были изложены выше. Более подробно пример рассматривается в [20, 21].

Таблица 1. Исходные данные.

j		X_j	c_j			D_j
1	11	0	1	1	2	6
2	12	0	1	2	2	12
3	13	11	1	1	2	8
4	14	13, 12	1	2	2	4
5	15	13, 12	1	1	2	10
6	21	0	1	1	1	4
7	22	0	1	2	1	2
8	23	21	1	1	2	10
9	24	22	1	2	2	4

Таблица 2. Экстремальный ресурсный граф.

				n_j
21	21	0	1	1	0	4	4
11	11	0	1	1	0	4	4
11	12	21, 11	1	2	4	1	5
12	13	0	2	1	0	2	2
12	14	13	2	0	2	2	4
12	15	14, 23	2	2	4	5	9
22	22	0	2	1	0	2	2
13	16	12	1	2	5	4	9
24	23	22, 13	2	2	2	2	4
14	17	16, 15	2	2	9	2	11
23	24	16, 21	1	2	9	5	14

Обоснованность задания критерия оптимальности (1) в виде графа следует из теоремы 1.