§ 59. Задачи о временном упорядочении

Для некоторых задач оптимизации, имеющих комбинаторный характер, подход с помощью теории графов не представляется наиболее естественным. Таковы часто встречающиеся задачи о временном упорядочении.

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

Рис. 389.

Требуется минимизировать время, в течение которого станок остается незанятым; задача иногда формулируется как требование минимизировать общее время обработки изделий, включающее время работы и время простоя станка

На рис. 389 схематически показан случай обработки шести изделий двумя станками. Время обработки каждого из изделий дается белым прямоугольником, время простоя — заштрихованными прямоугольниками.

Можно обобщить задачу на случай изделий и станков. При минимизирование общего времени обработки и минимизирование времени простоя станков — задачи, вообще говоря, различные.

Известен алгоритм для случая и, с одним ограничением, для Это — алгоритм Джонсона; можно также использовать метод ветвления и ограничения. В общем случае можно применять эвристические методы.

Алгоритм Джонсона. Случай двух станков. Сначала сформулируем алгоритм и дадим пример его использования, а затем уже приведем обоснование алгоритма.

1) Выберем в матрице наименьший элемент

2) Если этот элемент находится в первой строке, то начинаем с изделия если во второй, то заканчиваем изделием

3) Рассматриваем все изделия, исключая и действуем, как указано в 1) и 2). Поступаем так, пока не исчерпаем все

Пример. Рассмотрим следующую матрицу

Наименьший элемент матрицы (59.1) есть Он находится во второй строке, поэтому процесс надо заканчивать обработкой изделия Затем идет элемент следовательно, предпоследним нужно обрабатывать изделие

Рис. 390.

Далее, поэтому перед должно проходить обработку изделие

Рис. 391.

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

Результат представлен на рис. 390.

На рис. 391 представлен результат другого упорядочения (всего их :

Обоснование алгоритма. Пусть общее время, которое проходит с начала обработки первого изделия на станке и до конца обработки последнего изделия на станке Фиксируем некоторый порядок прохождения изделий . Пусть -время простоя второго станка

после окончания обработки и до начала работы с изделием Тогда

где

Так как , известны, то для минимизации достаточно найти минимум

Рис. 392.

Обозначим также

Очевидно, что (рис. 392)

Следовательно,

Для суммы получаем

Аналогично

и

Эта формула легко переносится на слагаемых;

или

Полагая

имеем

Обозначим теперь первоначальный порядок обработки изделий через

а через порядок, в котором переставлены местами

Значения полученные, исходя из порядков 5, и 52, совпадают для всех а, кроме, быть может,

1) Имеем

если

2) Если

то один из двух порядков предпочтительнее. Порядок в котором следует за предпочтительнее в котором предшествует если

Так как

и

то мы можем записать

и

Соотношение (59.20) перепишется тогда так:

или

Таким образом, порядок предпочтительнее если

Рассмотрим теперь порядок

Не следует изменять порядок если для любой пары соседних индексов имеем

Это выполняется, если меньше или равно В этом случае (59.29) равносильно

Отсюда следует, что если в матрице есть не превосходящее всех других то порядок обработки должен начинаться такое может равняться нескольким другим или но (по это не препятствует выбору в качестве начального элемента.

Соотношение (59.29) выполняется также, если меньше или равно В этом случае оно равносильно

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

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

Случай трех станков. Алгоритм Джонсона применим и в этом случае, если

или

где

Нахождение оптимального порядка производится с помощью сумм

Пример. Пусть в матрице (59.34) даны числа

Выполнено условие

так как Следовательно, можно использовать алгоритм Джонсона.

Рис. 393.

В качестве оптимального порядка получают одну из двух последовательностей

для каждой из которых время простоя равно 35. Рис. 393 иллюстрирует полученный результат.

УПРАЖНЕНИЯ

(см. скан)