5.5.1. Вычисление длины расписания для системы с тремя приборами
Пусть
время обслуживания требований на первом,
втором и третьем приборах
,
,
и
,
,
– моменты завершения обслуживания
требования, стоящего на i-м
месте в расписании на первом, втором и
третьем приборах соответственно.
Тогда
,
,
,
,
,
,
откуда
.
Пример 5.4. Дано пять деталей, которые последовательно обрабатываются на трех станках. Время обработки каждой детали на каждом станке указано в табл. 5.9. Вычислить длину расписания.
Таблица 5.9
i |
1 |
2 |
3 |
4 |
5 |
|
3 |
1 |
5 |
2 |
4 |
|
1 |
3 |
2 |
4 |
5 |
|
2 |
5 |
3 |
1 |
4 |
Расписание
.
Длина расписания вычисляется в табл.
5.10.
Таблица 5.10
|
2 |
4 |
5 |
3 |
1 |
|
1 |
3 |
7 |
12 |
15 |
|
4 |
8 |
13 |
15 |
16 |
|
9 |
10 |
17 |
20 |
22 |
Здесь
общее время обслуживания составит
.
5.5.2. Системы, для которых возможно построение оптимального расписания
Как было сказано выше, задача для системы с тремя приборами является NP-трудной. Однако существуют частные случаи, для которых возможно построение оптимального расписания с помощью конструктивного алгоритма.
Можно показать, что если
(5.5.1)
или
,
(5.5.2)
то достаточным условие оптимальности расписания является условие
,
следовательно, если система удовлетворяет условию (5.5.1) или (5.5.2), то при введении
,
,
можно свести задачу к системе с двумя приборами и найти оптимальное расписание с помощью алгоритма построения расписания (алгоритма Джонсона).
Заметим, что длина найденного расписания будет искаться для исходной системы.
Пример 5.5. Имеются пять деталей, которые последовательно обрабатываются на трех станках. Время обработки каждой детали на каждом станке указано в табл. 5.11.
Таблица 5.11
i |
1 |
2 |
3 |
4 |
5 |
|
3 |
4 |
5 |
4 |
6 |
|
3 |
1 |
2 |
4 |
3 |
|
2 |
5 |
1 |
6 |
4 |
Данная система удовлетворяет условию (5.4.1). Сведем ее к системе с двумя приборами (табл. 5.12) и решим с помощью алгоритма Джонсона.
Таблица 5.12
i |
1 |
2 |
3 |
4 |
5 |
|
6 |
5 |
7 |
8 |
9 |
|
5 |
6 |
3 |
10 |
7 |
В соответствии с требованиями алгоритма разобьем требования на группы (табл. 5.13):
Таблица 5.13
I группа |
|
II группа |
|||||
|
|
|
|||||
i |
2 |
4 |
|
i |
1 |
3 |
5 |
|
5 |
8 |
|
|
5 |
3 |
7 |
Оптимальное
расписание
.
Длина расписания вычисляется в табл.
5.14
Таблица 5.14
|
2 |
4 |
5 |
1 |
3 |
|
4 |
8 |
14 |
17 |
22 |
|
5 |
12 |
17 |
20 |
24 |
|
10 |
18 |
22 |
24 |
25 |
Здесь
общее время обслуживания составит
.