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

í 5 • г

БАШКИРСКАЯ ГОСУДЛРСТВШЬ'Я УНИВЕРСИТЕТ 1HFHH 40—JIETilfl ОКТЯБРЯ

Ka правах рукописи

УДК 5I9.B54.3 : 65.011.56

СОЛОМЕЩ ЮЛИ ИЗРАЛЛШМ

ЗАДЛЧ'1 ЛШГейНиГО UFJI ОЧЛС.Ч Ь.Ш ЮГ О РАСКРОЯ МАТЕРИАЛА

случайной дллнк

05.13.16 - Приугнпчие рипислятелыюй техники, мятсмт

w.Y. (.'етрдпп и матоуятиупскот,о моделирования п ня'лтн): исследованиях

05.13.07 - Лптгматияяпуя тпхнологичпских проиессоп и проня-г одет г»

Азюрсфорат дкссоргати ка соискание учено Я степени кп1!Г,идята '^пико-млгематичйс.кях imvit

Ща 19УЗ

. Работа выполнена на кафедре вычислительной математики и кибернетики Уфимского ордена Ленина авиационного института.

Научный руководитель - доктор технических наук, професс'р Мухачева Э.А.

Официальное оппоненты - доктор физико-математических I тук ( профессор Залгаллер В.А. - доктор технических наук, профессор Ильясов Б.Г.

Ведущая организация - инстиг т математики и . еханики УрО ЛН СССР (г.Свердловск)

защита состоится '

(? •• О'/ 1990 г. в час»

на заседании специализированного совета К.064.13.03 при Башкирском государственном университете им. 40-летия Октября по адресу: 4Ь0074, г. Уфа, Фрунзе 32.

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

Автореферат разослан " (Р " /"'-у" ■ 1ЭЭ9 г.

Отзывы на автореферат, заверенные гербовой печатью, просим высылать го указанному адресу на имя ученого секретаря специализированного совета К.064.13.03 Мороэкина Н.Д.

Учений секретарь специализированного совета

К.064.13.03 — Морозкин Н.Д.

.! - э -

-¡г. ,, ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Классическая задача линейного раскроя заклпчается в следующем.

Лмеются полосы длиной Я) . Требуется порезать комплект из

/Ь заготовок длиной С11.....а^ . От каад 1 полосы мокн- отре -

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

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

Саланн <0Ч0 и набор Л — {а,.....С1%) положительных чи -

сел. .Чийт:' •••аншкиь по по числу подмножеств разииение множества V- | / ,..., п } ио ндтерсссктииосл полииожоста ..., Л'н (Л'-П.У: :■■ Ф . I I • //л'; - л') такое,что У,а- ^ .V V

К настоящему времени имеется значительное число публикаций, обсуждающих вопроси рационального раскроя материала, длина которого известна заранее ("задачи детерминированного раскроя). Результаты исследований, проводимых В.А. Залгаллером, И.В. Романовским , Э.А. Мухачевой, Ю.Г. Стояном, Л.Б. Беляковой, А.И. Липовенким нашли непосредственную практическую реализацию. Однако поставка материалов определенной длины связана с выполнением дополнительных работ и увеличением отходов на заводе-поставщике. Умение рационально планировать раскрой материала случайных длин позволяет отказаться от заказа мерного материала, тем самим уменьшив общие рас ходи. Возникающие при этом задачи оптимизации раскроя являются мал изученными, а ситуации раскроя материала случайной длины в условиях о, ¡-ничного производства (будем назывоть соответствующие задачи зада -чами целочисленного стохастического раскроя ) практически не рас -сматривались.

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

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

разработка программного обеспечения линейного нелочнелепного стохастического раскроя;

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

систему раскроя линейного материала. •

Исследования велись по программе "Авиационная технология" Минвуза Р06СР в рамках хоздоговорных работ ( гоо.регистрация № 01630077229)!

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

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

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

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

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

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

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

Практическая ценность диссертационной работы заключается в следующем:

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

луженных оптимизационных алгоритмах;

- поедложен новый способ раскрои немерного полосового материала (авторское сгид. № 1^66117 ), позволяющий снизить .расход материала и автоматизировать процесс раскроя;

- разработано гибкое программное обеспечение задач линейного цс-лочислгчного раскроя, которое может быть использовано в САПР раскр^ч.'

Апробация работы. Результаты диссертационной работы били до -ложени на Всесоюзных семинара^ и конференциях, в том числе на Всесоюзной конференции "Методы математического программирования", овердловск, 1937 г.; Всесоюзной конференции " Математическое обеспечение рационального раскроя в системах автоматизированного проектирования" , Уфа, 1987 г. ;Ц1 Всесоюзной вколе "Дискретная опти -иизация и компьютеры", Москва,1967 г.; Всесоюзной школи^семица^е 11 Моделирование и оптимизация сложных систем Баку, 1988 г.; отраслевой конференции "Информатика комплексно-автоматизированной подготовки производства", Иркутск, 1989 г.

Публикации. По rené диссертации опубликовано 10 научных статей.

Объем и структура работы. Основное содержание работы изложено на 103 страницах машинописного текета и состоит из введения, .четырех глав, заключения. Диссертация содержит библиографию 70 Наименований , 2 приложения, 6 таблиц, Э рисунка.

Основное содержание работы.

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

ния; проводится анализ технологически* ситуаций в условиях сто -хаотического раекрол.

Первые теоретические работы в области оптимального раскроя были проведены В. Л, Канторовичем и В.Л. Залгаллером. В них рас -скатривалась задача детерминированного раскрп, с^прм.улировянная как задача цзлочисленного программирования. Основу алгоритмов в таких случаях составляют всевозможные приемы улучшенного перебора вариантов.

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

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

л

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

;! зависимости от принимаемого критерия оптимизации рассмат -пиВ'»е|.'ыс в работе задачи долится на две группы. Приведем предва -«ителыше постановки тих задач.

Первая группа.¿лч получения комплекта заготовок заданных размеров "¡пользуется но гиен случайной длины с известным законом распределения, Чообходимо ¡«скроить полосы так, чтобы расход материал (. суммарная длина полог.)на комплект в среднем бил мини -малмп-'ч.

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

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

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

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

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

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

будем называть отходом, независимо от того, является ли она деловым остатком или нет.)

Пти соображения приводят к следуюцей предварительной поста -новке.

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

Рассматриваются два случая технологических ограничений.

Б первом - нельзя отказаться от полосы, длина которой больше некоторой заданной, если от нее может .быть отрезана хотя бы

одна заготовка.. ...

»

Во втором - возможен отказ от любой полосы.

Для задач этой группы î качестве информации о длине р.п. принимается точная длина, измеряемая после поступления полосы на резку.

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

Об оптимальном раскрое имеет смысл говорить лишь в рамках определенной структуры процесса раскроя. Для задач по критерию рас -ходуемого материала (критерий I) рассматривается следующая структура процесса раскроя (СПР1), состоящая из идентичных шагов. Ma каждом шаге выполняются следующие действия;

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

' - заготовка отрезается, независимо от того, удастся ли ее отрезать от р.п. или потребуется привлечение новой.

Теперь общая формулировка задач по критерию I следу мая. Задача СР I. Из полос случайной длины Х.^с1тпх)

требуется получить комплект заготовок длин О.^ ( (пасс О; < , среди которых могут быть и одинаковые. Извес-

I/V

•ген закон распределения /Т^ длины полосы. При СПИ и задан -ной информации I о длине р.п. найти алгоритм раскроя, при кото -ром математическое ожидание Г,..о.) числа расходуемых на комплект полос минимально.

Введем некоторые обозначения.

Пусть Кд — { Л } - множество номеров требуемых

заротовок; доопределение I. Комбинацией заготовок из набора К, будем называть набор заготовок о номерами, входящими в К ,

Определение 2, Под длиной комбинации заготовок понимается сумма длин заготовок, входящих в ату комбинацию.

, Пусть ¿"= (4 , ^/г-- > ^* список длш, где ^ = й , а длины ^¿1 ^ ~ у< совпадают с длинами всевозможных

комбинаций заготовок из набора К , не превосходящих С^тасс •

Пусть б=(44 =(? - список длин О,- , ¿— Д п заготовок, расположенных в порядке строгого .возрастания.

Определение 3. Приведенной длиной р.п. относительно некото -рога списка назовем наибольшую из длин этого списка, не превосходящую действительную длину р.п.

Уточним оодтржание информации I о длине р.п. в вариантах | 1-3 гл. I .

В первом варианте известна длина 6 р.п., приведенная от-

носите-, ыю списка Ь , т.е. /•'= Се С.

Во втором - суммарная длина (1 заготовок, уже отрезанных от р.п., т.е. 1:~с1, (¿£А.

В третьем - заданы а и приведенная относительно списка В длина 6 р.п., т.е. I :~(с[, 6), с1еС , о€В.

В зависимости от принимаемого варианта информации о длин" р.п. получаем модификации общей задачи СГ (.1 - СР Т.З.

В слумое оптимизации по критерию стоимости (критерий 2) структура процесса раскроя ССПР 2) состоит из идентичных шагов, на каждом из которых выполняются следующие действия:

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

по некоторому правилу выбора определяется номер о,:-'р«д-ной отрезаемой заготовки от текущего набора; заготовка отрезается. Теперь общая формулировка задач по критерия 2 следующая. ^Задача >' И полю случайной длины X АГ ^^^

требуется ю.лучить комплект заготовок заданных длин й^ г I- 1 и .1-Сч?" . Известен закон распределения длины по-

лосы у -- /,.-.77 , где р- - вероятности поступления

полосы длиной <1: . Садани 3-(с1:) , у — Лл? - стоимость новой полосы лл:ноа а- и #£) - стоимость сдапаемай п отход полосы

г ^

длины О . Ир;; заданной '/К' г' найти алгоритм раскроя, при кото -ром м.о. г-то 1мости комплекта будят минимальным.

г) паш'с 1мос'П! )Т шрлапта технологических ограничений (гл. I) повучапм уоллфчкиш:« яйчсИ задачи СР Р.1 и СР 2.2.

•^агччл^:'^^. у- лопия/. задачи С1* ? задала величина с1кр ,•

тСя Д,- < с! .

¿=/7л: '

Задача СР 2.2.В условиях задачи СР 2 не задана.

При исследовании задачи СР 2.2 возникла необходимость ре -шить следующую задачу об отказе от новой полосы, относящуюся к классу задач об оптимальной остановке.

Радача об отказе. Для получения комплекта К заготовок поступают полосы случайной длины. Известна вероятность р- (¿={,пг) поступления полосы длиной . Заданы стоимости посту-

пающих полос и стоимости возможных остатков. При поступлении очередной полосы, например, ¿' - ой возможны два варианта:

- использовать полосу дли получения комплекта К , при птом м.о. стоимости комплекта известно и равно величине ;

- отказаться от полосы и вернуться в исходную ситуацию, заплатив за отказ известную сумму С- •

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

Следующие леммы и теорема доказывают существование опта -мальной стратегии и позволяют .^формулировать ео.

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

Лемма I. Значение М удовлетворяет уравнению

Л = £ Р; ■ па (4 5 ¿с+Сс). ([)

т

Лемма 2. Если Л Р;'С->0 , то М - -.-димстренное решение уравнения (1).

Для заданного Л>0 определяется пороговая стратегия ^ следующим образом : отказ от использования новых полос продол -жается до тех пор, пока при появлении очередной £-эй полови не окажется, что Л + С^ •

Лемма 3. При любом Л> тСа^^^С;) | ¿^/^Тп, | математическое ожидание фактических затрат при лрименеиии стратегии равно

и®-+ Мпя%

М^т(Л) - м.о. затрат на произвольном шаге на получение комплекта К , если согласно появившаяся на этом шаге полоса бу -дет использована.

М (Л)- м.о. платы на произвольном шаге, если согласно стратегии происходит отказ от использования полосы.

л

Р-.Т1Р: , £ = Рс .

** С-с^ ■ С!

1С II

т.

Теорема. При Д1! Рс 'С^О пороговая стратегия ^ , где М - единственный корень уравнения СГ), является оптимальной для рассматриваемой задачи в классе стратегий, обладающих конечным математическим ожиданием затрат..

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

В рассматриваемых в главе 2 задачах алгоритм раскроя определяется заданием информации о длине полосы, структурой процесса раскроя и алгоритмом выбора покера очередной отрезаемой за -готовки и отказа от р.п. Первые две составлявшие алгоритма раскроя, а в задаче СР1 и алгоритм отказа заданы.* Поэтому нахойе-

- IH -

ние'оптимизационного алгоритма раскроя равносильно нахождению оптимизационного алгоритма выбора в задачах типа CPI и нахождению оптимизационного алгоритма выбора и отказа в задачах типа GP2.

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

Для э-чач CPI. /,.2,3)

М (I,К) - и.о. числа необходимых полос в ситуации (1,к) , если раскрой ведется в условиях задачи CPI. q, /,2,3) по опти -

мизационному алгоритму.

- и.о. стоимости набора К. при оптимизационном алгорит-

Для задач СР 2. (± = 1,2).

м.о. стоимости набора К при длине 5 рабочей полосу и оптимизационном алгоритме раскроя.

не раскроя и условии, что от р.п. длины<? будет отрезана хотя бы одна заготовка из набора К .

- м.о. стоимости набора К при оптимизационном алго -ритме раскроя в тлучае, когда р.п. длиной 6 считается отходом.

Таблица раскроя строится с помощью аналогичной таблицы, в клетке (1,к) которой указывается значение

Заполнение такой таблицы ведется по рекуррентным соотношениям.

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

- после поступления р.п. становится известной информация о

ней;

- на основании отой информации Г и наборе еще не отрезанных заготовок К по клетке (1,К) таблицы определяют действия над полосой и исполняют их.

Построенные для каждой из задач рекуррентные соотношения имеют следующий вид. Задача CP I.I.

Вместо М^(1,К) будем писать Mj(¿,K) . , где 6éL,

При С> mía (a¿ ¡¿ел}

М/С,К) = mía { м 1(¿-a¿ , f\\ {¿ } )| Се К }. При mea {a¿ \.¿e к}

м/с,к) - £ [r/r¿¿u)-ff4)) ■ M,(£¿,*)lt

где C¿€ L , a í* такое, что >

Л* >d ■

+ í т-Л •

Кроме того, следует считать M^C^íS) - ■( д^я ¿£L. Задача CP 1.2.

Вместо М (Т,к) будем писать M¿(c/,K),

Считаем M(d i 0) = ^ , de L .

Для любой клетки (d,K) справедливо следующее соотношение

Alz(d,K) = mía {(S-Fd(a¿))< M/d+a¿, к\ (¿ }) +

где ^(•х;- --^ - _ функция распределения длины полосы, если от нее удалось отрезать длину с1 . Задача СР 1.3.

Ьыесто Л^ (I, К) будем писать А)' (с1, к) , где

¿ее, 6$В.

Считаем Мл(с1, 0)= /.

вычисляется следуощим образом. Если 5> тс/ь (¿¿I \1е К } , то

Мз(с1М - тс«. {г [Ъ^/^-^С^аЛ < . Если

6 - /7Ы>1 {я; ) ¿е /с

}

, то

Здесь

Я,*/*' =

г "V/

функция распределения длину полосы, если после отрезания д^й^Н ре приведенная относительно списка В длина равна ^ , Задача СР 2.1.

\ьек ]

При

ггил

О

/71 _

/V¿,к] = £ ГА 'mc, (¿j,K) -с(П. j=/ / » »

При mía (a¿ I ¿ел }, ¿<clK MC4(C,fQ= nñi {mc™U,k), A7cJa(¿,')j t

где

л/c/tf *) = { Mc/¿-a¿,/<\ {¿¡)l ¿ел ■■a¿<£ Jf

a

MC = ¿ [p; -(fic,(dj,K)* J(dfÛ-c(C).

* j=i / / J

При ¿> max [dKp., rnin.^a¿ |í'e/r}j

min IMC,(¿~Q¿,k\ (l } I Le к a¿ « ¿j.

Задача CP 2.2.

При men fe I i€ К J

MCtU, К) = МСг (O, K)-C(í). (2)

При "u/i fe j ¿e л J

Л7С(£л) = rain I МС^'Л(С,к) ; /Vc/^/Oj f

где

MC™(e,K) - win. | vcjC-ä¿, k\{l } I i е. к ;aL*s í j f X í'í.M-- MCt,0.i\)-C(£h

[l¡ ;i ¡iwM-.T^.r< следует считать )m ~C(£). ée/,«?.

Входящие в соотношения (2), (3) величины MC^fO, Л) — и.о. стоимости набора К при нулевой длине рабочей полпсы - вычисляются путем реиения задачи об отказе от новой полосы С глава 2).

На основе полученных теоретических результатов предложен новый способ раскроя немерного полосового материала в условиях единичного и мелкосерийного производства, позволяющий полностью автоматизировать процесс раскроя. Основная идея заключается в следую -дем. Предварительно по рекуррентным соотношениям производится расЧет таблицы на достаточно мощной оВМ. Полученную таблицу вводят в микро-ЭВМ, управляющую режущим устройством, ./'алее, с рабочего места поступает информация о длине р.п. 11а основании :>той информации ЭВМ по указанному алгоритму определяет номер очередной отрезаемой заготовки. Сообщение о номере подастся на режущее устройство для исполнения.

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

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

Без ограничения общности можно считать, что требуемый комп -лект К состоит из К; заготовок длины Q; , !ji , J.-J'íh

u t- ' i j

при L^j . Комплект, состоящий из ('' V^ заготовок ¿ - го вида, (l~ -f,n) будем называть подкомплексом.

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

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

ф

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

Л

число столбцов не должно превосходить величину о — "лт,Гк 1 Здесь п. - объем оперативной памяти, а \Г(Кд,итах) - Фучк -ция, заданная алгоритмически и определяющая число строк в таблице раскроя по набору К0 и длине Вычисление зтой функции осуществляется на ЭВМ по специальна разработанной программе при . незначительных затратах машинных ресурсов. Поэтому интерес представляют субоптиыальные алгоритмы, дающие хорошее решение за приемлемое время. Предложенные в работе приближенные алгоритмы базируются на том, "то основная задача,• имеющая большую размер -ность, разбивается на подзадачи меньшей размерности, для решения которых используются оптимизационные алгоритш.

Применение каждого из них обусловлено соотношением величин $ и <?Я'. Если 2'Ъ< 3 , то может быть использован метод подкомп-л екта. Он заключается в том, что из комплекта специальным об -г. разом выделяется подкомплект о Для • Для не-

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

Если 2/1>3 И £>.п >?* с тал а,-) , то можно при-

СР■

менить метод кроя остатков. Здесь Ь - средняя длина поступав -щих полос . При атом основной комплект разбивается на два под -комплекта, условно названных "большими" и " палыми" заготовками. Для последнего по оптимизационному алгоритму строится таблица

{¡51с кроя. Раскрой осуществляется следующим образом. От новой р.п. отрезаются "большие" заготовки по алгоритму "первый подходя -щий о упорядочиванием" до тех пор, пока длина полосы не .окажется меньше некоторой заданной. Из оставшейся части полосы получают "малые" заготовки согласно алгоритму, заданному таблицей раскроя.

Ясли 2.п~>$ , можно использовать метод группировок. Идея его заключается в том, что комплект А разбивается на подкомп -лекты так, что I) суммарное члсло столбцов в таблицах оптимального раскроя для этих подкомплвктов не превосходит Я ; 2) заготовки предыдущего подкомплекта длиннее заготовок следующего,

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

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

Задача МР.

Пусть задан вектор К-(К,, ■ -■■ , Кп) , ле// , >0, С~ Л л- а «У^ , Произвольной последовательности

целых неотрицательных чисел Сд-0.<[, < < С^** П

сопоставим совокупность векторов Р4 , ■■ ■ ,

у/) Требуется найти минимальную по числу ¡элементов

последовательность чисел ¿е , 1/ ¿п , такую, что

Т Л(, ¿¡) где функция Г)(Сф = Ки, ■ '-'Кг-^

определена на множестве ¿М с-* ^ ^ п..

Ута задача решена в работе с помощью приемов динамического программирования.

Если определить функцию ) как наибольшее значение

^ в последовательностях, удовлетворяющих условии ¿^ и ввести функцию - та Л {у ¡¿> ¿, ПИ^)^ ^

то функциональные уравнения Веллмана можно записать так:

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

с я строки, соответствующие лишь тем значениям .5 , где происходит скачок функции ).

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

На основе полученных в работе теоретических результатов создан комплекс программ "Стохастический раскрой". Состоит из Э'> независимых модулей и представляет собой открытую систему. Но --дульное построение комплекса дает возможность совершенствовать и модифицировать как сами программы, ток и алгоритм!! решения задач раскроя, /лп опенки алгоритмов решения задач линейного стохасти -ческог") раскроя проведен вычислительный оксперимст, моделирующий процесс ш'тг.члтизированноп) раскроя. Сравнение точных алгоритмов о "/¡орл.'м п >л:<1>лч;ци1 с упорядочиванием" (141/) дало увеличение ко:«!ф.пч(.-!1та ¡•сиолькочмии 1атср.1п.»п в пределах от до I?.:.

Вычислительный эксперимент для сравнения приближенного метода подкомплекта и алгоритма ППУ дал увеличение коэффициента использования материала в среднем на 5,5<?. Для оптимизационных алго -ритмов была проведена оценка гипотез« о равенстве расчетного и оксперименталыюго значения м.о. критерия оптимизации. Статистический анализ показал, что разница между ними незначима.

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

1. Формализованы и исследованы целочисленные задачи оптимизации раскроя материала случайной длины по критерию расходуемого материала и критерию стоимости, учитывающие ряд технологических ограничений, возникающих в практическом процессе раскроя.

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

3. Для поставленных в работе задач стохастического раскроя (все они относятся к классу МР - трудных в силыюм с.'шсле ) на основе оптимизационных алгоритмов с использованием принципа дском-

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

Ц. На базе предложенных алгоритмов разработан Ш "С'тохас -тический раскрой" для решения задач раскроя немерного материала в условиях единичного производства. Ьнчпслшелмшй эксперимент по пакету программ показал увеличение коэффициента использова -ния материала в продолах от 'Гй до 12'! по сравнении с алгоритмом " первый подходящий с упорядочиванием" - лучшим ип [«пев разработанных и применимых к классу задач стохастического раскроя.

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

6. В проиессв исследования общей проблемы поставлены и решены следующие вспомогательные задачи, представляющие самостоятельный интерес:

1) задача об отказе от новой полосы, дающая новое приложение задачам об оптимальной остановке и возникающая при оптимизации раскроя по критерию стоимости;

2) задача о минимальном разбиении комплекта заготовок, относящаяся к классу задач о разбиении множеств и возникающая при использовании метода группировок; . •

3) задача о генерации комбинаций и частичном упорядочивании множества комбинаций, относящаяся к классу задач о нумерации и

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

7. Результаты работы используются при создании системы автоматизированного раскроя текстильного материала при производстве офсетных пластин на Уфимском заводе резиново-технических изделий. Ожидаемый экономический эффект 80 тыс.руб. в год.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Мухачева Э.А., Соломещ Н. ¡1. Задача стохастического линейного раскроя // Оптимизация. 1985. Вып. 36(53).- С. 49-55.

2. Мухачева Э.А., Соломещ H.H. Математическое обеспечение линей-'ного раскроя,в условиях неопределенности//Методы математичес- -кого программирования и программное обеспечение: Тез.докл. научной конференции. Свердловск, 1987. С, 8'|-85,

3. Мухачева Э.А., Соломещ H.H. Рекуррентная процедура оптимиза ~

« ции стохастического раскроя//Дискретная оптимизация и компьютеры : Тез. докл. Ш Всесоюзной школы. Москва, 1987.С.196-197.

4, Мухачева O.A., Соломещ H.A., Соломещ Н.И. Оптимизация-линей -ного стохастического раскроя по критерию стоимости//0птичиза-ция. 1988. Вып. Vt 61 . - С. 56-63.

5, Соломещ Н.И. Оптимизация раскроя линейного материала случай -Hl.; длины// Математическое обеспечение рационального раскроя в системах автоматизированного проектирования. Уфа, 1988. С. 33-38.

6, Соломещ Н.И. Об оптимальной остановке в задаче раскроя//Лрог-раммн^методические и программно-технические комплексы САПР

и ACTtin : Тез. докл. Ижевск. 1У88. С. 95-96.

7, Григорчук Т.Н., Соломещ Н.И. Об оптимизации раскроя рулонного материала с дефектными точками //Программно-методичаские и программно-технические комплексы САПР и АСТПП: Тездокл,Ижевск, 1988. о. 95.

8, Григорчук Т.И., Соломещ Н.И, 0 приближенном подходе к решению одномерной задачи упаковки в контейнеры случайной емкости //Применение ЭВМ в решении научно-технических и народнохозяйственных задач : Тез. докл. Уфа, 1989. С. 68.

9, Ратн'ер М.Ф., Соломещ Н.И. О реализации стохастического линейного раскроя на оборудовании с ЧПУ//Математическое обеспечение рационального раскроя э системах автоматизированного проектирования : Материалы Всесоюзной конференции. Уфа, Г988 , С,48--50.

10,Григорчук Т,И,, Соломен Н.И. Автоматизированное управление . раскроем рулона с обходом дефектных точек//Информатика комплексно—автоматизированной подготовки производства: Тез.докл,

Иркутск, 1989'. С.30-32.