Материал: Рациональное размещение работ по времени. методические указания к проведению практических занятий и самостоятельной работе по дисциплине «Организационно-технологическое проектирование». Баркалов С.А., Курочка П.Н
дача заключается в определении {xis }, i =1,n , s =1,T, так, чтобы все работы были выполнены, то есть
xis ≤Cis , i Ps , s =1,T
∑xis = Wi , i =1,n
s Ri
где Wi - объем i-ой работы, а перегрузка исполнителей, то есть превышение
объема работ над тем объемом, который могут выполнить исполнители, работал по нормативам, была минимальной. Если обозначить через
α - относительный уровень перегрузки ресурсов, то формально критерий можно записать в виде
α →min
при ограничениях
∑xis = αQsj , j =1,m i Ri
Фактически мы перешли от задачи календарного планирования к задаче объемно-календарного планирования.
Если перегрузка ресурсов недопустимо велика, то естественно снизить её за счёт передачи части работ на субподряд. Обозначим через Р множество работ , передаваемых на субподряд, Ci - стоимость i-й работы при передаче её на
субподряд. Задача заключается в определении множества Р, такого, чтобы стоимость субподрядных работ
C(P)= ∑Ci |
(1) |
|||||||
|
i P |
|
||||||
была минимальной при ограничениях |
|
|
|
|
|
|
|
|
xis ≤ Cis , i Ps , s = |
|
|
|
, |
(2) |
|||
1,T |
||||||||
∑xis =Wi , |
i = |
|
, |
(3) |
||||
1,n |
||||||||
s Ri |
|
|
|
|
|
|
|
|
∑xis ≤αQsj , |
j = |
|
, |
(4) |
||||
1,m |
||||||||
i Ri |
|
|
|
|
|
|
|
|
для всех i P (при этом α =1). Другими слова, требуется минимизировать за-
6
траты на субподрядные работы при условии, что остальные работы могут быть выполнены своими силами без перегрузки ресурсов (либо при допустимой перегрузке ресурсов α ≤ αдоп ).
Вусловиях ограниченных ресурсов для выполнения производственного плана в заданные сроки приходится привлекать другие организации.
Вусловиях ограниченных ресурсов для выполнения договорных обязательств в заданные сроки приходится привлекать другие организации.
Рассмотрим первоначально случай, независимых работ, то есть могут выполняться одновременно.
Начнем рассмотрение с простейшего случая, когда зависимость скорости
работы wi от количества ресурсов ui имеет вид
wi = ui , i = |
1, n |
. |
(5) |
В этом случае каждый вид проектных работ можно рассматривать отдельно. Пусть количество ресурсов рассматриваемого вида равно N. В этом случае продолжительность выполнения всех проектных работ определяется выражением
T = W |
, |
(6) |
N |
|
|
n
где W = ∑Wi .
i=1
Если Т>Т0 (Т0 – заданный срок выполнения проектных работ), то часть работ необходимо передать другим организациям, которые смогут выполнить эти работы за время не больше Т0. Обозначим ci стоимость выполнения i-й ра-
боты на субподряде. Для формальной постановки задачи обозначим xi =1, если работа i передается на субподряд, xi = 0 - в противном случае. Задача заключается в определении {xi }таких, что сумма
C(x) = ∑ci xi |
(7) |
i |
|
минимальна при ограничении
7
∑wi xi ≥ b , |
(8) |
i |
|
где b =W −T0 N .
Это классическая «задача о ранце», для которой существуют эффективные методы решения. Рассмотрим для её решения метод дихотомического программирования.
Пример
Рассмотрим численный пример. Пусть имеется шесть проектных работ, данные о которых приведены в табл. 1.
Таблица 1
i |
1 |
2 |
3 |
4 |
5 |
6 |
Wi |
3 |
5 |
7 |
9 |
10 |
12 |
сi |
2 |
3 |
4 |
7 |
9 |
10 |
Общий объём работ W = 46. Пусть N=3, T0=9. Тогда b=46–27=19.. Рассмотрим следующую структуру дихотомического представления ограничения
(8) (рис. 1).
|
|
y5 |
|
|
|
|
|
y4 |
|
|
|
|
y1 |
y2 |
|
|
y3 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
Рис. 1
Сначала объединяются работа 1 и работа 2 (обозначено у1), работа 3 с работой 4 (обозначено у2) и работа 5 с работой 6 (обозначено у3). Затем результат объединения у1 и у2 (то есть у4) объединяется с у3.
Алгоритм состоит из двух этапов. На первом этапе строятся матрицы дихотомического представления. На втором– определяется оптимальное решение.
1 этап. Построим последовательно матрицы дихотомического представления.
Шаг 1. Строим матрицу у1 (рис. 2).
8
|
|
5 |
8 |
|
(у1)= |
|
3 |
5 |
|
х2 |
х1 |
3 |
||
|
||||
|
2 |
Рис. 2
Верхнее число в каждой клетке равно объёму работ, отдаваемых на субподряд в соответствующем варианте, а нижнее – стоимости. Так, например, если работа 1 отдается на субподряд, а работа 2 не отдается, то объём субподрядных работ составит 3, а стоимость – 2.
Шаг 2. Строим матрицу у2 (рис. 3).
|
|
9 |
16 |
||
(у2)= |
|
7 |
11 |
||
х4 |
х3 |
7 |
|||
|
|||||
|
4 |
||||
|
Рис. 3 |
|
|
||
Шаг 3. Строим матрицу у3 (рис. 4). |
|
|
|||
|
|
|
|
||
|
12 |
|
22 |
||
(у3)= |
10 |
|
19 |
||
|
|
10 |
|||
|
х6 |
х5 |
|
||
|
|
9 |
|||
Рис. 4
Шаг 4. Строим матрицу (у4) (рис. 5), пустые клетки соответствуют вариантам, которые не могут быть оптимальными.
|
16 |
19 |
|
|
|
|
11 |
13 |
|
|
|
|
9 |
12 |
14 |
17 |
|
(у4)= |
7 |
9 |
10 |
12 |
|
7 |
10 |
12 |
15 |
||
|
|||||
|
4 |
6 |
7 |
9 |
|
|
у2 у1 |
3 |
5 |
8 |
|
|
2 |
3 |
5 |
Рис. 5
Шаг 5. Строим матрицу (у5) (рис. 6). Заметим, что число столбцов матрицы (у5) равно 11, так как b = 19 и поэтому столбцы с величинами объёмов 21 и 24 можно не рассматривать.
9
22 |
|
|
|
|
|
|
|
|
|
|
|
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
15 |
17 |
19 |
|
|
|
|
|
|
|
|
10 |
12 |
13 |
14 |
|
|
|
|
|
|
|
|
(у5)= |
|
|
|
|
|
|
|
|
|
|
|
10 |
13 |
15 |
17 |
18 |
20 |
|
|
|
|
|
|
9 |
11 |
12 |
13 |
14 |
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
у3 |
3 |
5 |
7 |
8 |
10 |
12 |
15 |
16 |
17 |
19 |
|
у4 |
2 |
3 |
4 |
5 |
6 |
7 |
9 |
11 |
12 |
13 |
Рис. 6
Кроме того, вариант W=9, C=7 доминируется вариантом W=10, C=6, так как большему объёму субподрядных работ соответствуют меньшие затраты. Аналогично вариант W=14, C=10 доминируется вариантом W=15, C=9, а вариант W=12, C=9 доминируется вариантом W=12, C=7. Незаполненные клетки матрицы не рассматриваются, поскольку соответствующие варианты не могут быть оптимальными.
2 этап Шаг 1. В матрице (у5) рис. 6 находим клетку с минимальной стоимостью
субподрядных работ среди всех клеток с объёмом субподрядных работ не меньше 19. Это клетка y3 = 0, y4 = 19 с величиной стоимости С=13.
Шаг 2. В матрице (у4) рис. 5 находим клетку с объёмом субподрядных работ W=19 и стоимостью С=13. Ей соответствует y1 = 3 (стоимость 2) и
y2 = 16 (стоимость 11).
Шаг 3. В матрице (у3) рис. 4 находим клетку с объёмом y3 = 0 (стоимость также равна 0). Ей соответствует, очевидно, x5 = x6 = 0, то есть работы 5 и 6
выполняются собственными силами.
Шаг 4. В матрице (у2) рис. 3 находим клетку со значением y2 = 16 (стоимость также равна 11). Ей соответствует вариант, в котором x3 = x4 = 1, то есть
работы 3 и 4 отдаются на субподряд.
Шаг 5. В матрице (у1) рис.2 находим клетку со значением y1 = 3 (стоимость равна 2). Ей соответствует вариант x1 = 1, x2 = 0, то есть работа 1 отдаётся
на субподряд, а работа 2 нет.
Окончательно получаем оптимальный вариант, в котором на субподряд отдаются работы 1, 3 и 4 суммарного объёма 19 и суммарной стоимостью 13.
10