5432-1 (707056), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

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

Для решения задачи, обусловленной переменной структурой графа, используется метод последовательных назначений, применяемый в обычных задачах целочисленного программирования [18].

3. Алгоритм.

Основные идеи алгоритма представлены пунктами 1 51.

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

1. Принять f2_j=1,

2. Определить множество работ свободных в данный момент времени от условий согласно технологии проектирования проектов.

(6) .

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

если нет, то принять иперейти к п.33.

4. Принять .

5. Построить вектор-строку возможных приращений целевой функции (1).

(7) где

Физически означает возможное приращение целевой (1) за счет того, что на выполнение работы множества назначается одна единица ресурса.

6. Определить максимальное приращение целевой функции (1).

(8) , .

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

если нет к п.14.

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

(9) если

9. Проверить выполняется ли условие Если выполняется, перейти. к п.10 c целью назначения; если b_i = 0, то исключить данную работу из дальнейшего рассмотрения, приняв , и перейти к п. 6.

10. Осуществить назначение ресурсов на j -ю работу.

(10)

(11) , , .

При очередном назначении накапливается число ресурсов, а также выполняемый объем работы в единицу времени.

11. Изменить число свободных ресурсов.

(12) , , .

12. Проверить, не исчерпаны ли свободные ресурсы. Если , то перейти к п.13.

В противном случае к п.14.

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

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

14. Выделить из множества подмножество работ, обеспеченных ресурсами.

(13)

15. Определить множество работ, начало которых совпадает с моментом времени ..

(14) где

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

, где

(15) .

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

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

(16) .

18 Зафиксировать код j-й работы множества .

(17)

.19. Определить срок начала работ множества

(18)

(19) если

20. Вычислить продолжительность выполнения работ множества

(20) .

(21) если

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

(22)

(23)

22. Для работ множества определить число назначенных ресурсов.

(24)

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

если нет, то принять и перейти к п. 32.

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

(25) , где

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

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

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

26. Определить возможное число ресурсов, которые могут переходить на j - ю работу множества с других работ в момент времени ,

(26)

(27) .

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

(28) , где .

множество оконченных работ к моменту времени определяется на предыдущем шаге пунктом 45.

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

28. Зафиксировать код работы и вид ресурса для работ множества

(29)

(30)

29. Определить число ресурсов, которые могут переходить с работы множества на выполнение других работ ,

(31)

(32)

30. Распределить работы множества между множествами ресурсных условий .

(33) ,

(34)

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

(35)

32. Определить множество работ, обеспеченных ресурсами, но окончание каждой из которых еще не наступило.

(36)

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

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

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. Исходные данные.

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

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

Характеристики

Список файлов реферата