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

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

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

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

2.1 Задача Джонсона о двух станках[5]

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

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

X1=A1;

X1+X2=max(A1+A2-B1,A1)

X1+X2 +X3= max(A1+A2+A3-B1-B2, A1+A2-B1 A1),…

Если обозначить через 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/k=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= Bj + max[Bi + max(t-Ai,0)- Aj,0]= Bj + Bi – Aj – Ai +max [t, max(Ai+ Aj - Bi,Ai]

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

F(t, Ak, Bk/k=1..N)= Aj + Ai+ F(tij, Ak, Bk/k=1..N; k≠i, j), где

tji= Bi max[Bi + max(t-Aj,0)- Ai,0]= Bji+ Bj - Ai - Aj +max [t, max(Aj+ Ai – Bj,Ai]

Если max(Ai+ Aj - Bi,Ai)< max(Aj+ Ai – Bj,Ai), то сначала разумнее обрабатывать j - ю деталь.

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

              min(Aj, Bi)< min(Ai, Bj)

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

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

Таблица 1

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

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

Таблица 2

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

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

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 Задача о назначениях[6]

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

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

Таблица 3

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

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

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

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

Например,

                  4          7         0

С=(сij)=     0          3         8

                            6          0         9

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

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

             n   n

L(X) = ∑∑cijxij→min

           i=1 j=1

                                 n

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

                               j=1

                                n

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

                               i=1

                              xij=0 или 1.

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

1)     проведение преобразования строк и столбцов матрицы С;

2)     определения назначения;

3)     модификация преобразования матрицы.

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

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

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

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