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

Л. П. Костина, канд. физ. — мат. наук
Санкт — Петербургский государственный университет
Задача распределения ресурсов (нескладируемого типа) на cтохастических сетях (параллельные проекты) сформулирована как обусловленная переменной структурой графа. Предложенный метод решения обеспечивает получение экстремального графа для случая, когда каждая работа многопроектной разработки может выполняться с переменной интенсивностью использования ресурсов. Принципиально новый подход к решению задачи распределения ресурсов на сетях позволяет совершить качественный скачок в области математического обеспечения автоматизированных систем управления, так как создаются предпосылки для использования всех достижений сетевого планирования при управлении ресурсами, которые выполняют параллельные проекты.
1. Введение.
Все известные теории решения задач распределения ресурсов на сетях базируются на комбинаторике, которая приводит либо к анализу бесконечного числа вариантов, либо к привлечению эвристики. Прежде чем приступить к распределению ресурсов производят расчет сетевых графиков, каждый из которых построен на основании технологии и принятой организации работ по каждому проекту. Затем полученные таким образом показатели, а также критические пути используются в качестве подсобного инструмента с целью обеспечения работ ресурсами и получения расписания их выполнения в планируруемом периоде времени [1, 2, 3, 4, 5].
Необоснованность традиционного решения можно легко показать на примерах, иллюстрирющих возникающие при этом парадоксы[6], причина которых состоит в том, что при распределении ресурсов между работами возникают связи по использованию одного и того же ресурса. Поскольку возможны различные варианты перехода каждой единицы ресурса с одной работы на другую, то задача нахождения ресурсных связей многовариантна ( обусловлена переменной структурой графа ). Каждый вариант распределения ресурсов определяет топологию сетевой модели, которая характеризуется своими параметрами. Оптимальный вариант определяет оптимальную топологию сетевой модели согласно выбранному критерию. Следовательно при традиционном подходе к решению задачи распределения ресурсов на сетях трудаемкая работа, требующая участия коллек-тива и затрачиваемая на составление сетевых графиков, а также их расчета на ЭВМ, выполняется впустую. Кроме того, поскольку конечной целью при этом является получение расписания выполнения работ, то сетевая модель вообще выпадает из управления [7, 8, 9, ]. Неудачные попытки ввести в сетевое планирование нескладируемой ресурс привели к затуханию интереса к данному направлению. В настоящее время в научной литературе внимание в основном уделяется задачам загрузки оборудования и построение расписаний [10, 11, 12, 13, 14, 15].
2. Постановка.
Задачу распределения ресурсов на сетях, базой которой является принципиально новая теория, сформулируем на примере проектной организации. Тематический план проектной организации содержит как новые проекты, так и переходящие из плана предыдущего года. Каждый проект представлен в виде элементарных составляющих работ с указанием множества условий ( под множеством условий понимаются другие работы того же самого проекта, результаты каждой из которых, согласно технологии проектирования, необходимы для того, чтобы начать данную).
При этом каждый проект может содержать такие работы, от результатов которых зависит дальнейшее развертывание проектирования проекта. Иначе говоря, нельзя полностью определить технологию проектирования проекта, поскольку результат некоторых работ влияет на последующий ход его реализации. Такие работы мы будем называть решающим результатом. В одном проекте может быть несколько решающих результатов.
Введение решающих работ позволяет принимать в расчет альтернативы, которые возникают на некоторых этапах реализации проекта [16]. Каждой альтернативе приписана априорная вероятность. Каждая работа помимо взаимоcвязи с другими работами согласно технологии проектирования характеризуется видом ресурса, которым она может выполняться, а также трудоемкостью. Каждый ресурс специализированного подразделения характеризуется его наличием и пределами потребления данного ресурса на различных работах. Требуется определить стохастическую сетевую модель, отображающую многопроектную разработку с учетом ресурсов.
Введем условные обозначения число проектов; число различных видов ресурсов , обеспечивающих выполнение многопроектной разработки; продолжительность критического пути m-го проекта в сетевом графике без учета ресурсов, продолжительность самой длинной цепочки работ, выполняемых i-ым видом ресурса, множество работ многопроектной разработки (данное множество включает работы всех проектов, которые задаются общим списком);
код j-й работы, весовой коэффициент j-й работы, вид ресурса, которым может выполняться j-я работа, максимально возможное число ресурсов для j-й работы,трудоемкость j-й работы, планируемое число ресурсов на j-ю работу, множество технологических условий для j-й работы, множество ресурсных условий (данное множество включает работы, c каждой из которых ресурсы переходят на выполнение j-й работы, );код q-го условия для j-й работы, срок начала j-й работы,
срок окончания q-го условия для j-й работы,
множество работ многопроектной разработки, каждая из которых выполняется i-м видом ресурса в к-ю единицу времени,
число единиц ресурса i-го вида, число работ множества
Прежде чем дать математическую формулировку задачи, введем определения
1. Под ресурсным графом мы понимаем сетевую модель, отображающую многопроектную разработку с учетом ресурсов.
2. Под установлением между работами связей по ресурсам мы понимаем указание для j-й работы множества ресурсных условий Zj ,
3. Путь, имеющий продолжительность Tm , мы называем критическим путем сетевого графика для m-го проекта без учета ресурсов.
4. Путь, имеющий продолжительность мы называем критическим путем сетевой модели многопроектной разработки без учета ресурсов. Сетевая модель в данном случае состоит из совокупности сетевых графиков.
5. Путь ресурсного графа, имеющий продолжительность , мы называем. критическим.
. . V(t0)известно( состояние системы в момент времени t0).
(1) для любого
(2)
(3)
(4) целое,
(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, . . . , прерывается и все ресурсы переходят на выполнение других работ. Выполнение работ указанного множества будет продолжено позже.
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. Исходные данные.

j

Xj
cj

Dj

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. Экстремальный ресурсный граф.

nj

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.
. Теорема1 Для того чтобы продолжительность выполнения всех работ многопроектной разработки с учетом ресурсов равнялась бы продолжительности критического пути, необходимо и достаточно, чтобы между работами ресурсного графа были установлены связи по ресурсам при соблюдении технологических условий предшествования работ в качестве ограничений.
Доказательство теоремы дается в предпололожении, что чило ресурсов для каждой работы фиксировано.
. Достаточность.Пусть продолжительность критического пути ресурсного графа равна продолжительности выполнения всех работ с.учетом ресурсов. Предположим, что при этом между работами ресурсного графа не установлены связи по ресурсам. В таком случае не для всех цепочек работ, образуемых ресурсными связями, гарантировано Найдется хотя бы одна такая цепочка, для которой что противоречит предположению.
. Необходимость. Пусть между работами ресурсного графа установлены связи по ресурсам. Продолжительность самого длинного пути L, который назван критическим, определит продолжительность выполнения всех работ многопроектной разработки.
Получение экстремального графа алгоритмом, включающим пункты , следует из теоремы 2, где под математическим построением сетевой модели будем понимать нахождение графа согласно критерию (1) в области, определяемой ограничениями (2)(5).
Теорема 2. Если все функции , n2, . . . , ), вогнуты и аддитивны, то математическое построение сетевой модели многопроектной разработки обеспечивает получение экстремального графа.
Cостояние системы меняется в моменты времени 2, . . . , что соответствует времени обеспечения работ ресурсами. Причем при распределении участвуют все ресурсы, выделенные на выполнение многопроектной разработки, и все работы, свободные в данный момент времени от технологических условий. Для всех значений к, состояние системыпостоянно. Распределение ресурсов среди работ множества 2, . . . , осуществляется по одной и той же схеме, включающей пункты алгоритма 1для всех и для всех 2, . . . , В свете сказанного необходимо доказать, что переменные ni , Zj обеспечивают максимальное значение функции (1) при фиксированных значениях i, . Зафиксируем значения i, , приняв i=1, . Не теряя общности рассуждений, доказательство теоремы проведем для случая, когда число работ множества A2, выполняемых 1-м видом ресурсов, равно 2. Для общего случая теорема доказана в работе [19] .
Пронумеруем работы множества А2 . функция (1) примет вид (52)
(52)
Пусть в соответствии с условием теоремы
(53) .
(54)
Рассмотрим матрицу (55).
(55)
Физически означает приращение функции (52) за счет того, что на выполнение работы множества А1 дополнительно назначается одна единица ресурса при условии, что на эту же самую работу уже было назначено единиц ресурсов.
В силу вогнутости функций справедливы соотношения (56).
(56)
С вводом элементов матрицы (55) функция (52) примет вид (57).
(57)
Это следует из (53), если представить
(58)
Преобразуем матрицу в вектор-строку p=1, 2, . . ., b1 так, чтобы элементы вектора образовали вариационный ряд по невозрастанию.
(59)
Элементы ряда (59) обладают тем важным свойством, вытекающим из (56), что если , то найдется такое , для которого . Это свойство имеет место только для вогнутых функций и позволяет предложить конструктивный метод решения задачи. Составим сумму первых J элементов вектора
(60) .
В силу отмеченного выше свойства (59) очевидно, что
(61)
Значение определяется числом наибольших элементов столбца с номером матрицы , попавших в последовательность .
Таким образом, при распределении ресурсов последовательно двигаясь по наибольшим приращениям функции (52) мы на каждом шаге получаем оптимальный план.
Ресурсы на работу , 1, 2 переходят с работ множества согласно критерию (52), что обеспечивает получение оптимальной структуры графа. При J=b1 получаем оптимальное распределение всех ресурсов. В свете сказанного граф (1) является экстремальным.
Список литературы
1 . Х. Ахьюджа. Cетевые методы управления в проектировании и производстве. М. Наука, 1979.
2. Cборник III-го Bcесоюзного симпозиума по проблемам планирования и управления научными исследованиями и разработками. М. ЦЭМИ. 1975.
3. Применение пакетов прикладных программ по экономико — математическим методам в АСУ. М. Статистика, 1980.
4 Глушков В. М. , Михалевич В. C. и др. Управляющий этап // Управляющие системы и машины. Киев Ин-т кибернетики АН УССР, 1989. N3. С. 5-7.
5. Основные положения по разработке и применению систем сетевого планирования и управления. М. , Экономика. 1974.
6. Костина Л. П. Причины парадоксов при распределении ресурсов на сетях в книге Х. Ахьюджа ? Сетевые методы управления в проектировании и производстве¦ (под ред. В.В Калашникова. М. , 638 c). Деп. организацией п / а А — 1420 МРС
?ТТЭ¦. Сер.0. Вып. 18, Д05134 от 5 августа 1982 г.
7. Fersko-Weis H. Projekt management software // PC Magazine. 1988. November 15. p. 178-226.
8. Fersko-Weis H. High-end proekt managers make the plans // PC magazine 1989 May 16 p. 155-195.
9. С. В. Кохова. Некоторые динамические задачи распределения ресурсов на сетевых графиках с переменными объемами работ // Вестник Московского университета.
сер.15. Вычислительная математика и кибернетика. 1991. N1. C. 48-57.
10. Kouveles P., Lee H.L. Block angular structures and the loading problem in flexible manufakcturing systems // Oper. Res. 1991.V.39. N4. P. 666- 676.
11. Rogers V.R. White K. P. Algebraic, Mathematical Programming, and Notwork Models of the Deterministig Job-shop Scheduling Problem //IEEE Trans. on Systems, Man, and Cybernetics.1991.V. 21. N3. P.693-697.
12. В. И. Левин. Оптимизация расписаний в системах с неопределенными временами обработки // Автоматика и телемеханика. 1995. N2. C. 99-110.
13. В.Н.Калачев, Б. В. Немчинов, В.Е. Кривоножко. Зфдачи планирования в гибких производственных системах // Автоматика и телемеханика. 1995. N6. C. 155-164.
14. П. И. Шарыгин. Оценки приближенного решения одной задачи календарного планирования // Дискретный анализ и исследование операций. Новосибирск Ин-т математики СО РАН, 1995, т. 2. N1, 57-67.
15. А. В. Кононов. О расписаниях работ на одной машине с длительностями нелинейно зависящими от времени // Дискретный анализ и исследование операций. Новосибирск Ин-т математики СО РАН, 1995, т. 2 N1, 21-35.
16. А. Кофман, Г. Дебазей. Сетевые методы планирования и их применение. М. Прогресс, 1968
17. Костина Л. П. Математическое построение сетевой модели многотемной разработки. //Теоретический семинар ?Проблемы совершенствования управления научно-техническим прогрессом¦. Московский университет. 1975. С. 253-256.
18. Дымарский Я. С., Прудовский Б. Д. Сталбо А. К. //Вопросы оптимизации в исследовании операций. Труды в/ч 30895. Вып. 99. C. 153-162.
19. Костина Л. П. Опыт создания АСУ проектной организацией на базе методов распределения ресурсов на сетях, обусловленных переменной структурой графа. Деп. организацией п/я А-1420 МРС ?ТТЭ¦, серия 0, вып. 18, Д05135 от 5 августа 1982 г.
20. Костина Л. П. Постановка проблемы оптимального распределения ресурсов на стохастических сетях со сложной пространственно-временной структурой. //Вестник Санкт -Петербургского университета. Сер.1. 1992. Вып. 2 (8). С. 15-19.
21. Костина Л. П. Метод решения задачи оптимального распределения ресурсов на стохастических сетях со сложной пространнственно-временной структурой. //Вестник Санкт-Петербургского университета. Сер. 1. 1992. Вып. 3 (15).