Календарное планирование

Многие задачи календарного планирования относятся к классу задач, для которых трудна конкретная аналитическая постановка, неярко выражена величина критерия эффективности и отсутствуют эффективные алгоритмы численного решения. Последнее связано с тем, что минимизируемые функции комбинаторных задач лежат не в непрерывной области переменных, а на различных дискретных перестановках элементов. Следовательно, применение приближенных методов, основанных на сочетании аналитических принципов и моделировании календарных планов с использованием правил предпочтительности, является наиболее перспективным направлением практического решения данного класса задач.

Среди приближенных методов  различают большую группу аналитико-приоритетных методов. Аналитико-приоритетные методы не следует смешивать с эвристическими. В аналитико-приоритетных методах имеется математическая модель с соответствующей функцией - критерием, что позволяет приблизить решение к оптимальному, тогда как в эвристических методах такая функция отсутствует, либо имеется в неявно выраженной форме или же задается как локальная функция приоритета. Эвристические методы строятся на использовании установленных свойств и приемов решения задач других смежных групп, а также интуитивных свойств и приемов поиска.

Глава 2. Примеры решения основных задач календарного планирования

 

2.1 Задача Джонсона  о двух станках⁵

Рассмотрим задачу последовательной обработки на двух машинах N различных  деталей, если известно время Ai и Bi обработки i -й детали на соответствующих машинах. Очевидно, что первая машина будет загружена полностью, но вторая может периодически оказываться в состоянии простоя. Попытаемся найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.

Если обозначить через Xi - время простоя в ожидании i - й детали, то

X₁=A₁;

X₁+X₂=max(A₁+A₂-B₁,A₁)

X₁+X₂ +X₃= max(A₁+A₂+A₃-B₁-B₂, A₁+A₂-B₁ A₁),…

Если обозначить через F(t, A_k, B_k/k=1..N) - суммарное время обработки N деталей при условии, что вторая машина включается с задержкой t и используется оптимальный порядок обработки, то c учетом принципа оптимальности (независимо от выбора начальной детали порядок выбора последующих должен быть оптимальным) имеем:

F(t, A_k, B_k/k=1..N)=min[A_i +F(B_i + max(t-A_i,0), A_k, B_k/k=1..N, k≠i

Если после i - й детали при оптимальном порядке обрабатывается j-я, то

 F(t, A_k, B_k/k=1..N)= A_i+ A_j+F(t_ij, A_k, B_k/k=1..N; k≠i, j), где

t_ij= B_j + max[B_i + max(t-A_i,0)- A_j,0]= B_j + B_i – A_j – A_i +max [t, max(A_i+ A_j - B_i,A_i]

При обработке в обратном порядке 

F(t, A_k, B_k/k=1..N)= A_j + A_i+ F(t_ij, A_k, B_k/k=1..N; k≠i, j), где

t_ji= B_i max[B_i + max(t-A_j,0)- A_i,0]= B_ji+ B_j - A_i - A_j +max [t, max(A_j+ A_i – B_j,A_i]

Если max(A_i+ A_j - B_i,A_i)< max(A_j+ A_i – B_j,A_i), то сначала разумнее обрабатывать j - ю деталь.

Можно показать, что указанное  условие необходимости перестановки эквивалентно условию 

min(A_j, B_i)< min(A_i, B_j)

Соответственно ищем среди всех значений A_i и B_i наименьшее. Если найденное значение совпадает с некоторым A_i, то i - ю деталь ставим на обработку первой; если оно совпадает с некоторым B_i, то последней. Эту процедуру повторяем для всех остальных деталей.

Пример. Пусть информация о времени обработки задана таблицей 1

Таблица 1

Время обработки деталей

i	1	2	3	4	5	6	7	8
Ai	4	4	30	6	2	9	13	9
Bi	5	1	4	30	3	13	9	9

 

Минимальное из значений равно 1 и соответствует B₂: вторая деталь обрабатывается последней. Минимальное из значений (кроме второго столбца) соответствует A₅: пятая деталь обрабатывается первой. Минимальное из значений в столбцах, кроме 2 и 5, равно A₁ и соответственно среди рассмотренных сейчас деталей эта деталь обрабатывается первой и т.д. В итоге упорядоченная информация принимает вид (таблица 2):

Таблица 2

Упорядоченная информация

I	5	1	4	8	6	7	3	2
Ai	2	4	6	9	9	13	30	4
Bi	3	5	30	9	13	9	4	1

 

Время простоя второй машины при  первичном порядке равно 

max(4,4+4-5,4+4+30-5-1,4+4+30+6-5-1-4,4+4+30+6+2-5-1-4-30,4+4+30+6+2+9-5-1-4-30-3,4+4+30+6+2+9+13-5-1-4-30-3-13,4+4+30+6+2+9+13-5-1-4-30-3-13)=max(4, 3, 32, 34, 6, 12, 12, 12)=34

Время простоя при  оптимальной перестановке равно 

max(2,2+4-3,2+4+6-3-5,2+4+6+9-3-5-30,2+4+6+9+9-3-5-30-9,2+4+6+9+9+13-3-5-30-9-13,2+4+6+9+9+13+30-3-5-30-9-13-9,2+4+6+9+9+13+30+4-3-5-30-9-13-9-4)=max(2, 3, 4, -17, -17, -17, 4, 4)=4

В процессе решения можно  было заметить, что существует и  другой оптимальный порядок обработки, связанный с неоднозначностью установки  детали 8.

 

2.2 Задача о назначениях⁶

Задача о назначениях  заключается в выборе такого распределениях ресурсов по объектам, при котором минимизируется стоимость назначений. Предполагается, что каждый ресурс назначается только один раз и каждому объекту приписывается только один ресурс.

Различные случаи применения данной задачи указаны в таблице 3.

Таблица 3

Случаи применения задачи

Ресурсы	Объекты	Критерии эффективности
Рабочие Грузовые автомобили Станки Экипажи коммивояжер	Рабочие места Маршруты Участки Рейсы города	Время Затраты Объем переработанной продукции Время простоя товарооборот

Матрица стоимостей назначения С определяется как: С=С(с_ij), где с_ij, i, j = 1,2,…,n – затраты, связанные с назначение i-го ресурса на j-й объект, n- число объектов или ресурсов.

Положим x_ij=1, если i-й ресурс назначается на j-й объект, и x_ij=0 в противном случае. Тогда решение задачи о назначении может быть записано в виде матрицы Х=(x_ij)_n*n.

Допустимое решение  задачи называется назначением. Оно  находится путем такого выбора элементов x_ij матрицы Х, что в каждой строке и в каждом столбце будет только один выбранный элемент. Элементы с_ij матрицы С, соответствующие выбранным элементам x_ij=1 матрицы Х, отметим кружками.

Например,

                  4          7         0

С=(с_ij)=     0          3         8

                            6          0         9

Тогда решение задачи о назначениях имеет вид:

      

 

 

Математическая модель и алгоритм решения задач. Математическая постановка задачи о назначении записывается в виде

             _{n   n}

L(X) = ∑∑c_ijx_ij→min

           ^{i=1 j=1}

                                 _n

при ограничениях ∑x_ij=1, i=1,2,….n

                               ^j=1

                                _n

                               ∑x_ij=1, j=1,2,….n

                               ⁱ⁼¹

                              x_ij=0 или 1.

Задача о назначениях  является частным случаем транспортной задачи, в которой а_i=b_j=1. поэтому задачу о назначениях можно решать с помощью алгоритмов, предназначенных для транспортной задачи. Однако есть и другой метод, который более эффективен, так как он учитывает специфику математической модели. Этот метод называют венгерским алгоритмом. Он состоит из следующих шагов:

1. проведение преобразования строк и столбцов матрицы С;
2. определения назначения;
3. модификация преобразования матрицы.

1-й шаг. Цель данного  шага – получение максимально возможного числа нулевых элементов в матрице С. Для этого из всех элементов каждой строки вычитаем минимальный элемент соответствующей строки, а из всех элементов каждого столбца вычитаем минимальный элемент соответствующего столбца.

2-й шаг. Если после выполнения 1-го шага в каждой строке и каждом столбце матрицы С можно выбрать по одному нулевому элементу, то полученное решение будет оптимальным назначением.

3-й шаг. Если допустимое  решение, состоящее из нулей,  не найдено, то проводим минимальное число прямых через некоторые столбцы и строки так, чтобы все нули оказались вычеркнутыми. Выбираем наименьшей невычеркнутый элемент. Этот элемент вычитаем из каждого невычеркнутого элемента и прибавляем к каждому элементу, стоящему на пересечении проведенных прямых.

Если после проведения 3-го шага оптимальное решение не достигнуто, то процедуру проведения прямых следует повторять до тех  пор, пока не будет получено допустимое решение.

Пример. Дана матрица ресурсов

 

С=(с_ij)=

 

 

Распределить ресурсы  матрицы С по четырем объектам.

Решение. 1-й шаг. Значение минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим матрицу вида

 

 

 

Значения минимальных элементов  столбцов 1, 2, 3 и 4 равны 5, 0, 0, 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим:

2-й шаг. Ни одно  назначение не получено, необходимо  провести модификацию матрицы  стоимостей.

3-й шаг. Вычеркиваем столбец 1, строку 3, строку или столбец 2. значение минимального невычеркнутого элемента равно 2:

 

 

 

 

Вычитаем его из всех невычеркнутых  элементов и, складывая его со всеми элементами, расположенными на пересечении двух линий, получим:

 

 

 

Следовательно, оптимальное решение:

 

          Х_опт =

 

Таким образом, первый ресурс направляем на 3-й объект, второй – 2-й  объект, третий ресурс – на 4-й объект, четвертый – на 1-ый объект. Стоимость  назначения: 9+4+11+4=28.

Примечания:

1) Если исходная матрица  не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной.

2) Если какой-либо ресурс  не может быть назначен на  какой-то объект, то соответствующая  стоимость полагается равной  достаточно большому числу М.

3) Если исходная задача является задачей максимизации, то все элементы матрицы С следует умножить на -1 и сложить с достаточно большим числом так, чтобы матрица не содержала отрицательных элементов. Затем следует решать задачу минимизации целевой функции.

4) Если число линий, необходимое для того, чтобы вычеркнуть нулевые элементы, равно числу строк или столбцов (квадратной матрицы), то существует назначение нулевой стоимости.

Пример:

Цех имеет пять станков разных типов, каждый из которых может выполнять  пять различных операций по обработке деталей. Известна производительность c_ij каждого станка при выполнении каждой операции, заданная матрицей

 

 

 

 

Определить, какую операцию и за каким станком следует  закрепить, чтобы суммарная производительность была максимальной при условии, что за каждым станком закреплена только одна операция.

Решение. В задаче требуется найти максимум целевой функции, в то время как алгоритм метода дан для задач на минимум. Поэтому умножим матрицу С на -1. сложим полученную матрицу, элементы которой отрицательны, с достаточно большим положительным числом, например с числом 10. Получим:

 

 

 

Минимальные элементы в строках  равны 3, 4, 4, 6, 4. вычтем их из соответствующих  элементов матрицы:

 

 

 

 

 

 

 

Так как назначение не получено, вычеркиваем  строку 2, столбы 2, 4, 5:

 

 

 

 

Минимальный элемент равен 1. вычитаем его из всех невычеркнутых элементов  и складываем со всеми элементами, расположенными на пересечении двух линий, получаем:

 

 

 

 

Оптимальное решение, соответствующее  последней матрице:

 

 

 

 

Суммарная производительность: 6+6+3+6+7=28

Таким образом, наибольшая суммарная производительность станков  цеха будет равна 28 деталям в единицу  времени, при этом за первым станком  надо закрепить 5-ю операцию, за вторым – 1-ю операцию, за третьим – 4-ю  операцию, за четвертым – 3-ю операцию, за пятым станком – 2-ю операцию.