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

На правах рукописи Малышев Дмитрий Николаевич

Разработка автоматизированных средспз оптимизации одномерного раскроя

Специальность 05 13 01-«сисгемный анализ, управление и обработка информации»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

г Долгопрудный 2007

□030Б028Т

003060287

Работа выполнена на кафедре прикладных информационных технологий факультета физической и квантовой электроники Московском физико-техническом институте (государственный университет)

Научный руководитель

д ф -м н , проф. Карелова О Л.

Официальные оппоненты

д ф -м.н , проф Дикусар В.В. д т н, проф. Умнов А Е

Ведущая организация.

Институт проблем управления РАН

Защита состоится 26 июня 2007 г в 14 00 на заседании диссертационного совета Д212 133 01 при Московском государственном институте электроники и математики по адресу

109028, Москва, Б Трехсвятительский пер , д 1-3 12, стр 8

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики.

Автореферат разослан 24 мая 2007 г

Ученый секретарь диссертационного совета

ктн,доцент С.Е Бузников

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы

Подготовительно-раскройное производство относится к классу материалоемких производств Именно поэтому, во многом экономические показатели предприятий, на которых выполняются операции раскроя, напрямую связаны с задачей оптимального расхода материалов

На практике, процесс оптимизации расхода рулонных материалов зависит от оптимальности Ш и 20 карт кроя, составляемых на предприятиях Кроме того, следует отметить, что данный процесс требует обработки значительных объемов информации (информации о паспортах материалов, требований по оптимальности, организационных особенностей конкретного предприятия и т п) - всех тех параметров, которые используются при выполнении расчета В настоящее же время решение данной задачи основывается на опыте и интуиции квалифицированных работников данной сферы Выполнение подобной работы без привлечения вычислительных средств, естественно приводит к завышенным затратам временных и материальных ресурсов Поэтому требуется разработка современных вычислительных средств (программ), позволяющих формировать решения с большей степенью оптимальности и научной обоснованностью Это особенно актуально в условиях все возрастающей конкуренции на рынке в условиях перехода России к рыночным отношениям

Не менее важным аспектом при решении задач оптимального расхода материалов является соблюдение всех необходимых технологических требований, предъявляемым к виду получаемых карт кроя

Кроме того, актуальным является и рассмотрение другого аспекта -глобальной системной интеграции производства, то есть объединение единой

3

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

На большинстве предприятий выполнение операций, входящих в комплекс работ подготовительно-раскройного производства, выполняется без привлечения современных вычислительных средств Как уже говорилось, это приводит к повышенным временным, а также кадровым затратам, и как следствие, снижению экономических показателей предприятия Тем не менее, интенсивное развитие информационных технологий в последнее десятилетие позволяет создавать автоматизированные средства для выполнения все большего спектра задач, которые предъявляют новые требования к организации работы предприятий В настоящее время все более актуальными становятся вопросы автоматизации производства в полном объеме с целью возможного перехода к созданию на предприятии единой информационной среды, позволяющей гибкое интегрирование современных средств проектирования, производства, управления (Computer Aided Design, Computer Aided Manufacturing, Product Data Managment систем) и т д, которые позволяют эффективно решать задачи оперативного планирования производства Поэтому в таких условиях особенно важным становится поиск новых подходов, обеспечивающий целесообразную перестройку системы оптимального расчета карт кроя с учетом жизненных реалий, в частности вопросы создания САМ средств для рассматриваемой в работе задачи одномерного раскроя материала Уровень развитие вычислительной техники в последние десятилетия позволяет успешно решать поставленные задачи в необходимом для практики объеме, а также качестве

Целью настоящей диссертационной работы является разработка алгоритмов

расчета одномерных карт кроя, а также практическая реализация

4

программной среды для автоматизации процесса составления оптимальных одномерных карт кроя для уменьшения количества нерациональных отходов

Методы исследования В ходе работы использованы методы исследования операций, включающие в себя математическое моделирование, численные методы, проведение экспертных оценок

Научная новизна исследования заключается в том, что в ходе работы были решены следующие задачи

1 Предложены математические модели задач одномерного раскроя для существующих методов настилания материалов в подготовительно-раскройном производстве,

2 Разработаны алгоритмы решения разработанных формулировок задач ЦЛП с использованием комбинаторных методов с древовидной структурой вычислений, основанных на эвристических правилах отбора для сокращения количества ветвей,

3 Получены сравнительные характеристики производительности и качества решения задачи методами эвристических алгоритмов и методов решения, основанных на использовании метода ветвей и границ,

4 Разработан программный комплекс для проведения вычислительных экспериментов в условиях реального производства

Положения, выносимые на защиту

1 Формулировки задачи одномерного раскроя подготовительно-

раскройного производства

а Методом параллельного настилания материалов

Ь Методом последовательного настилания материалов

5

с Методом «красных» полотен

2 Алгоритмы решения сформулированных задач на основе разработанных эвристических подходов

3 Программный комплекс для автоматизации операций, выполняемых на подготовительно-раскройном производстве, для получения одномерных оптимальных карт кроя

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

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

Публикации По теме диссертационной работы опубликованы семь печатных работ

Структура и объем диссертационной работы

Данная диссертация состоит из введения, четырех глав и заключения

Работа изложена на 102 страницах машинописного текста В работе содержится 29 рисунков, 13 таблиц Библиографический список включает 79 наименования на 7 страницах

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении к работе излагаются основные аспекты актуальности работы Формулируются цель, научная новизна и практическая ценность работы

В главе I проведен анализ существующей в условиях реального подготовительно-раскройного производства (на примере швейных предприятий) системы формирования оптимальных одномерных карт кроя Описаны основные стадии и методы, использующиеся в рамках подготовительно-раскройного производства В рамках исследуемого технологического процесса выделяют следующие основные стадии

1) классификация материалов по степени пригодности к раскрою

2) подбор материалов в расчет

3) расчет

4) оформление карт кроя

5) настилание материалов в соответствии с полученными картами кроя

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

Так, например, описание стадии 1, 2, 4 содержит требования относительно функциональности разрабатываемого программного комплекса, а стадий 1, 3,

5 - описание основных параметров для построения математической модели и алгоритмов решения

Изложение всех этих аспектов приводится в основных главах диссертационной работы — Глава 3 и 4

Также в данной главе сделан обзор общих характеристик задач ЦП и рассмотрены основные формулировки математических моделей CSP задачи, к которым в настоящее время проявляют наибольший интерес и которые являются базовыми для наибольшего количества работ В частности, приводятся формулировки следующих моделей

1) Канторовича

2) Гилмори-Гомори

3) MCSP (Multi Cutting Stock Problem)

4) PMP (Pattern Minimization Problem)

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

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

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

8

модели), выбор методов и алгоритмов решения, проверка адекватности и корректировка модели, поиск решения на модели, реализация найденного решения на практике

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

1) Определение основных сущностей, которые являются определяющими в работе

2) Представления их основные параметров

3) Выявления основных критериев и методов оценки эффективности результатов

Данный процесс является итерационным, включает в себя следующие этапы

1) Тщательное рассмотрение связей исследуемой операции с другими этапами производственного цикла

2) Исследование подзадач, возникающих при выполнении рассматриваемой операции

3) Исследование критериев, которыми руководствуются при оценке эксперты

Таким образом, путем составления и анализа DFD (Data Flow Diagram)

1 ^

Подоор материалов

Склад

PavM&T заказа

Отдел планирования

Раскрои материалов

Раскроины цех

о (материалах

Информация о 2D

картах кроя

Формирование задания

Расчет задания

Расчетный отдел

Тех ограничения

D1 1D карты кроя

Информация о 1D

Рис 1 DP D тсхнологичекого процесса оптимизации одномерного раскроя

Детали

Номер детали Длина План Описание

Номер 1Р карты кро я Код карты кроя Ограничения Дата формирования Дата расчета Результаты

2D cirri

Höring 2D карты кроя

Код карты кроя

Длина

Ширина

Описание

Материалы

Номрр мат^риапа

Артикул

Карта браков

Полная длина

Ширина

Цена

Описание

Цвет

Дата поступления Расположение на склад?

DETAIL_

DETAIL ID INT(11)

LENGTH DOUBLE

PLAN INT(11)

DESС TEXT

1D CARD

1D CARDIO INTf111

CODE TEXT

CONSTRAIN BLOB

DATE DATE

CALC DATE DATE

RESULT BLOB

2D CARD

2D CARD D INT И1 )

CODE TEXT

LENGTH DOUBLE

WDTH DOUBLE

DE SC TEXT

MATERIAL ID IW111

APTICLE TEXT

DEFECT MAP BLOB

LENGTH DOUBLE

iMDTH DOUBLE

PRICE DOUBLE

COLOR TEXT

DESC TEXT

DATE DATE

LOCATION TEXT

Рис 2 ERD объектов информационной модели задачи

исследуемого технологического процесса составляется ERD (Entity Relation Diagram)

На основе представленной Е1Ш, которая дает наиболее общее формализованное описание объектов исследуемой задачи, формулируются

математические модели задач для следующих методов раскроя (настилания)

1 Параллельный раскрой

2 Последовательный раскрой

3 Раскрой «красных» полотен Для дальнейшего описания алгоритмов и формулировок введем следующие условные обозначения

/V— количество столов в задание раскрой

М— количество рулонов ткани в раскрое

I - индекс стола

J — индекс рулона

п, — план для 1-ого настила

т] — количество пригодных для раскроя отрезов в рулоне к — индекс отреза ву-ом рулоне а, - длина /- ого настила

1'к — длина к-ого отреза ву-ом рулона

Ь/ - полная длинау-ого рулона

— количество единиц /-ого настила, выкраиваемых из отреза к— ого отреза в 7-ом рулоне

¿>1 = Ч~ а1 - остаток от /к- ого отреза после раскроя

к

Параллельный метод раскроя Формулировка задачи

/ = 5Х ~> 1 = . 5ж )

ч- 2>/*

I

I

I = 1,", ] = \т, к =

г' ег

л1к & +

где <5П1П -величина допустимого концевого остатка, ¿>т>х-длина наибольшего нерационального остатка

Так как ввиду ограничений налагаемых видом целевой функции и набором ограничений, невозможно применять наиболее популярные методы Гилмори-Гомори генерации столбцов и методы ЬР релаксаций в работе предлагается метод локальной оптимизации заключающийся в решение последовательности задач следующего вида

Формулировка (1) представляет собой бикретериальную задачу о рюкзаке и является расширением классической (2), так как последняя в рамках решаемой задачи не позволяет выполнить технологические требования, предъявляемые к картам кроя.

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

I

л л< а>-> тах

I

1>, а,<1, х,

I

(1)

I = 1 ,п

/=Т,х' а. -»тах

I

х, я, </, х1

(2)

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

/-У1*, а. <тта,

I

В противном случае, мощность множества рассматриваемых допустимых решений, среди которых производится поиск оптимального решения, может значительно возрасти, что увеличивает трудоемкость алгоритма, а следовательно снижает его эффективность

Формирование очереди

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

• Метод рандомизированного перебора

• Метод поиска худшего

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

13

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

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

1 Выполняется построение множества всех отрезов, для которых

выполняется условие 1]к ~ У,-*, а, <1""™

I

2 В полученном множестве производится поиск отреза с максимальным значением (1°"т -1и )

3 Найденный отрез в очереди задач передвигается на первую позицию Порядок остальных задач в очереди сохраняется

Данную стратегию можно характеризовать как «жадную» - предоставление возможности расчета с полным планом для отреза с худшей оценкой расчета Данный метод может быть модифицирован при помощи введения рандомизации в процесс поиска худшего решения (пункт 2) В этом случае номер отреза, который передвигается на первую позицию в очереди, выбирается из множества отрезов случайным образом

Последовательный метод раскроя

Для задачи последовательного раскроя технологические ограничения на вид карты кроя таковы, что в отличие от параллельного раскроя, отрезы одного рулона не могут рассматриваться как независимые И поэтому в качестве

/= XX ~>т1П>

I

шш I > шах /

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

Если между локальными задачами при решении задачи параллельного раскроя зависимость косвенная, то при решении задачи раскроя рулона добавляется ограничение, которое вносит зависимость решений отрезов в явном виде

шш I > шах 1 Раскрой методом «красных» полотен

Цель раскроя методом «красных» полотен - минимизации остатков, получаемых после целочисленного раскроя Формулировка и алгоритм расчета для решения целочисленной задачи соответствуют одному из алгоритмов описанных выше Что касается формулировки задачи минимизации остатков методом «красных» полотен, то следует выделить основные требования, предъявляемые к расчету

1 Части детали должны выкраиваться из отрезов, принадлежащих одному рулону

2 Длины частей не могут быть меньше определенного фиксированного значения, характерного для каждой детали Первое условие соответствует требованию о разнооттеночности Второе -соответствию суммарной длине детали

Пусть в плане имеется N типов деталей, допускающих раскрой методом «красных» полотен Тогда для каждого остатка в 7-ом рулоне может быть сформулированы следующие ограничения

mJ +* = а, '

к

1 = \fN\k = 1 ,т]

Для того, чтобы окончательно сформулировать ЬР задачу к условиям необходимо добавить критерий оптимальности решения В качестве целевой функции предлагается использовать суммарное количество разложенных деталей

лг" т,

I к

Для решения полученной задачи линейного программирования модели можно применять симплекс-метод

Структура программной реализации алгоритма для решения задачи раскроя для метода «красных» полотен представлена на рис 3

Рис 3 Схема алгоритма нецелочисленного расчета для метода «красных» полотен

1) Предварительная обработка данных

а Оценка того, какие детали (красные полотна) могут быть

раскроены на остатках данного куска Ь Оценка количества красных полотен

2) Формулировка ЬР модели для решения средствами программного пакета ЬР8о1уе

а Формулировка ограничений на расход материала Ь Формулировка ограничений на суммарную длину частей

полотна, раскроенных из разных отрезов с Формулировка целевой функции

3) Конфигурирование модуля решения ЬР задач Задание правил и параметров

а масштабирования Ь выбора/удаления столбца с метода ветвления

4) Формирование результата расчета в формате, необходимом для сохранения решения - полученной карты кроя - в БД

В главе IV обсуждаются аспекты, связанные с разработкой экспериментальной среды, представляющей собой комплекс программного обеспечения для автоматизации технологического процесса расчета

• модуль САМ (Computer Aided Manufacturing) системы

Рис 4 Диаграмма приведенная на рис , демонстрирует общую структуру системы а также взаимосвязи модулей

• модуль управления виртуальным складом

• БД — хранилище данных

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

Центральное место в системе занимает модуль САМ системы, реализующей разработанные алгоритмы

Среди основных достоинств данной архитектуры можно выделить следующие особенности

1) Использование стандарта SQL в качестве средства управления данными позволяет обеспечить полную совместимость при интеграции в информационную среду конечного предприятия 18

2) Использование технологий ХМЦХБЬТ или СОМ, ЛБспр! позволило создать унифицированную отчетно-аналитическую систему

Особенность реализации последней подсистемы особенно выгодно проявляются на стадии оценки адекватности разработанных алгоритмов путем экспертных оценок Было показано, что при помощи разработанной системы возможно гибкое получение отчетно-аналитической документации любого вида

Применение

Описываемая система автоматизации оптимизации одномерной задачи используется в комплексе программных средств компании «Ассоль» Данное средство предназначено для автоматизированного формирования, расчета заданий одномерного раскроя, а также в зависимости от требований предприятия формировать документацию для отделов нормирования, планирования,раскройного цеха

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

1) использование алгоритмов разработанных в рамках работы, приводит к уменьшению расходов материала на 1-2 процента для последовательного метода раскроя, на 2-4 процента для параллельного метода раскроя

2) автоматизация всех стадий технологического процесса расчета куска позволяет

а) эффективно сократить временных затрат на выполнение операций

б) сократить количество трудовых ресурсов, вовлеченных в тех процесс

Кроме того, функциональность разработанного комплекса позволяет повысить оперативность проведения операций нормирования и планирования, на любых предприятиях, где имеется подготовительно-раскройное производство, позволяющее применять модель данных описания материалов, представленную в работе В частности к таким относятся предприятия швейной, мебельной, текстильной промышленности

В заключении подведены итоги диссертационной работы

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В рамках выполненной работы были получены следующие основные результаты

1 Описана актуальность постановки задачи оптимального одномерного раскроя в рамках подготовительно-раскройного производства

2 Приведена математическая формулировка задачи одномерного раскроя подготовительно-раскройного производства легкой промышленности

а Методом параллельного настилания материалов Ь Методом последовательного настилания материалов с Методом «красных» полотен

3 Показана необходимость разработки новых методов решения задачи, отличных от методов изучаемых в теоретических разработках

4 Разработаны алгоритмы решения всех формулировок задач, предложенных в работе

5 Разработан программный комплекс, позволяющий выполнять весь комплекс исследований необходимых для решения поставленной задачи в рамках подготовительно-раскройного производства, а также значительно повышающий оперативность расчетов за счет автоматизации процесса

6 Получены экспериментальные данные, показывающие высокую эффективность применения разработанных алгоритмов

Основные результаты работы опубликованы в работах

1 Д Н Малышев, К Г Андреева Исследование и анализ эффективности методов линейного программирования для решения задачи одномерной упаковки //Современные проблемы фундаментальных и прикладных паук Часть V Труды Х1ЛП научной конференции/Моек физ - тех ип-т -М - Долгопрудный, 2003 -С 97

2 ДН Малышев, К Г Андреева, Л М Павлов Разрабо гка эвристических алгорит мов решения I Г)-С8Р задачи //Современные проблемы фундаментальных и прикладных наук Часть V Труды XI.VII научной конференции /Моек физ - тех ин-т - М - Долгопрудный, 2004 -С 98

3 КГ Андреева, ДII Малышев, С А Никитов, А М Павлов Задача рационального использования сырья в рамках САМ-системы предприятия легкой промышленности //Автоматизация в промышленности Декабрь 2004 С 14-17

4 ДН Малышев, Г Г Андреев Исследование и разработка средств для решения Ш-С8Г' задачи в информационной среде предприятий // Тезисы 5-й международной конференции САЭ/САМ/РОМ Под ред Е И Артамонова / М ИПУ РАН 2005, С 84-85

5 Д Н Малышев, Г Г Андреев Реализация САМ средств для решения одномерной задачи раскроя //Современные проблемы фундаментальных и прикладных наук Часть V Труды XI,VIII научной конференции /Моек физ - тех ин-т - М -Долгопрудный, 2005 - С 117

6 Д Н Малышев Экспериментальная среда для эффективного проведения исследований задачи одномерного раскроя на предприятиях швейной промышленности // Процессы и методы обработки информации Сб СТ / Моек физ-тех ин-т - М,2006 С 193-198

7 ДН Малышев, Г Г Андреев Теория и практика решения задач Ш-С8Р задач на предприятиях легкой промышленности // Процессы и методы обработки информации Сб ст / Моек физ-тех ин-т-М, 2006 С 199-207

Малышев Дмитрий Николаевич

Разработка автоматизированных средств оптимизации одномерного раскроя

Подписано в печать 18 04 07 Формат 60 * 84 Печать офсетная Уел печ л 1 0 Уч -изд л 1 0 Тираж 80 экз Заказ № 377

Государственное образовательное учреждение высшего профессионального образования Московский физико-технический институт (государственный университет) ТШЧ МФТИ

141700, Московская обл, г Долгопрудный Институтский пер , 9

Введение

Глава I. Обзор предметной области

1.1. Описание технологического процесса расчета куска 9 1.1.1. Разбраковка и промер кусков материалов

1.2.1. Расчет кусков

1.2.2. Подготовка к расчету

1.2.3. Расчет

1.2.4. Оформление карты кроя

1.2.5. Настилание

1.2. Специфика задачи одномерного раскроя

1.3. Классические модели 1D-CSP

1.3.1. Формулировка Гил мори, Гомори

1.3.2. Задачи с несколькими типами заготовок

1.3.3. Задача минимизации типов карт кроя

1.4. Алгоритмы

1.4.1. Метод секущих плоскостей

1.4.2. Метод ветвей и границ

1.4.3. Эвристически методы

Глава II. Методология проведения исследований

2.1. Постановка задачи и разработка концептуальной модели

2.2. Формализация задачи

2.3. Выбор метода и алгоритма решения

2.4. Проверка адекватности и корректировка модели

2.5. Поиск решения на модели

2.6. Реализация найденного решения на практике

Глава III. Этапы построения информационной среды и алгоритмов решения задачи 1D-CSP

3.1. Анализ информационной модели производственного цикла

3.2. Разработка алгоритмов 45 3.2.1. Расчет карт кроя для параллельного метода раскроя 47 3.2.2 Расчет карты кроя для последовательного метода раскроя 62 3.2.3. Расчет для метода «красных» полотен

3.3. Тестирование

Глава IV. Практическая реализация

4.1. Общая архитектура

4.2. Хранилище данных

4.3. Модуль управления виртуальным складом

4.4. Модуль оптимального расчета

4.5. Применение

Подготовительно-раскройное производство относится к классу материалоемких производств. Именно поэтому, во многом экономические показатели предприятий, на которых выполняются операции раскроя, напрямую связаны с задачей оптимального расхода материалов [1].

На практике, процесс оптимизации расхода рулонных материалов зависит от оптимальности 1D и 2D карт кроя, составляемых на предприятиях. Кроме того, следует отметить, что данный процесс требует обработки значительных объемов информации (информации о паспортах материалов, требований по оптимальности, организационных особенностей конкретного предприятия и т.п.) - всех тех параметров, которые используются при выполнении расчета. В настоящее же время решение данной задачи основывается на опыте и интуиции квалифицированных работников данной сферы. Выполнение подобной работы без привлечения вычислительных средств, естественно приводит к завышенным затратам временных и материальных ресурсов. Поэтому требуется разработка современных вычислительных средств (программ), позволяющих формировать решения с большей степенью оптимальности и научной обоснованностью. Это особенно актуально в условиях все возрастающей конкуренции на рынке в условиях перехода России к рыночным отношениям.

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

Кроме того, актуальным является и рассмотрение другого аспекта -глобальной системной интеграции производства [2], то есть объединение единой информационной средой связанных между собой технологических операций, что приводит к естественной необходимости проведения системного анализа рассматриваемой сферы деятельности, а именно -подготовительно-раскройного производства.

На большинстве предприятий выполнение операций, входящих в комплекс работ подготовительно-раскройного производства, выполняется без привлечения современных вычислительных средств. Как уже говорилось, это приводит к повышенным временным, а также кадровым затратам, и как следствие, снижению экономических показателей предприятия. Тем не менее, интенсивное развитие информационных технологий в последнее десятилетие позволяет создавать автоматизированные средства для выполнения все большего спектра задач [3-6], которые предъявляют новые требования к организации работы предприятий. В настоящее время все более актуальными становятся вопросы автоматизации производства в полном объеме с целью возможного перехода к созданию на предприятии единой информационной среды, позволяющей гибкое интегрирование современных средств проектирования, производства, управления (Computer Aided Design, Computer Aided Manufacturing, Product Data Managment систем) и т.д., которые позволяют эффективно решать задачи оперативного планирования производства. Поэтому в таких условиях особенно важным становится поиск новых подходов, обеспечивающий целесообразную перестройку системы оптимального расчета карт кроя с учетом жизненных реалий, в частности вопросы создания САМ средств для рассматриваемой в работе задачи одномерного раскроя материала. Уровень развитие вычислительной техники в последние десятилетия позволяет успешно решать поставленные задачи в необходимом для практики объеме, а также качестве [7].

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

Методы исследования. В работе использованы методы исследования операция, включающие в себя математическое моделирование, численные методы, проведение экспертных оценок.

Научная новизна исследования заключается в том, что в ходе работы были решены следующие задачи:

1. Предложены математические модели задач одномерного раскроя для существующих методов настилания материалов в подготовительно-раскройном производстве;

2. Разработаны алгоритмы решения разработанных формулировок задач ЦЛП с использованием комбинаторных методов с древовидной структурой вычислений, основанных на эвристических правилах отбора для сокращения количества ветвей;

3. Получены сравнительные характеристики производительности и качества решения задачи методами комбинаторных алгоритмов и методов решения, основанных на использовании метода ветвей и границ;

4. Разработан программный комплекс для проведения вычислительных экспериментов в условия реального производства.

Положения, выносимые на защиту

1. Формулировки задачи одномерного раскроя подготовительно-раскройного производства: a. Методом параллельного настилания материалов b. Методом последовательного настилания материалов с. Методом «красных» полотен

2. Алгоритмы решения сформулированных задач на основе разработанных эвристических подходов.

3. Программный комплекс для автоматизации операций, выполняемых на подготовительно-раскройном производстве, для получения одномерных оптимальных карт кроя.

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

Структура диссертационной работы

В главе I проведен анализ существующей в условиях реального подготовительно-раскройного производства (на примере швейных предприятий) системы формирования оптимальных одномерных карт кроя. Описаны основные стадии, средства, а также методы, использующиеся в рамках подготовительно-раскройного производства. Сделан обзор алгоритмов, являющихся базовыми для исследований, проводимых в области решения задач одномерного раскроя (ID Cutting Stock Problem).

В главе II описываются основные этапы, при решении задач исследования операций, к которым относится и исследование задачи одномерного раскроя.

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

В главе IV обсуждаются аспекты, связанные с процессами внедрения разработанных алгоритмов, в виде автоматизированных вычислительных средств, интегрируемых в информационную среду конечного предприятия. Также описываются подходы реализации конечных САМ средств, соответствующих современным требованиям, которые предъявляются к высокоуровневым средствам автоматизации. Описано практическое применение и экономическая выгода системы.

В заключении подводятся итоги диссертационной работы.

Заключение

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

1. Процесс является многопоточным, многостадийным

2. Требуется тщательное изучение информационных потоков с целью выявления основных объектов изучения

В результате обзора современных работ, посвященных математическим моделям, а также алгоритмам решения, было установлено:

1. В настоящее время исследование задач раскроя (упаковки) проводится в большей степени на теоретическом уровне.

2. Предлагаемые модели CSP задач описывают весьма ограниченный круг практически интересных задач, что значительно снижает их практическую применимость.

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

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

1. Организация рационального использования материалов в швейной промышленности / И.Н. Град, Е.Г. Авсеев, В.Ф. Петроченко. М.: Легпромбытиздат, 1986. С. 168.

2. Основные направления автоматизации процессов подготовительно-раскройного производства в швейной промышленности / Т.В. Бабар, Т.В. Бурова, В.Н. Соколов // Оборудование для швейной промышленности: Обзорн. Информ. ЦНИИТЭИлегром. М., 1986. Вып. 3. С. 56

3. Автоматизированный настилочно-раскройный комплекс отечественного производства / Ю.А. Балкастов, Б.П. Старков, С.Т. Ильина // Швейная промышленность. 1992. № 2. С. 18-19.

4. Автоматизированная промерочно-браковочная машина / А.С. Железняков, В.А. Александров, К.А. Беличенко, Ю.В. Елтышев // Швейная промышленность. 1991. № 5. С. 19-21.

5. Автоматизированная система регистрации пороков и формирования массива отрезов куска ткани / А.С. Железняков, В.А. Александров, К.А. Беличенко, Ю.В. Елтышев // Швейная промышленность. 1991. № 3. С.15-17.

6. Аскаров Б.Р. Модернизация и расширение САПР Investmark DS // Швейная промышленность. 1995. № 6. С. 24.

7. Armbruster М. A solution procedure for a pattern sequencing problem as part of a one-dimensional cutting stock problem in the steel industry. European Journal of Operational Research 141 (2002) 328-340

8. Любина A.C., Смирнова Г.П. Оперативно-производственное планирование и диспетчеризация // Швейная промышленность. 1987. № 1. С. 21-23.

9. Пдолякин В.И. Автоматизированный комплекс рационального использования материалов на швейном предприятии. М.: Легпромбытиздат, 1987. С. 152.

10. Степин Ю. Д. Современные средства автоматизации процесса подготовки раскроя швейных изделий // Швейная промышленность. 1994. № 2. С. 13-15.

11. Справочник по подготовке и раскрою материалов при производстве одежды / Под ред. И.И. Галынкера. М.: Легкая индустрия, 1980, С. 272.

12. Галынкер И.И. Подготовка и настилание тканей. М.: Легкая индустрия, 1969. С. 346

13. Ветнцель Е.С. Исследование операций: задачи, принципы, методология. Учеб. для вузов. М.: Дрофа. 2004. С. 206.

14. Хэмди А. Таха. Введение в исследование операций. Шестое издание, Вильяме, 2001. С. 912.

15. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1981.

16. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: Наука, 1978.

17. Пападимириу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. С. 512.

18. Ашманов С.А. Линейное программирование. М.: Наука, 1981.

19. Гери М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Наука, 1981.

20. Джон Э. Севидж. Сложность вычислений. М.: Факториал, 1998. С.368.

21. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.

22. Garey M.R., Johnson D.S., Stockmeyer L.J. Some simplified NP-completethproblems // Proc. 6 Annual ACM Symp. on Theory of Computing. Seattle, 1974. P. 47-63.

23. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. Новосибирск:. Наука, 1971. С. 299.

24. Gilmore P. and Gomory R. A linear programming approach to the cutting stock problem: Part 2 // Operations Research. 1963. V.l 1. P. 863-888.

25. Gilmore P.C. and Gomory R.E. A linear programming approach to the cutting-stock problem. // Operations Research. 1961. V.9. P. 849-859.

26. Vanderbeck F., Wolsey A.L. An exact algorithm for IP column generation. Operation Research Letters 19(1996) P. 151-159.

27. Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems. Digital Object Identifier (DOI) 10.1007/s 101079900096. Published online July 19, 1999

28. Belov G. Problems, models and algorithms in one- and two-dimensional cutting. //Dissertation. 2003

29. Scheithauer G., Terno J., Muller A., Belov G. Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm. Dresden University, Institute of Numerical Mathematics, June, 1999

30. Aboudia R. and Barciab P. Determining cutting stock patterns when defects are present. Annals of Operations Research 82(1998) P. 343-354.

31. Holthaus O. Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths. European Journal of Operational Research 141 (2002) P. 295-312.

32. Мухачева Э.А., Мухачева A.C., Белов Г.Н. Методы последовательного уточнения оценок: алгоритм для задачи одномерного раскроя // Информационные технологии. 2000. № 2. С. 11-17.

33. F. Vanderbeck, Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem, Operations Research 48 (2000) 915-926.

34. Umetani S.,Yagiura M.,Ibaraki T. One-dimensional cutting stock problem to minimize the number of different patterns. European Journal of Operational Research 146 (2003) P. 388-402.

35. Belov G. and Weismantel R. A Class of Subpattern Formulations for One-Dimensional Stock Cutting. Dresden University, Institute of Numerical Mathematics, October, 2003

36. Belov G., Scheithauer G. Solving the general one-dimensional cutting stock problem with a cutting plane approach. Dresden University, Institute of Numerical Mathematics, June, 2000

37. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации. // Информационные технологии. 1999. № 1. С. 2-7.

38. Корбут А.А., Сигал И.Х., Финкелыитейн Ю.Ю. Метод ветвей и границ. Обзор теории, алгоритмов, программ и приложений // Math Operation Forsch. Statist. Ser. Optimization. 1977. V. 8. № 2. P. 253-280.

39. Поляк Э. Численные методы оптимизации. М.: Мир, 1974.

40. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.

41. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1985.

42. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наукова думка, 1981.

43. Сигал И.Х. Параметризация и исследование некоторых задач дискретного программирования большой размерности // Известия РАН. Теория и системы управления. 2001. №2. С. 83-92.

44. Схрейвер А. Теория линейного и целочисленного программирования. Т. 2. М.: Мир, 1991.

45. Vance P. Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem. Computational Optimization and Applications, 9(1998) P. 211-228.

46. Valerio J.M. de Carvalho. Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research 86(1999) P. 629-659.

47. Valerio J.M. de Carvalho. A Note on branch-and-price algorithms for the one-dimensional cutting stock problems. Computational Optimization and Applications, 21(2002) P. 339-340.

48. Savelsbergh M. A Branch-and-Price Algorithm for the Generalized Assignment Problem. Georgia Institute of Technology. July 1995

49. Land A.H., Doig A.G. An automatic method of solving discrete programming problems. // Econometrica. V.28(1960). №3. P. 497-520.

50. Boon J.Y., Ken V.R. Establishing the optimality of sequencing heuristics for cutting stock problems. European Journal of Operational Research 84(1995) P. 590-598.

51. Martello S., Toth P., Knapsack Problems: Algorithms and Computer Implementations // Operation Research. V.32(1990)

52. Андреева К.Г., Ннкитов C.A. Оптимизация использования сырья в задаче линейного раскроя // Информационные технологии. 2003. №11.

53. Усманова. А. Вероятностные жадные эвристики для задачи упаковки в контейнеры//Санкт-Петербург: ОПТИМ. 2001. С. 141-146.

54. Кочетов Ю., Уманова А. Вероятностный поиск с запретами для задачи упаковки в контейнеры // XII Байкальская международная конференция. Иркутск. 2001. С. 22-27.

55. Vahrenkamp R. Random search in the one-dimensional cutting stock problem. European Journal of Operational Research 95(1996) P. 191-200.

56. Финкелыдтейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976.

57. Хачатуров В.Р. Аппроксимационно-комбинаторный метод и некоторые его приложения // ЖВМиМФ. 1974. Т.14, № 6. С.1464-1487.

58. Валеева А.Ф., Гареев И.Р., Мухачева Э.А. Задача одномерной упаковки: рандомизированный метод динамического перебора и метод перебора с усечением. // Приложение к «Информационные технологии». 2003. №2.

59. Бешелев С.Д., Гурвич Ф.Г. Математико-статистические методы экспертных оценок. Москва, 1980. С. 262

60. Донецкий государственный университет управления, http://dsum.edu.ua.

61. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / В.Р. Хачатуров и др. М.: Наука, 2000.

62. MySQL: The World's Most Popular Open Source Database, http://www.mysql.org

63. Д.Н. Малышев, Г.Г. Андреев. Теория и практика решения задач 1D-CSP задач на предприятиях легкой промышленности. // Процессы и методы обработки информации: Сб.ст. / Моск.физ.-тех. ин-т. М., 2006. С. 199-207.

64. Корбут А.А. Сигал И.Х., Финкельштейн Ю.Ю. Об эффективности комбинаторных методов в дискретном программировании // Современное состояние теории исследования операций. М.: Наука, 1979. С.283-310.

65. К.Г. Андреева, Д.Н. Малышев, С.А. Никитов, A.M. Павлов. Задача рационального использования сырья в рамках САМ-системы предприятия легкой промышленности. // Автоматизация в промышленности. Декабрь 2004. С. 14-17.

66. Mixed Integer Programming (MIP) solver, http://lpsolve.sourceforge.net.

67. Ветнцель E.C. Теория вероятностей: Учеб. для вузов. М.: Высшая школа. 2001. С. 575.

68. Д.Н. Малышев, Г.Г. Андреев. Исследование и разработка средств для решения 1D-CSP задачи в информационной среде предприятий. // Тезисы 5-й международной конференции CAD/CAM/PDM. Под ред. Е.И. Артомонова. / М.: ИПУ РАН. 2005, С. 84-85.

69. Д.Н. Малышев, Г.Г. Андреев. Реализация САМ средств для решения одномерной задачи раскроя. //Современные проблемы фундаментальных и прикладных наук. Часть V: Труды XLVIII научной конференции /Моск. физ. тех. ин-т. - М. - Долгопрудный, 2005. - С. 117.

70. Д.Н. Малышев. Экспериментальная среда для эффективного проведения исследований задачи одномерного раскроя на предприятиях швейной промышленности. // Процессы и методы обработки информации: Сб.ст. / Моск.физ.-тех. ин-т. -М., 2006. С. 193-198.

71. Zak E.J. Row and column generation technique for a multistage cutting stock problem. Computers & Operations Research 29 (2002) P. 1143-1156.

72. Benchmarks for optimization software, http://plato.la.asu.edu/bench.html

73. XML Extensible Markup Language 1.1, W3C Recommendation 04 February 2004 http ://www.w3 .org/TR/2004/REC-xml 11 -20040204/

74. XML Path Language (XPath) 1.0, W3C Recommendation 16 November 1999 http://www.w3 .org/TR/xpath

75. XSL trasformations (XSLT) 1.0, W3C Recommendation 16 November 1999 http://www.w3 .org/TR/xslt

76. Зачем штриховой код? / Ю.А. Доможиров, В.В. Лемчиков, Т.Т. Рябинская //Швейная промышленность. 1997. №2. С. 15-16.

77. Устройства для маркировки и отметки пороков: Пат. 3436231 Германия.