Глава 2. Примеры решения основных задач календарного планирования
2.1 Задача Джонсона о двух станках[5].
Рассмотрим задачу последовательной обработки на двух машинах N различных деталей, если известно время Ai и Bi обработки i-й детали на соответствующих машинах. Очевидно, что первая машина будет загружена полностью, но вторая может периодически оказываться в состоянии простоя. Попытаемся найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей. Если обозначить через Xi - время простоя в ожидании i-й детали, то: A1 X1 + X2 = max(A1 + A2 - B1, A1) X1 + X2 + X3 = max(A1 + A2 +A3 - B1 - B2, A1 + A2 - B1, A1) ∑Xi = max(∑Ai - ∑Bi) Если обозначить через F(t, Ak, Bk/k=1..N) - суммарное время обработки N деталей при условии, что вторая машина включается с задержкой t и используется оптимальный порядок обработки, то c учетом принципа оптимальности (независимо от выбора начальной детали порядок выбора последующих должен быть оптимальным) имеем: F(t, Ak, Bk/k = 1..N) = min(Ai + F(Bi + max(t-Ai,0),Ak,Bk=1..N,k≠i)) Если после i-й детали при оптимальном порядке обрабатывается j-я, то: F(t, Ak, Bk/k=1..N) = Ai + Aj + F(tij, Ak, Bk/k=1..N; k≠i,j) где tij = Bi + max[Bj + max(t-Aj,0) - Aj,0] = Bi + Bj - Ai - Aj + max[t, max(t,max(Aj - Ai - Bj,Aj))] Если max(Ai + Aj - Bi,Ai) < max(Aj + Ai - Bj, Aj), то сначала разумнее обрабатывать j-ю деталь. Можно показать, что указанное условие необходимости перестановки эквивалентно условию: min(Aj, Bi) < min(Ai, Bj) Соответственно ищем среди всех значений Ai и Bi наименьшее. Если найденное значение совпадает с некоторым Ai, то i-ю деталь ставим на обработку первой; если оно совпадает с некоторым Bi, то последней. Эту процедуру повторяем для всех остальных деталей. Пример. Пусть информация о времени обработки задана таблицей:
|
2 |
3 |
|
8 |
3 |
|
4 |
6 |
|
9 |
5 |
|
6 |
8 |
|
9 |
7 |
Минимальное из значений соответствует A1: 1-ая деталь обрабатывается первой.
|
2 |
3 |
|
- |
- |
|
- |
- |
|
- |
- |
|
- |
- |
|
- |
- |
Минимальное из значений равно 3 и соответствует B2: 2-ая деталь обрабатывается последней.
|
2 |
3 |
|
- |
- |
|
- |
- |
|
- |
- |
|
- |
- |
|
8 |
3 |
Минимальное из значений соответствует A3: 3-ая деталь обрабатывается первой.
|
2 |
3 |
|
4 |
6 |
|
- |
- |
|
- |
- |
|
- |
- |
|
8 |
3 |
Минимальное из значений равно 5 и соответствует B4: 4-ая деталь обрабатывается последней.
|
2 |
3 |
|
4 |
6 |
|
- |
- |
|
- |
- |
|
9 |
5 |
|
8 |
3 |
Минимальное из значений соответствует A5: 5-ая деталь обрабатывается первой.
|
2 |
3 |
|
4 |
6 |
|
6 |
8 |
|
- |
- |
|
9 |
5 |
|
8 |
3 |
Минимальное из значений равно 7 и соответствует B6: 6-ая деталь обрабатывается последней.
|
2 |
3 |
|
4 |
6 |
|
6 |
8 |
|
9 |
7 |
|
9 |
5 |
|
8 |
3 |
|
2 |
3 | |
|
4 |
6 | |
|
6 |
8 | |
|
9 |
7 | |
|
9 |
5 | |
|
8 |
3 | |
max(2 , 2 + 8 - 3 , 2 + 8 + 4 - 3 - 3 , 2 + 8 + 4 + 9 - 3 - 3 - 6 , 2 + 8 + 4 + 9 + 6 - 3 - 3 - 6 - 5 , 2 + 8 + 4 + 9 + 6 + 9 - 3 - 3 - 6 - 5 - 8 ) = max(2, 7, 8, 11, 12, 13) = 13
Время простоя при оптимальной перестановке равно:
max(2 , 2 + 4 - 3 , 2 + 4 + 6 - 3 - 6 , 2 + 4 + 6 + 9 - 3 - 6 - 8 , 2 + 4 + 6 + 9 + 9 - 3 - 6 - 8 - 7 , 2 + 4 + 6 + 9 + 9 + 8 - 3 - 6 - 8 - 7 - 5 ) = max(2, 3, 3, 4, 6, 9) = 9
2.2 Задача о назначениях[6].
Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й задачи на j-м машине. Задачи решаются одновременно с некоторого момента t0. Найти такое распределение задач по вычислительным машинам, чтобы общее время решения всех задач было бы минимальным при условии что на одной машине может решаться только одна задача. Решение. Исходная матрица имеет вид:
|
5 |
5 |
M |
2 |
2 |
|
7 |
4 |
2 |
3 |
1 |
|
9 |
3 |
5 |
M |
2 |
|
7 |
2 |
6 |
7 |
8 |
Для устранения дисбаланса добавляем дополнительные строки. 1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
|
3 |
3 |
M |
0 |
0 |
2 |
|
6 |
3 |
1 |
2 |
0 |
1 |
|
7 |
1 |
3 |
M |
0 |
2 |
|
5 |
0 |
4 |
5 |
6 |
2 |
|
0 |
0 |
0 |
0 |
0 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
|
3 |
3 |
M |
0 |
0 |
|
6 |
3 |
1 |
2 |
0 |
|
7 |
1 |
3 |
M |
0 |
|
5 |
0 |
4 |
5 |
6 |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу. 2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
|
3 |
3 |
M |
[0] |
[-0-] |
|
6 |
3 |
1 |
2 |
[-0-] |
|
7 |
1 |
3 |
M |
[-0-] |
|
5 |
[0] |
4 |
5 |
6 |
|
[-0-] |
[-0-] |
[-0-] |
[-0-] |
[0] |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 3), то решение недопустимое.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 5, столбец 5, строку1,столбец2.
Получаем сокращенную матрицу (элементы выделены):
|
3 |
3 |
M |
0 |
0 |
|
6 |
3 |
1 |
2 |
0 |
|
7 |
1 |
3 |
M |
0 |
|
5 |
0 |
4 |
5 |
6 |
|
0 |
0 |
0 |
0 |
0 |
Минимальный элемент сокращенной матрицы (1) вычитаем из всех ее элементов:
|
3 |
3 |
M |
0 |
0 |
|
5 |
3 |
0 |
1 |
0 |
|
6 |
1 |
2 |
M |
0 |
|
4 |
0 |
3 |
4 |
6 |
|
0 |
0 |
0 |
0 |
0 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
|
3 |
4 |
M |
0 |
1 |
|
5 |
3 |
0 |
1 |
0 |
|
6 |
1 |
2 |
M |
0 |
|
4 |
0 |
3 |
4 |
6 |
|
0 |
1 |
0 |
0 |
1 |
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
|
3 |
4 |
M |
0 |
1 |
0 |
|
5 |
3 |
0 |
1 |
0 |
0 |
|
6 |
1 |
2 |
M |
0 |
0 |
|
4 |
0 |
3 |
4 |
6 |
0 |
|
0 |
1 |
0 |
0 |
1 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
|
3 |
4 |
M |
0 |
1 |
|
5 |
3 |
0 |
1 |
0 |
|
6 |
1 |
2 |
M |
0 |
|
4 |
0 |
3 |
4 |
6 |
|
0 |
1 |
0 |
0 |
1 |
|
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
|
3 |
4 |
M |
[0] |
1 |
|
5 |
3 |
[0] |
1 |
[-0-] |
|
6 |
1 |
2 |
M |
[0] |
|
4 |
[0] |
3 |
4 |
6 |
|
[0] |
1 |
[-0-] |
[-0-] |
1 |
В результате получаем эквивалентную матрицу Сэ:
|
3 |
4 |
M |
0 |
1 |
|
5 |
3 |
0 |
1 |
0 |
|
6 |
1 |
2 |
M |
0 |
|
4 |
0 |
3 |
4 |
6 |
|
0 |
1 |
0 |
0 |
1 |
4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
|
3 |
4 |
M |
[0] |
1 |
|
5 |
3 |
[0] |
1 |
[-0-] |
|
6 |
1 |
2 |
M |
[0] |
|
4 |
[0] |
3 |
4 |
6 |
|
[0] |
1 |
[-0-] |
[-0-] |
1 |
Cmin = 2 + 2 + 2 + 2 + 0 = 8
2.3 Задача о замене оборудования[7]
Известно, что проблема замены старого парка машин новыми, устаревших орудий — современными — одна из основных проблем индустрии.
Оборудование со временем изнашивается, стареет физически и «морально»; в процессе эксплуатации либо падает производительность оборудования, либо растут эксплуатационные расходы, либо и то и другое. Поэтому задача о замене оборудования весьма актуальна.
Найти оптимальную стратегию эксплуатации оборудования на период продолжительностью 6 лет, если годовой доход r(t) и остаточная стоимость S(t) в зависимости от возраста заданы в таблице, стоимость нового оборудования равна P = 10, а возраст оборудования к началу эксплуатационного периода составлял 1 год.
Начало формы
Конец формы
|
T |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
r(t) |
8 |
8 |
7 |
7 |
6 |
6 |
5 |
|
S(t) |
10 |
7 |
6 |
5 |
4 |
3 |
2 |
Решение: I этап. Условная оптимизация (k = 6,5,4,3,2,1). Переменной управления на k-м шаге является логическая переменная, которая может принимать одно из двух значений: сохранить (С) или заменить (З) оборудование в начале k-го года. 1-й шаг: k = 6. Для 1-го шага возможные состояния системы t = 1,2,3,4,5,6, а функциональные уравнения имеют вид: F6(t) = max(r(t), (C); S(t) - P + r(0), (З ) ) F6(1) = max(8 ; 7 - 10 + 8) = 8 (C) F6(2) = max(7 ; 6 - 10 + 8) = 7 (C) F6(3) = max(7 ; 5 - 10 + 8) = 7 (C) F6(4) = max(6 ; 4 - 10 + 8) = 6 (C) F6(5) = max(6 ; 3 - 10 + 8) = 6 (C) F6(6) = max(5 ; 2 - 10 + 8) = 5 (C) 2-й шаг : k = 5. Для 2-го шага возможные состояния системы t = 1,2,3,4,5, а функциональные уравнения имеют вид: F5(t) = max(r(t) + F6(t+1) ; S(t) - P + r(0) + F6(1)) F5(1) = max(8 + 7 ; 7 - 10 + 8 + 8) = 15 (C) F5(2) = max(7 + 7 ; 6 - 10 + 8 + 8) = 14 (C) F5(3) = max(7 + 6 ; 5 - 10 + 8 + 8) = 13 (C) F5(4) = max(6 + 6 ; 4 - 10 + 8 + 8) = 12 (C) F5(5) = max(6 + 5 ; 3 - 10 + 8 + 8) = 11 (C) 3-й шаг : k = 4. Для 3-го шага возможные состояния системы t = 1,2,3,4, а функциональные уравнения имеют вид: F4(t) = max(r(t) + F5(t+1) ; S(t) - P + r(0) + F5(1)) F4(1) = max(8 + 14 ; 7 - 10 + 8 + 15) = 22 (C) F4(2) = max(7 + 13 ; 6 - 10 + 8 + 15) = 20 (C) F4(3) = max(7 + 12 ; 5 - 10 + 8 + 15) = 19 (C) F4(4) = max(6 + 11 ; 4 - 10 + 8 + 15) = 17 (C/ З ) 4-й шаг : k = 3. Для 4-го шага возможные состояния системы t = 1,2,3, а функциональные уравнения имеют вид: F3(t) = max(r(t) + F4(t+1) ; S(t) - P + r(0) + F4(1)) F3(1) = max(8 + 20 ; 7 - 10 + 8 + 22) = 28 (C) F3(2) = max(7 + 19 ; 6 - 10 + 8 + 22) = 26 (C/ З ) F3(3) = max(7 + 17 ; 5 - 10 + 8 + 22) = 25 ( З ) 5-й шаг : k = 2. Для 5-го шага возможные состояния системы t = 1,2, а функциональные уравнения имеют вид: F2(t) = max(r(t) + F3(t+1) ; S(t) - P + r(0) + F3(1)) F2(1) = max(8 + 26 ; 7 - 10 + 8 + 28) = 34 (C) F2(2) = max(7 + 25 ; 6 - 10 + 8 + 28) = 32 (C/ З ) 6-й шаг : k = 1. Для 6-го шага возможные состояния системы t = 1, а функциональные уравнения имеют вид: F1(t) = max(r(t) + F2(t+1) ; S(t) - P + r(0) + F2(1)) F1(1) = max(8 + 32 ; 7 - 10 + 8 + 34) = 40 (C) Результаты вычислений по уравнениям Беллмана Fk(t) приведены в таблице, в которой k - год эксплуатации, а t - возраст оборудования.
|
k / t |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
40 |
0 |
0 |
0 |
0 |
0 |
|
2 |
34 |
32 |
0 |
0 |
0 |
0 |
|
3 |
28 |
26 |
25 |
0 |
0 |
0 |
|
4 |
22 |
20 |
19 |
17 |
0 |
0 |
|
5 |
15 |
14 |
13 |
12 |
11 |
0 |
|
6 |
8 |
7 |
7 |
6 |
6 |
5 |
В таблице выделено значение функции, соответствующее состоянию (З) - замена оборудования.
II этап. Безусловная оптимизация (k = 6,5,4,3,2,1) Безусловная оптимизация начинается с шага при k = 1. Максимальной возможный доход от эксплуатации оборудования за годы с 1-го по 7-й составляет F1(1) = 40. Этот оптимальный выигрыш достигается, если на первом году не производить замены оборудования. К началу 2-го года возраст оборудования увеличится на единицу и составит: t2 = t1 + 1 = 1 + 1 = 2. Безусловное оптимальное управление при k = 2, x2(2) = (C/З), т.е. для получения максимума прибыли за оставшиеся годы необходимо в этом году провести замену оборудования. К началу 3-го года возраст оборудования увеличится на единицу и составит: t3 = t2 + 1 = 0 + 1 = 1. Оптимальное управление при k = 3, x3(1) = (C), т.е. максимум дохода за годы с 3-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется. К началу 4-го года возраст оборудования увеличится на единицу и составит: t4 = t3 + 1 = 1 + 1 = 2. Оптимальное управление при k = 4, x4(2) = (C), т.е. максимум дохода за годы с 4-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется. К началу 5-го года возраст оборудования увеличится на единицу и составит: t5 = t4 + 1 = 2 + 1 = 3. Оптимальное управление при k = 5, x5(3) = (C), т.е. максимум дохода за годы с 5-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется. К началу 6-го года возраст оборудования увеличится на единицу и составит: t6 = t5 + 1 = 3 + 1 = 4. Оптимальное управление при k = 6, x6(4) = (C), т.е. максимум дохода за годы с 6-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
Таким образом, за 6 лет эксплуатации оборудования замену надо произвести в начале 2-го года эксплуатации.