Задача о двух технологических линиях

Постановка задачи

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

Обычно изделие проходит все этапы сборки на одной и той же линии. Однако иногда требуется, чтобы партия изделий была собрана за кратчайшее время, и такой порядок приходится нарушить. Для ускорения сборки изделие по-прежнему проходит все n рабочих мест в обычном порядке, однако менеджер может дать указание переместить частично собранное изделие с одной линии на другую, причем такое перемещение возможно на любом этапе сборки. Временем перехода от одного рабочего места к другому, если этот переход выполняется в пределах одной технологической линии, можно пренебречь. Время, которое требуется для перемещения изделия с технологической линии i на линию после прохождения рабочего места , равно , . Требуется определить, какие рабочие места должны быть выбраны на первой линии, а какие – на второй, чтобы минимизировать общее время, затраченное на сборку одного изделия.

Зададим условия задачи в таблице (табл.5).

Таблица 5

Временные параметры операций

Рабочее место линии 1
Время операции
Время перемещения изделия на линию 2 после прохождения рабочего места
Рабочее место линии 2
Время операции
Время перемещения изделия на линию 1 после прохождения рабочего места
Время от момента подачи начальной заготовки на линию до начала первой операции
Время от момента окончания последней операции до снятияготового изделия с линии

Решение задачи

Данную задачу можно отнести к задачам составления расписаний. Однако для ее решения удобно применить подход динамического программирования: разбиение задачи на n шагов, поиск оптимального решения начинать с последнего шага.

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

Техн. линия 1 Рабочие места M11 M12 M13 M14 M15 M16

M21 M22 M23 M24 M25 M26 Рабочие места Техн. линия 2

Вход

Выход

Рис.17. Схема технологических линий

Схема, представленная на рис.17, аналогична схеме маршрутов, связывающих пункты А и Б в задаче о поиске минимального маршрута (рис.4). В данной задаче такими пунктами являются «Вход» (состояние ) и «Выход» (состояния ). Весь маршрут и, следовательно, процесс управления, можно разбить на 7 шагов. Каждый из первых 6 шагов содержит 2 действия: перемещение изделия к рабочему месту и выполнение операции на этом рабочем месте. Состояниями системы можно считать нахождение изделия на рабочем месте после окончания выполнения операции, управлением – выбор одной из технологических линий для выполнения следующей операции, т. е. . Алгоритм решения задачи поиска минимального маршрута от пункта А до пункта Б уже подробно рассмотрен. Единственное отличие от решенной ранее задачи в том, что на каждом шаге k показатель эффективности должен учитывать и время , связанное с перемещением изделия на другую линию, и время на выполнение операции (нахождение на рабочем месте ). Целевая функция – суммарное время сборки изделия.

Перейдем к пошаговому решению.

Шаг k=7. К началу этого шага завершена последняя операция, для любого из двух возможных состояний (изделие находится или на линии 1, или на линии 2) остается только снятие изделия с линии:

(37)

Шаг k=6. К началу этого шага завершена пятая операция, для каждого из двух возможных состояний (изделие находится или на линии 1, или на линии 2) возможны 2 варианта: или изделие остается на этой же линии, или перемещается на другую линию. Для каждого из двух состояний необходимо определить условный минимум целевой функции при оптимальном управлении на двух последних шагах:

(38)

Шаг k=5. К началу этого шага завершена четвертая операция. Рассуждения аналогичны шагу при k=6:

(39)

Дальнейшие шаги выполняем аналогично.

Шаг k=4.

(40)

Шаг k=3.

(41)

Шаг k=2.

(42)

Шаг k=1. На первом шаге выбор оптимального управления выполняется для одного возможного начального состояния . При этом учитываем время от момента поступления заготовки на технологические линии до начала выполнения первой операции:

(43)

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

(44)

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

Техн. линия 1 Рабочие места M11 M12 M13 M14 M15 M16

M21 M22 M23 M24 M25 M26 Рабочие места Техн. линия 2

Вход

Выход

Рис.18. Оптимальное решение

Сравним полученное значение и время сборки на каждой линии при отсутствии перемещений.

Для технологической линии 1 это время составляет

(45)

Для технологической линии 2 это время составляет

. (46)

В данном примере использование комбинированной сборки оказалось эффективным.

6. Построение оптимальной последовательности операций

Постановка задачи

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

Алгоритм решения

Из условия следует, что состояние системы определено двумя параметрами: n – количеством принятых и оформленных машин по разгрузке товаров и m – количеством машин, отправляемых с товаром в магазины. Поэтому решение можно искать на плоскости в области допустимых состояний системы (рис.19). По оси абсцисс откладываем число разгруженных машин, а по оси ординат – число загруженных товаром машин. Можно построить на плоскости граф состояний процесса, в котором каждая вершина соответствует состоянию операции приема и отправки товара на оптовой базе. Ребра графа соответствуют выполнению работы по приему или отправке товара на очередной машине. Каждому ребру можно сопоставить издержки, связанные с выполнением операции по разгрузке или загрузке машины. Таким образом поставленная задача свелась к задаче о поиске оптимального маршрута от начального пункта до конечного.

Рис.19. Схема операций на складе

Пример

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

Решение

Решаем данную задачу аналогично задаче об оптимальном маршруте. Процесс управления разбивается на шагов. Решение предлагается выполнить самостоятельно.

В итоге должны получиться следующие результаты. Минимальные издержки . Оптимальное управление процессом разгрузки и загрузки машин товаром при данных условиях заключается в следующем: на первом и втором шагах следует оформить документы по разгрузке двух машин, на третьем – по загрузке одной машины, далее – снова две машины по разгрузке товара, затем три машины по загрузке и на последнем шаге оформить документы по разгрузке последней машины. При этом минимальные суммарные издержки по приему и отправке товаров для всех машин равны 73. Оптимальное решение выделено двойной линией на рис.20.

Рис.20. Оптимальное управление операциями на складе

Другие примеры задач

Принцип оптимальности Беллмана применим в решении многих интересных практических задач на производстве. Опишем общую постановку еще нескольких типов задач.