Современные информационные
технологии/3. Программное обеспечение
К.т.н. Денисов А.Р., Баранов А.А.
Костромской государственный университет им. Н.А. Некрасова, Россия
Алгоритм балансировки производственных линий
Одной из тенденций
развития современного производства является переход к средне- и мелкосерийности.
В данных условиях ключевой проблемой становится повышение гибкости производственной
системы, в частности, максимально возможное сокращение сроков подготовки
производства и эффективная организация производственного процесса [1]. Это
требует изменения формы представления результатов технологического проектирования,
а именно представление технологического процесса (ТП) в виде графа следования
технологических операций (ТО) [2, стр.
86]. Однако такой подход требует более сложных алгоритмов планирования. Так,
например, даже в простейшем случае (изготовление одного вида изделия на одной производственно линии) на основании графа следования ТО
изготовления женского головного убора (рис. 1) могут быть сформированы
следующие маршруты обработки: 1®2®3®4®5®6®7; 1®2®4®3®5®6®7; 1®2®4®5®3®6®7; 1®4®2®3®5®6®7; 1®4®2®5®3®6®7; 1®4®5®2®3®6®7. Естественно, часть маршрутов
обработки не могут быть применены в производственных условиях предприятия, что
связано:
· с отсутствием в составе ПЛ
оборудования, необходимого для выполнения ТО изготовления изделий;
· с расположением оборудования внутри
ПЛ.
Рис. 1.
Сетевой план ТП изготовления головного убора
Во втором случае
структура производственной линии (ПЛ) накладывает ограничения на некоторые
варианты маршрутов обработки одного изделия. Так, например, при развертывании графа
следования ТО (рис. 1) на ПЛ (рис. 2) недопустимыми являются маршруты: 1®4®2®3®5®6®7; 1®4®2®5®3®6®7; 1®4®5®2®3®6®7. Это
связано с тем, что структура данной ПЛ предполагает первоначальное выполнение
операций раскроя и дублирования. Однако даже в этом случае остаются возможными
три варианта маршрутного описания, каждый из которых необходимо проверить, а затем
среди них выбрать наилучший.
Рис 2. Пример модели производственной линии
в виде сети Петри
Особенно остро проблема
планирования стоит в многономенклатурном производстве, когда необходимо
обеспечить одновременное изготовление нескольких типов изделий заданных объемов
выпуска на существующих ПЛ (балансировка ПЛ). Проведенный анализ показал, что
наиболее эффективно задачу балансировки можно решить через использование
имитационного моделирования с использованием сетей Петри. В этом случае
структура производственной линии будет иметь вид (рис. 2). Основным недостатком
такого подхода является отсутствие формальной аналитической зависимости при
определении времени работы ПЛ, что делает невозможным поиск оптимума по используемым
критериям эффективности классическими методами оптимизации. Вследствие этого
при решении задачи балансировки ПЛ был использован алгоритм, основанный на
принципах эволюционной оптимизации (рис. 3.):
Рис 3. Алгоритм балансировки
производственных линий
Шаг 1. Определение соответствий
(выполнимости) технологических операций изготовления изделий и организационных
операций производственных линий. В результате выполнения этого шага для каждого сочетания
«тип изделия – ПЛ» формируется матрица выполнимости, в которой в качестве столбцов
выступают организационные операции ПЛ, а в качестве строк – ТО изготовления
изделия. В каждую ячейку матрицы ставится «1», если соответствующая ТО может
быть выполнена на рабочем месте соответствующей организационной операции, и «0»
– в противном случае.
Шаг 2. Определение всех возможных вариантов
изготовления изделий.
На данном этапе на основе матриц выполнимости формируются все варианты
изготовления изделий на каждой ПЛ. Каждый вариант проверяется на возможность
его выполнения по алгоритму [2, стр. 88], в соответствии с которым для сетевого
плана ТП и структуры ПЛ формируются матрицы достижимости Мтп и Мпл, где:
Далее формируется
результирующая матрица Мр:
Если полученная матрица
является «нулевой», то анализируемый маршрут обработки выполним на данной ПЛ, в
противном случае – невыполним. Результаты анализа маршрутов 1®2®3®4®5®6®7 и 1®4®2®3®5®6®7 на
соответствие ПЛ (рис. 2) представлены на рис. 4.
Если какой-либо из
анализируемых вариантов не может быть выполнен, то он удаляется. При этом все
оставшиеся варианты получают собственные идентификаторы.
Шаг 3. Первоначальное формирование особей
эволюционного алгоритма. На данном этапе случайным образом формируются
несколько различных особей (вариантов распределения изделий по ПЛ), где каждая
особь имеет вид (рис. 5). При этом учитывается, что часть генов особей не будет
использоваться вследствие невозможности изготовления некоторых изделий на
отдельных ПЛ.
Маршрут 1®2®3®4®5®6®7
Маршрут 1®4®2®3®5®6®7
Рис. 4. Примеры анализа применимости маршрутов обработки для ПЛ
|
|
Линия 1 |
Линия 2 |
… |
Линия M |
|||
|
№ варианта |
Кол-во |
№ варианта |
Кол-во |
№ варианта |
Кол-во |
||
|
Изделие 1 |
|
|
|
|
… |
|
|
|
Изделие 2 |
|
|
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
|
Изделие N |
|
|
|
|
|
|
|
Рис. 5.
Структура хромосомы особи балансировки
производственной линии
Шаг 4. Циклическое улучшение полученных
популяций методом эволюционной оптимизации. При выполнении данного этапа
применяются следующие виды мутаций:
· мутация 1 –
изменение варианта изготовления изделия на одной ПЛ;
· мутация 2 – перемещение одного изделия с одной ПЛ на другую, при
этом проверяется возможность такого перемещения, и если оно невозможно, то
новая особь считается «мертворожденной»;
· кроссинговер – обмен между двумя особями распределениями одного
типа изделия по ПЛ.
Проведенный
вычислительный эксперимент показал, что предлагаемый алгоритм позволяет
добиться высокого качества балансировки ПЛ за приемлемое время (время
календарного планирования работы ПЛ в
три смены по 8 часов составляет 7.29 часов, что требует наличия только одного
соответствующего специалиста). Это является достаточным условием для
подтверждения эффективности данного алгоритма.
Литература:
2. Митрофанов С.П. Технологическая подготовка гибких производственных
систем / С.П. Митрофанов, Д.Д. Куликов. – Л.: Машиностроение, 1987. – 352
с.