Задачи диспетчеризации и их автоматизация

Напомним, что под диспетчеризацией понимают разнообразные задачи, решаемые уже после завершения конструкторско-технологической подготовки производства (КТТП), т.е. непосредственно в ходе производственного процесса. Понятно, что к задачам диспетчеризации предъявляются еще более жесткие требования по строкам выполнения, чем к процедурам КТПП. Например, суточные и сменные задания должны разрабатываться не дольше, чем 3..4 часа, иначе вся разработка становится бесполезной.

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

Оптимизация раскроя

Оптимизация раскроя (англ. 2D packing) – одна из основных задач диспетчеризации. При ее решении возникает следующее трудноразрешимое противоречие: с одной стороны, для глубокой оптимизации и экономии материала нужны сложные и долго работающие алгоритмы; с другой стороны, в ходе производственного процесса просто нет времени на генерацию самых оптимальных планов раскроя, которая в сложных случаях требует нескольких часов работы даже современных быстрых компьютеров.

Что же делать? Как правило, в реальной жизни при оптимизации вводят некоторые критерии, по которым процесс размещения считается завершенным, даже если полученный вариант не является самым оптимальным. К таким критериям в первую очередь относится коэффициент использования материала (КИМ). Чем он выше, тем больше материала используется для изготовления деталей. Можно определять КИМ для каждого генерируемого алгоритмом плана раскроя за заданный период времени и применять тот план, у которого КИМ окажется максимальным. Хотя полученное решение не является глобальным экстремумом функции размещения, в условиях дефицита времени оно оказывается оптимальным.

Задачами оптимизации раскроя занимались и занимаются многие исследователи, в том числе такие известные, как Колмогоров, Келдыш, Гаусс. Несмотря на кажущуюся простоту задачи, и по сей день нет единственного наилучшего и универсального алгоритма ее решения. Это связано как со сложностью самой задачи, так и с различными видами раскроя, применяемыми в промышленности (Рис. 9.1).

Рис. 10.1 - Классификация видов раскроя.

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

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

Рис. 10.2 – Типовые раскрои полосы.

Оптимизация одномерного раскроя. Рассмотрение задач оптимизации раскроя начнем с простейшего одномерного случая – раскроя длинномерного проката. Применение длинномерного сортового металлопроката неизбежно приводит к образованию потерь на некратность материала по длине. Отходы металла в среднем по предприятиям машиностроения составляют 29%, что свидетельствует о наличии больших резервов экономии. Для сортового проката отходы составляют от 35 до 60%, из них лишь половина используется повторно.

Задача оптимального раскроя длинномерного проката решается по-разному в зависимости от типа производства. Для крупносерийного и массового производства характерно получение значительного числа заготовок одинаковой длины L_заг из материала стандартной длины L_мат. В данном случае отход на некратность

(8)

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

В условиях средне- и мелкосерийного производства чаще решается задача оптимального получения n₁ заготовок длиной , n₂ заготовок длиной ,...n_m заготовок длиной  (m - число рассматриваемых размеров заготовок из одного и того же материала в производственной программе предприятия) из материала длиной L_мат. При этом решается задача целочисленной оптимизации вида

(9)

где - вектор технологических параметров оптимизации, указывающий приоритет i-й заготовки в производстве (при р_i=0 i-я заготовка может не изготавливаться, при р_i=a обязательно получение а заготовок длины L_загi).

Приоритет заготовки назначается технологом в зависимости от назначения детали. Уже при малых значениях n решение задачи (2) путем полного перебора оказывается неприемлемым, поскольку число действий составляет порядка . К тому же в реальных производственных условиях использование деловых отходов (например, отходов на некратность) в качестве исходных материалов приводит к наличию на складе материалов разной длины , где M - число размеров материалов.

Рис. 10.3 - Блок-схема алгоритма оптимального раскроя.

Представим имеющийся набор материалов в виде отношения R_M:

(10)

где домен L_мат содержит длину материала, а домен I - тот или иной идентификатор материала (инвентарный номер, код, адрес складской ячейки и т.д.)

Домен L_мат является ключевым - по нему производится упорядочивание отношения R_М. Число кортежей в отношении R_M равно М.

Требуемый производственной программой набор заготовок представим в виде отношения R_B:

(11)

где домен L_заг содержит длину заготовки, а домен n - программу выпуска данной заготовки.

Число кортежей в отношении R_B равно m. Из (1) следует, что минимизировать W_нк можно либо уменьшением L_мат, либо увеличением  и n_i. Иными словами, должно соблюдаться правило: “делаем максимально возможное число самых длинных заготовок из самого короткого материала”. Тогда можно предложить универсальную методику оптимального раскроя длинномерного проката, блок-схема которой показана на Рис. 9.3 .

В блоках 1 и 2 выполняется динамическое упорядочивание отношений R_M и R_B. Блок 3 проверяет условие прекращения работы - равенство нулю числа кортежей m в отношении R_B. В блоке 4 рассчитывается число k заготовок наибольшей длины, которые можно изготовить из материала наименьшей длины. Если длина самой длинной заготовки превышает длину самого короткого материала (блок 5), следует взять следующий по возрастанию длины материал. Если ни один из материалов не подходит, кортеж исключается из рассмотрения и помечается как заготовка, разместить которую не удалось. Далее проверяется, не превышает ли значение k заданной программы выпуска текущей заготовки и при необходимости k уменьшается до n (блоки 6 и 8). В блоке 7 вносятся изменения в отношения R_M и R_B: длина материала заменяется текущим отходом на некратность, а программа выпуска детали уменьшается на число размещенных заготовок. Если все заготовки данной длины размещены (блок 9), то кортеж исключается из отношения R_B (блок 10). При реализации методики была предусмотрена система сохранения технологической информации в виде отношения, содержащего идентификаторы материалов и списки заготовок, изготавливаемых из каждого материала, а также другие параметры (отход на некратность, коэффициент использования материала и т.д.) Поскольку операции динамического упорядочивания выполняются исключительно эффективным методом двоичного поиска, среднее число действий составляет примерно m ´M, а не m! ´M, как в случае полного перебора.

Табл. 9.1 - Результаты оценки эффективности алгоритма.

Рис. 10.4- Диаграмма эффективности работы методики оптимизации.

Оптимизация двумерного раскроя. Рассмотрим теперь возможные способы решения задачи оптимизации раскроя листовых материалов. Перебор всего множества вариантов раскроя, для реальных заданий не представляется возможным из за очень большого количества вариантов. Один из возможных способов – так называемый алгоритм «уступок», разработанный А. Бабченко. Результат работы этого алгоритма является субоптимальным (т.е. либо оптимальным, либо близким к нему). Глубину перебора, а, значит, и время работы алгоритма можно контролировать.

Алгоритм «уступок» можно описать как последовательность действий:

1 шаг. Детали в задании упорядочиваются по убыванию размеров.

2 шаг. Начинается перебор вариантов очередной карты раскроя, при этом в первом варианте присутствуют детали из начала списка (т.е. большие, а значит потенциально менее удобные), в следующих вариантах большие детали вытесняются более мелкими; перебор осуществляется до того момента, пока не будет достигнута текущая уступка, либо будет просмотрено заданное количество вариантов.

3 шаг. Выбирается лучший из полученных вариантов очередной карты раскроя.

4 шаг. Детали, входящие в выбранный вариант, удаляются из задания.

5 шаг. Если в задании остались детали, повторяем все, начиная с шага 2.

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

При больших объемах производства существенными оказывается затраты на перенастройку оборудования, на котором осуществляется раскрой. В таких случаях бывает предпочтительнее получить менее оптимальный результат, при условии что количество разных карт раскроя (а значит и затрат на перенастройку) будет меньше. Тогда меняется цель оптимизации – либо получить минимальный отход, либо минимальное количество карт.