Быстрый поиск

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

(5)

При заданном начальном состоянии системы V(t0) в момент времени t0 необходимо найти в области, определяемой ограничениями: (2)(5), оптимальную траекторию движения(под оптимальной траекторией движения системы мы понимаем экстремальный граф, параметры которого для любого kобеспечивают максимальное значение функции (1)).

Положение j-й работы в графе (1) определяется указанием множества ресурсных условий Zj , . Граф(1) для каждого решающего результата включает только одну альтернативу.

. Обоснованность критерия (1) следует из определения ресурсов нескладируемого типа, которые отпускаются порциями ?квантами¦.Для них характерно то, что неиспользованная или неэффективно использованная часть каждой порции в каждый момент времени пропадает и не переносится на другое время.

Физически критерий (1) означает, что число выполненных работ с учетом их весовых коэффициентов за любой интервал времени должно быть максимальным. Согласно ограничению (2) у-я работа не может начаться раньше окончания своих условий. Для начала любой работы необходимо, чтобы к данному моменту времени были выполнены технологические условия а также свободны ресурсы, обеспечивающие ее выполнение. Ресурсы могут переходить с других работ, которые также для данной работы являются условиями

Система функционирует в дискретном времени и ее состояние в каждый момент определяется набором числовых параметров: ni , Zj,

Принимаются следующие допущения: 1) каждая работа может выполняться с переменной интенсивностью использования ресурсов; 2) выполнение работ может прерываться, даже если они не закончены. Они будут завершены позднее.

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

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

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

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

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

3. Алгоритм.

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

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

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

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

(6) .

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

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

4. Принять .

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

(7) где

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

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

(8) , .

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

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

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

(9) если

9. Проверить выполняется ли условие Если выполняется, перейти. к п.10 c целью назначения; если bi = 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, . . . , прерывается и все ресурсы переходят на выполнение других работ. Выполнение работ указанного множества будет продолжено позже.