Алгоритм интеллектуального планирования технологических процессов

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

Планирование работы технологического оборудования, минимизирующее суммарное время переналадок, является существенным резервом повышения производительности ПС, в первую очередь, за счет сокращения простоев оборудования. В теории расписаний учет времени, требуемого на переналадку оборудования, производится двумя следующими способами. В первом способе время переналадки прибавляется к времени операции обработки, что позволяет, учитывая косвенно время переналадки, исключить его из рассмотрения [1]. Способ основан на допущении, что время переналадки модуля на выполнение работы j не зависит от работы i, выполняемой на смежных модулях перед работой j. Однако это допущение во многих приложениях неприемлемо. Во втором способе время операции обработки прибавляется к времени переналадки, при этом из рассмотрения исключается время технологической операции, а задача минимизации времени переналадок сводится к решению задачи коммивояжера [1]. Недостатком такого способа является отсутствие простых и эффективных методов решения задачи коммивояжера.

Опишем модель, в рамках которой может быть применен предлагаемый алгоритм. Выделим уровень, требующий оптимального планирования (в дальнейшем будем называть его обрабатывающей машиной). Считаем, что обрабатывающая машина может находиться в одном из состояний S, S = 1,…,R, в каждом из которых обрабатываются изделия в соответствии с номером состояния номенклатуры. Переналадкой будем называть перевод машины из состояния i в состояние j. Будем считать, что выделенная в результате декомпозиции технологическая подсистема включена в общий технологический процесс, и, следовательно, изделия должны быть обработаны к определенным моментам времени – директивным срокам. Выполнение на машине определенной технологической операции будем в дальнейшем называть работой. На машине необходимо выполнить N работ. Директивные сроки выполнения работ D_i, i = 1,…,N определены. Работы поступают на обслуживание в моменты времени t_i, i = 1,…,N

Машина может быть налажена на одно из к состояний. Время переналадки машины из состояния i в состояние j определяется с помощью матрицы Считаем, что элементы матрицы обладают следующими свойствами: Это условие имеет важное значение для построения и обоснования алгоритма. Считаем, что это условие не является ограничивающим: если оно не выполняется, можно провести через промежуточное состояние 1, и тогда условие будет выполнено.

Работы, требующие обслуживания на машине, обозначим через P₁^S,…,P_N^S, где i – порядковый номер работы, s = 1,…,k – требуемая наладка машины для выполнения работы i.

Предполагаем, что выполнены следующие условия: работы выполняются без прерываний; в каждый момент времени на машине может выполняться не более одной работы. Необходимо определить порядок выполнения работ на машине, удовлетворяющий директивным срокам выполнения работ D_i (i = 1,…,N) и минимизирующий суммарное время переналадок машины Т(Р).

Предлагаемый алгоритм решения задачи составления расписания основан на известном алгоритме поиска кратчайшего пути между вершинами графа [2]. Рассмотрим алгоритм поиска кратчайшего пути подробнее. Пусть дан граф G, однозначно задаваемый набором его вершин и дуг. Вершины графа обозначим порядковым номером, дугу графа, соединяющую вершину i с вершиной j, - через . Каждой дуге сопоставляется число r_ij – длина дуги . Если дуга отсутствует, считаем, что r_ij = . В графе G выделено множество начальных (i₁^h,…,i_n^h) и конечных вершин. Необходимо построить минимальный путь, соединяющий начальные вершины графа с конечными вершинами, причем длина пути равна сумме длин всех входящих в него дуг. Каждой вершине графа G сопоставим два числа: R₁ – длину пути из начальных вершин в вершину i и N₁ – номер вершины, из которой произведен переход в вершину i.

Кратчайший путь в графе G рассчитывается по следующему алгоритму.

1. Присвоить начальные значения:R₁ = 0, если R₁ = , если

i N₁ = 0 для ( - число, большее суммы всех длин дуг графа).

2. Последовательно просмотреть все вершины i графа G, для которых

. Для каждой вершины j вычислить новое значение

Если тогда присвоить

3. Если выполнение п. 2 приводит к изменению длины R, повторить п. 2, в

противном случае перейти к п. 4.

4. Найти среди конечных вершин графа вершину с минимальной длиной R.

5. Восстановить по меткам N кратчайший путь из найденной в п. 4 вершины.

Применим данный алгоритм к решению задачи оптимизации переналадок. Построим граф задачи так, чтобы маршрут из начальных вершин графа в конечные можно было бы интерпретировать как некоторое расписание для обрабатывающей машины. Сгруппируем работы, требующие одной наладки машины: Расположим работы в группах в порядке возрастания директивных сроков, т.е. для любых работ если i<j, D_i<D_j. На ортогональных осях k-мерного пространства в зафиксированной последовательности отложим по группам время выполнения работ. Через полученные точки построим (k-1)-мерные подпространства, ортогональные соответствующим осям. Пересечение r-подпространств образует вершины, пересечение (k-1)-подпространств – дуги графа. Полученный граф обозначим через G^’. Движение в графе G^’ по дуге, параллельной некоторой оси, будем интерпретировать как выполнение соответствующей работы, отложенной на этой оси. Длина дуги принимается равной времени выполнения соответствующей работы. Некоторая вершина i графа обозначает такое состояние, когда на машине выполнены все работы, координаты начала которых меньше координаты вершины i. Выделим в графе G^’ начальную Н и конечную К вершины.

Тогда путь из начальной вершины в конечную можно рассматривать как некоторое расписание. Граф G^’ является вспомогательным. Преобразуем его в граф G – рабочий граф для решения задачи. Будем считать, что хотя это условие не обязательно. Каждую вершину графа G^’ преобразуем в группу вершин, состоящую из k вершин, попарно соединенных между собой. Каждая вершина группы соединяется с двумя дугами графа G^’, параллельными оси соответствующей наладки машины. Дуги, соединяющие вершины в группах, задают процесс переналадки машины и имеют длину, равную времени соответствующей переналадки Начальная и конечная вершины графа G^’ преобразуются соответственно в группу начальных и конечных вершин графа G. Длина любого маршрута на графе G из начальных вершин в конечные: L = T + T(P^П), где: Т – суммарное время выполнения всех работ, является постоянным;Т(Р^П) – суммарное время переналадок машины, зависящее от расписания Р.

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

С учетом вышеизложенного предлагается следующий алгоритм решения поставленной задачи.

1.Присвоить начальные значения:R_i = 0, если R_i = , если

N_i = 0 для

2. Последовательно просмотреть все вершины i графа G, для которых .

Вычислить для каждой вершины j новое значение Если

тогда присвоить где директивный

срок работы (принимаем равным ).

3 .Если выполнение п. 2 приводит к изменению R_i, повторить п. 2, в противном

случае перейти к п. 4.

4 .Если все конечные вершины имеют т.е. конечные метки не получены,

то задача не имеет решения, в противном случае перейти к п. 5.

5. Найти среди конечных вершин графа вершину с минимальной R_i.

6 .Восстановить по меткам N_i кратчайший путь из найденной в п. 4 вершины.

Необходимым условием построения графа G является фиксирование порядка выполнения работ в группах – по возрастанию директивных сроков выполнения работ. Введение такого порядка во много раз ограничивает область поиска оптимального решения. Всего же существует графов для данной задачи. Естественно предположить, что существует другой оптимальный порядок выполнения работ в группах, зафиксировав который можно построить расписание с меньшим суммарным временем переналадок, чем то, что дает описанный алгоритм. Однако это не так, что доказывает следующая теорема.

ТЕОРЕМА. Пусть дано допустимое (удовлетворяющее директивным срокам) расписание Р с суммарным временем переналадок машины Т^П(Р), тогда существует допустимое расписание , являющееся маршрутом на построенном графе G, с суммарным временем переналадок (1).

Зафиксированный порядок выполнения работ в группах оптимальный для данной задачи. Доказательство этой теоремы основано на использовании неравенства (1), справедливого для матрицы времен переналадок .

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

Литература:

1. Танаев В.С. Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы, - М.,1984.

2. Майника Э.Алгоритм оптимизации на сетях и графах.- М.,1981.

3. Исследование операции. Т. 1,2. - М ., 1981.

4. Болнокин В.Е., Чинаев П.И. Анализ и синтез систем автоматического управления на ЭВМ – алгоритмы и программы. – М., 1991.

Болнокин В.Е., г.Москва, Данг Ван Уи, Нгуен Ван Нганг,

г.Хайфон, Социалистическая Республика Вьетнам