Определение оптимального порядка обработки деталей на трех станках

Определение оптимального  порядка  обработки  деталей  на  трех станках.

Таблица 1. Исходные данные. Вариант №4.

   Минимальное  время на чистовую  обработку  равно  6  мин,  что  больше  или  равно максимального времени  на фрезерование - 6 мин.

   Тогда исходные данные можно представить в следующем виде:

Таблица 2. Сведение задачи к частному случаю.

   Применим алгоритм Джонсона:

Предварительный шаг: Построим матрицу времён    

ШАГ 1:    Выбираем в матрице  минимальный элемент  . Так как он находится в 1-ой строке, то деталь  Д6 будем обрабатывать первой. Переходим к шагу 2.

ШАГ 2:     Исключаем из рассмотрения 6-ой столбец матрицы , относящийся к упорядоченной детали Д6. Множество элементов матрицы  не пусто. Переходим к шагу 1.

ШАГ 1:    Выбираем в матрице  минимальный элемент  . Так как он находится в 1-ой строке, то деталь  Д3 будем обрабатывать после детали Д6. Переходим к шагу 2.

ШАГ 2:     Исключаем из рассмотрения 3-ий столбец матрицы , относящийся к упорядоченной детали Д3. Множество элементов матрицы  не пусто. Переходим к шагу 1.

ШАГ 1:    Выбираем в матрице  минимальный элемент  . Так как он находится в 1-ой строке, то деталь  Д1 будем обрабатывать после детали Д3. Переходим к шагу 2.

ШАГ 2:     Исключаем из рассмотрения 1-ый столбец матрицы , относящийся к упорядоченной детали Д1. Множество элементов матрицы  не пусто. Переходим к шагу 1.

ШАГ 1:    Выбираем в матрице  минимальный элемент  . Так как он находится во 2-ой строке, то деталь  Д2 будем обрабатывать последней. Переходим к шагу 2.

ШАГ 2:     Исключаем из рассмотрения 2-ой столбец матрицы , относящийся к упорядоченной детали Д2. Множество элементов матрицы  не пусто. Переходим к шагу 1.

ШАГ 1:    Выбираем в матрице  минимальный элемент  . Так как он находится во 2-ой строке, то деталь  Д5 будем обрабатывать до детали Д2. Переходим к шагу 2.

ШАГ 2:     Исключаем из рассмотрения 5-й столбец матрицы , относящийся к упорядоченной детали Д5. Множество элементов матрицы  не пусто. Переходим к шагу 1.

ШАГ 1:    Выбираем в матрице  минимальный элемент  . Так как он находится во 2-й строке, то деталь  Д4 будем обрабатывать до детали Д5. Переходим к шагу 2.

ШАГ 2:     Исключаем из рассмотрения 4-й столбец матрицы , относящийся к упорядоченной детали Д4. Множество элементов матрицы   пусто.

     Итак, получено оптимальное расписание:  (Д6, Д3, Д1, Д4, Д5, Д2).Результат занесём в последнюю строку таблицы 2. В нашем случае вариантов оптимальных решений много, укажем несколько из них:

(Д3, Д6, Д1, Д4, Д5, Д2);

(Д6, Д1, Д4, Д5, Д2, Д3).

     Построим график Ганта для обработки деталей по первому варианту: (Д6, Д3, Д1, Д4, Д5, Д2).