Учебное пособие 800519
.pdf
продолжительность. Дуги соответствуют мягким зависимостям между работами. Для каждой дуги заданы два числа: аij и bij. Первое число аij определяет увеличение продолжительности работы j, если зависимость (i; j) нарушается, то есть если работа j начата до окончания работы i. Второе число bij определяет увеличение затрат на выполнение работы j, если зависимость (i, j) нарушается.
1 |
(8;2) |
3 |
(3;1) |
6 |
|
||||
3 |
|
7 |
(5;3) |
8 |
|
|
|
|
|
|
(1;1) |
|
|
(2;3) |
|
|
|
4 |
|
|
|
|
|
|
|
(4;5) |
|
4 |
(1;4) |
|
|
|
|
|
2 |
(7;2) |
5 |
(3;4) |
7 |
5 |
|
2 |
|
6 |
Рис. 3.1.1
Для описанной модели возможны различные постановки задач.
Задача 3.1.1. Пусть заданы только числа аij (можно считать, что все bij=0). Требуется определить календарный план с минимальной продолжительностью проекта.
Задача 3.1.2. Пусть заданы только числа bij (можно считать, что все аij=0). Требуется определить календарный план с минимальными дополнительными затратами.
Задача 3.1.3. Пусть заданы оба числа аij и bij. Определить календарный план, при котором проект выполняется за время Т, а увеличение затрат минимально.
Заметим, что сетевой график при мягких зависимостях может иметь контуры в отличие от сетевого графика при жестких зависимостях.
3.2. Алгоритм решения задачи построения календарного плана с минимальной продолжительностью проекта
|
|
Присваиваем всем работам сетевого графика |
начальные индексы i= i, |
|||||
i 1, n . |
Рассматриваем |
каждую |
работу |
i. |
Обозначим |
через |
||
Qi множество работ, предшествующих работе i, то есть в сетевом графике существует дуга (j, i) для j Qi . Обозначим через mi число дуг, заходящих в
вершину i (число элементов множества Qi). Рассмотрим все подмножества из mi элементов (их число равно 2mi ). Для каждого подмножества, содержащего вершины Ri Qi, вычисляем
ti Ri i |
max j a ji . |
(3.2.1) |
|
|
j Ri |
j Ri |
|
Определяем новый индекс вершины
i
i: |
|
min ti Ri . |
(3.2.2) |
Ri |
|
81 |
|
Алгоритм заканчивается, когда все индексы установятся. Конечность
алгоритма следует из того, что последовательность индексов для каждого i является возрастающей. С другой стороны, индексы i ограничены величиной
T i a ji .
j Qi
Пример 3.2.1. Рассмотрим сетевой график (рис. 3.2.1).
|
[4] |
|
[6] |
|
|
|
1 |
2 |
2 |
|
|
|
6 |
|
|
|
|
|
2 |
|
3 |
4 |
|
[11] |
3 |
|
8 |
3 |
[5] |
|
|
|
|
|
|
|
6 |
|
|
1 |
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
5 |
|
4 |
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
3 |
|
4 |
|
|
|
|
|
|
|
|
|
5 |
|
4 |
[10] |
|
|
2 |
|
7 |
|
|
|
[12] |
|
|
|
|
Рис. 3.2.1
1шаг 1=2, 2=3, 3=1, 4=4, 5=2, 6=3.
2шаг Рассматриваем вершину 1. В нее заходит одна дуга (2,1). Если
соответствующую зависимость не учитывать, то продолжительность работы увеличиться на 2 единицы и будет равна t1=4. Если же зависимость (2,1)
учитывать (считать жесткой), то момент окончания работы будет равен t1=2+3=5. Поэтому выгоднее зависимость (2,1) не учитывать. Имеем
1 min 4;5 4
Рассматриваем вершину 2. В нее заходит также только одна дуга (6;2). Если соответствующую зависимость не учитывать, то момент окончания
работы 2 будет равен t2=3+3=6. Если |
учитывать, то t1= 6+ 2=6. Обе величины |
|
равны, поэтому 2 |
6. |
|
Рассматриваем работу 3. В нее также заходит только одна дуга (2,3). Если |
||
соответствующую |
зависимость не |
учитывать, то 3 3 a23 5 , а если |
учитывать, то 3 2 3 6 1 7 . |
|
|
Выбираем минимальное время 3 min 5;7 5 .
Рассматриваем работы 4. В данном случае в величину 4 заходят две дуги (2;4) и (3;4). Поэтому имеются 4 варианта.
Обе зависимости (2,4) и (3,4) не учитываем. Продолжительность работы
увеличивается на a24 a34 |
8 6 14 |
и момент ее окончания 4 4 14 18 . |
|
||||
Учитываем только одну зависимость (2,4). Продолжительность работы 4 |
|||||||
увеличивается |
на |
a34 16 , |
а |
момент |
ее |
окончания |
равен |
4 2 4 a34 4 6 6 16 . |
|
|
|
|
|
||
|
|
|
|
82 |
|
|
|
Учитываем только зависимость (3,4). Продолжительность работы
увеличивается |
на |
a24 8 , |
а |
момент |
ее |
завершения |
равен |
4 3 4 a24 5 8 4 17 . |
|
|
|
|
|
||
Учитываем обе зависимости (2,4) (3,4). Продолжительность работы не увеличивается, а момент ее завершения равен
4 max( 2 ; 3 ) 4 6 4 10 .
Выбираем вариант с минимальной величиной , то есть
4 min(18,16,17,10) 10 .
Рассматриваем работу 5. В нее также заходят две дуги (2,5) и (4,5). Потому рассматриваем четыре варианта. Обе зависимости не учитываем. Имеем
5 5 a25 a45 2 4 7 13 . Учитываем зависимость (2,5). Имеем
5 5 a45 2 2 7 6 15 .
Учитываем зависимость (4,5). Имеем 5 5 a25 4 2 4 10 16 . Учитываем
обе зависимости (2,5) (4,5). Имеем 5 max( 2 ; 4 ) 5 2 10 12 .
Выбираем четвертый вариант 5 12 .
Рассматриваем работу 6. В вершину 6 заходят три дуги (1,6) (3,6) и (5,6) в данном случае имеем 23=8 вариантов. Все три зависимости не учитываем.
Имеем 6 6 a16 a36 a56 3 6 5 3 17 .
Учитываем зависимость (1,6). Имеем
6 6 a36 a56 1 3 5 3 4 15 .
Учитываем зависимость (3,6). Имеем
6 6 a16 a56 3 3 6 3 5 17 .
Учитываем зависимость (5,6). Имеем
6 6 a16 a36 5 26 .
Учитываем зависимости (1,6) и (3,6). Имеем
6 6 a56 max( 1 ; 3 ) 3 3 5 11 .
Учитываем зависимости (1,6) и (5,6). Имеем
6 6 a36 max( 1 ; 5 ) 3 5 12 20 .
Учитываем зависимости (3,6) и (5,6). Имеем
6 6 a16 max( 3 ; 5 ) 21 .
Учитываем все три зависимости (1,6), (3,6) и (5,6). Имеем
6 max( 1; 3 ; 5 ) 6 15 .
Выбираем пятый вариант 6 11 .
Замечание 3.2.1. Число вариантов можно сохранить, если дуги множества Qi рассматривать в очередности убывания i. В этом случае, если мы учитываем дугу (j;i), то можно сразу учесть все дуги с меньшими или равными k j . В нашем случае достаточно рассмотреть 4 вариант. В общем случае, если в вершину i заходит mi дуг, достаточно рассмотреть (mi+1) вариант.
Проверим корректировку индексов вершин в том же порядке.
83
Рассматриваем вершину 1. Имеем одну заходящую дугу и значит два
варианта 2 min( 1 a21;1 2 ) 4 .
Величина индекса не изменилась. Рассматриваем вершину 2. Имеем такие два варианта
2 min( 2 a62 ; 2 6 ) 6 .
Величина индекса не изменилась. Рассматриваем вершину 3. Имеем два варианта
3 3 min( a23 ; 2 ) 5 .
Величина индекса не изменилась.
Рассматриваем вершину 4. Имеем три варианта, так как в вершину 4 заходят 2 дуги. Имеем
4 4 min( 6;13;18) 10 .
Величина индекса не изменилась. Рассматриваем вершину 5. Имеем три варианта
5 5 min(10;13;11) 12 .
Величина индекса не изменилась.
Рассматриваем вершину 6. Имеем четыре варианта, так как в вершину 6 заходят 3 дуги. Имеем
6 6 min(12;8;12) 11 .
Величина индекса не изменилась.
Поскольку индексы установлены, то алгоритм закончен.
Теорема 3.2.1. Установившиеся значения индексов i определяют минимальные ранние сроки завершения работ.
Доказательство. Заметим, что величины индексов, получаемые на каждом шаге, являются нижними оценками моментов окончания соответствующих работ. После того как индексы установились, можно выделить те зависимости, то есть становятся жесткими зависимости. Можно построить сетевой график выполнения работ с учетом только жестких зависимостей. Очевидно, что этот сетевой график не имеет контуров. Рассчитывая его известными алгоритмами (с учетом того, что зависимости, которые не выполняются, приводят к увеличению продолжительностей работ), мы получим те же самые установившиеся индексы. Это доказывает теорему.
3.3. Построение календарного плана с минимальными дополнительными затратами с использованием метода дихотомического программирования
Рассмотрим сетевой график без контуров, в котором некоторое множество Q зависимостей являются мягкими (рис. 3.3.1), мягкие зависимости показаны пунктиром.
При построении дихотомического представления естественно учитывать только моменты окончания тех работ j, которые связаны мягкими зависимостями хотя бы с одной работой, т.е. существует работа i, такая что (i,j) Q. В нашем примере таких работ три. Это работы 4,6 и 7.
84
1 |
3 |
(5) |
6 |
5 |
4 |
|
5 |
(6) |
|
|
|
|
|
4 |
|
(12) |
|
3 |
|
2 |
5 |
(2) |
7 |
6 |
2 |
|
6 |
Рис. 3.3.1
Дихотомическое представление сетевого графика (рис. 3.3.1) приведено на рис. 3.3.2.
Т
T6 T7
T4
(1.4) |
(2.4) |
(3.6) |
(5.7) |
Рис. 3.3.2
Построим соответствующие матрицы для t4, t6 t7. Матрица для момента t4 приведена на рис. 3.3.3.
Опишем более детально метод построения этой матрицы. Возможно 4 варианта для мягких зависимостей.
0 |
9 |
3 |
6 |
6 |
18 |
5 |
9 |
8 |
0 |
0 |
12 |
t1 |
6 |
0 |
t2 |
0 |
12 |
|
Рис 3.3.3 |
|
1 вариант. Учитываем обе зависимости. В этом случае момент завершения работы 4 равен
t4 4 max( t1, t2 ) 9 ,
а дополнительные затраты равны 0.
2 вариант. Учитываем только зависимость (1,4). В этом случае
t4 4 t1 8 , 85
а дополнительные затраты равны 12.
3 вариант. Учитываем только зависимость (2,4). В этом случае
t4 4 t2 9 ,
а дополнительные затраты равны 6. Заметим, что этот вариант можно не рассматривать, поскольку при учете зависимости (2,4) автоматически учитывается зависимость (1,4).
4 вариант. Не учитываем ни одной зависимости. В этом случае
t4 4 3 ,
а дополнительные затраты составят 18.
Матрица для момента t6 приведена на рис. 2.4. Заметим, что момент t4 используется дважды. Во-первых, для определения t6, а во-вторых, для определения t7. Поэтому затраты в матрице для t4 необходимо разделить на две части – одна часть для матрицы t6, а другая – для матрицы t7. Поделим их поровну. В этом случае получаем следующую матрицу (t6) (рис. 3.3.4).
|
0 |
14 |
13 |
|
8 |
|
|
5 |
5 |
11 |
14 |
(t6)= |
9 |
14 |
14 |
|
14 |
0 |
|
0 |
6 |
9 |
|
|
|
||||
|
t3 |
9 |
8 |
|
3 |
|
|
t4 |
0 |
6 |
9 |
Рис. 3.3.4
Матрица для момента t7 приведена на рис. 3.3.5.
|
0 |
15 |
14 |
|
9 |
|
|
2 |
2 |
8 |
11 |
(t7)= |
8 |
15 |
14 |
|
14 |
|
0 |
0 |
6 |
9 |
|
|
|
||||
|
t5 |
9 |
8 |
|
3 |
|
|
t4 |
0 |
6 |
9 |
Рис. 3.3.5
Окончательно получим дихотомическое представление, приведенное на рис. 3.3.6.
Теперь можно решить задачу оптимизации дополнительных затрат для любого T.
1.Возьмем T 15. Из матрицы (t7) получаем t5=8, t4=9. Следовательно, зависимость (5,7) учитывается. Из матрицы (t4) получаем при t4=9, t1=5, t2=6, то есть учитываются обе зависимости (1,4) и (2,4).
Из матрицы (t6) получаем t3=9, t4=9, то есть зависимость (3,6) учитывается. Таким образом, учитываем все зависимости и дополнительные затраты S(15)=0.
2.Возьмем T 14. Анализируя матрицу (t7), мы видим, что t4=9 не удовлетворяет ограничению T 14 при любом t5. Поэтому решение t4=9 не рассматриваем. Из матрицы (t7) получаем t4=8, t5=8, то есть зависимость (5.7)
86
учитывается. Из матрицы (t6) получаем t3=9, t4=8 (поскольку решения с t4=9 мы исключили). Наконец, из матрицы (t4) получаем при t4=8, t1=5, t2=0, то есть зависимость (2,4) не учитываем, а зависимость (1,4) учитываем. Окончательно получаем решение, в котором не учитывается только зависимость (2,4) с дополнительными затратами S(14)=12.
3. Возьмем T 13. Анализируя матрицу (t7), видим, что t4=9 и 8 следует исключить. Имеем t4=3, t5=0, то есть зависимость (5.7) не учитывается. Из матрицы (t6) получаем t3=0, t4=3, то есть зависимость (3,6) не учитывается. Из матрицы (t4) получаем t1=t2=0, то есть обе зависимости (1,4) и (2,4) не учитываем. Получаем решение, в котором ни одна из зависимостей не учитывается. Продолжительность проекта составляет Т=9, а дополнительные затратами S=25.
В рассмотренном примере и в матрице (t6) и в матрице (t7) мы получили одинаковые значения t4 при любых Т. Поэтому полученные решения являются допустимыми, а значит оптимальными. В более сложных случаях значения ti, полученные в разных матрицах могут не совпадать. В этих случаях мы получаем оценку снизу дополнительных затрат. Можно попытаться улучшить эту оценку, применив деление затрат. Если это не удается, то применяем метод ветвей и границ.
|
|
|
t6 |
|
|
|
0 |
14 |
13 |
|
8 |
|
|
5 |
5 |
11 |
14 |
t3 |
9 |
14 |
14 |
|
14 |
|
|
0 |
0 |
6 |
9 |
|
t3 |
9 |
8 |
|
3 |
|
|
t4 |
0 |
6 |
9 |
|
|
|
t4 |
|
|
|
0 |
9 |
3 |
|
|
|
|
6 |
6 |
18 |
|
|
5 |
9 |
8 |
|
|
|
|
0 |
0 |
12 |
|
|
t1 |
6 |
0 |
|
|
|
|
t2 |
0 |
12 |
|
1,4 |
|
|
2,4 |
|
|
|
|
|
|
|
|
|
|
t7 |
|
|
|
0 |
15 |
14 |
|
9 |
|
2 |
|
2 |
8 |
11 |
|
8 |
15 |
14 |
|
14 |
|
0 |
|
0 |
6 |
9 |
|
t5 |
9 |
8 |
|
3 |
|
t4 |
|
0 |
6 |
9 |
3,6 |
5,7 |
|
Рис. 3.3.6
87
3.4. Построение календарного плана заданной продолжительности при минимальном увеличении затрат
Метод дихотомического программирования можно обобщить на задачу 3.1.3. Изменение состоит только в том, что при формировании матриц дихотомического представления необходимо учитывать увеличение продолжительности работ. Дадим иллюстрацию метода на примере сетевого графика (рис. 3.3.1) Примем следующее значение аij, для мягких зависимостей
(i,j) |
(1.4) |
(2.4) |
(3.6) |
(5.7) |
aij |
3 |
1 |
4 |
2 |
Построим соответствующие матрицы для t4, t6 и t7. Матрица для момента t4 приведена на рис. 3.4.1.
Поясним, как получаются значения моментов окончания работы 4 для разных вариантов учета мягких зависимостей (1,4) и (2,4). Если учтены обе зависимости, то t1=5, t2=6, 4=3, t4 3 max 5;6 9 .
Если зависимость (1,4) не учитывается, а зависимость (2,4) учитывается,
то t1=0, t2=6, 4= 4 +а14=6, t4 6 max 0;6 12 .
Заметим, что этот случай можно не рассматривать, поскольку при учете зависимость (2,4) естественно учесть и зависимость (1,4).
|
0 |
12 |
7 |
|
|
|
6 |
6 |
18 |
(t4)= |
5 |
9 |
9 |
|
|
0 |
0 |
12 |
|
|
|
|||
|
t1 |
6 |
0 |
|
|
|
t2 |
0 |
12 |
|
|
Рис. 3.4.1 |
|
|
Если зависимость (1,4) учитывается, а зависимость (2,4) не учитывается,
то t1=5, t2=0, 4= 3 +а24=4, t4 max t1; t2 4 9 .
Наконец, если обе зависимости не учитываются, то t1=t2=0, 4= 4 +а14+а24 =7. Матрица для момента t6 приведена на рис. 3.4.2. Значение t4 =12 мы
исключили, поскольку оно доминирует значением t4=9.
|
0 |
14 |
12 |
|
|
|
5 |
6 |
23 |
(t6)= |
9 |
14 |
14 |
|
|
0 |
0 |
7 |
|
|
|
|||
|
t3 |
9 |
7 |
|
|
|
t4 |
0 |
9 |
|
|
Рис. 3.4.2 |
|
|
88
Матрица для момента t7 приведена на рис. 3.4.3.
|
0 |
17 |
15 |
|
|
2 |
2 |
11 |
|
(t7)= |
8 |
15 |
14 |
|
0 |
0 |
9 |
||
|
||||
|
t5 |
9 |
7 |
|
|
t4 |
0 |
9 |
|
|
Рис.3.4.3 |
|
||
Решим задачу для случая Т<15.
Из матрицы (t7) имеем t4=7, t5=8, учитывается зависимость (5,7). Из матрицы (t6) имеем t3=9, t4=7, учитывается зависимость (3,6).
Действительно, значение t4=9 исключаем, поскольку в матрице (t7) в столбце со значением t4=9 нет значений t7 меньше 15.
Из матрицы (t4) имеем t1=0, t2=0, то есть не учитываются зависимости
(1,4) и (2,4).
Окончательно получаем решение, в котором не учитывается только две зависимости (1,4) и (2,4). Продолжительность проекта составляет Т=14, а дополнительные затраты S=18. При этом продолжительности работ увеличились в сумме на 4 единицы.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1.Какие зависимости между работами проекта называются зависимостями рекомендательного типа?
2.К чему ведет нарушение зависимостей рекомендательного типа?
3.Сформулируйте алгоритм решения задачи построения календарного плана с минимальной продолжительностью проекта.
4.В чем заключается алгоритм построения календарного плана с минимальными дополнительными затратами.
5.Сформулируйте правила построения матриц для моментов t.
6.В чем заключается анализ матриц при решении задач оптимизации
дополнительных затрат для любого Т.
7. Сформулируйте алгоритм построения календарного плана заданной продолжительности при минимальном увеличении затрат.
8.Как определить из матриц продолжительность проекта и дополнительные затраты?
89
ГЛАВА 4. МОДЕЛИ И МЕТОДЫ ФОРМИРОВАНИЯ ПРОИЗВОДСТВЕННОЙ ПРОГРАММЫ ПРОЕКТНОЙ ОРГАНИЗАЦИИ
4.1. Оптимальное размещение единиц проектирования во времени
Рассмотрим случай независимых проектных работ. В этом случае задача решается отдельно для каждого вида проектных работ. Пусть ограничение Cis
отсутствует, то есть при наличии ресурсов каждая работа может быть выполнена в одном интервале. В этом случае существует простое правило оптимального распределения ресурсов: в первую очередь начинаются работы с минимальными поздними сроками окончания (правило А).
Доказательство. Пусть в каком-либо интервале s назначена работа i, хотя имеется работа j с меньшей величиной bj bi . Заметим, что соответствующий
объем работы j выполняется в некотором более позднем интервале q. Однако в этом же интервале может выполняться и работа i. Поэтому мы можем поменять объемы работ (то есть объем работы j, выполняемый в q-м интервале, переносим в интервал s, и наоборот соответствующий объем работ i переносим в интервал q). Поступая таким образом всякий раз, когда нарушается правило, мы придем к решению, в котором все работы выполняются в соответствии с правилом А принятия решения.
1 шаг. Определяем начальную величину :
|
|
|
W |
|
|
0 |
max 1; |
|
, |
|
|
|||
|
|
|
Q |
|
где W Wi |
; Q Qs . |
|
|
|
i |
s |
|
|
|
Применяем правило А при количестве ресурсов 0Qs ,
удается выполнить все работы, то получено оптимальное противном случае возможны два варианта:
1вариант. Найдется ближайший интервал S, такой, что
xis 0Q ,
i Ps
(4.1.1)
s 1,T. Если решение. В
то есть ресурсы не полностью используются.
Исключаем все работы, которые выполнены в интервалах 1,S . Для оставшихся работ определяем
|
|
|
|
|
W(s) |
|
|
|
|
1 |
max |
1; |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Q(s) |
, |
|
|
|
|
|
|
|
|
|
где W(s) Wi |
T |
|
|
|
|
|
|
, Q(s) Qp |
, Р(s) – множество невыполненных работ. |
||||||
i P s |
p s 1 |
|
|
|
|
|
|
Применяем правило А для распределения объемов невыполненных работ, начиная с интервала (s+1). Если удалось выполнить все работы, то получено оптимальное решение
90