Модели и методы оптимизации упаковки N-мерных параллелепипедов тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Картак, Вадим Михайлович

• Картак, Вадим Михайлович
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Картак, Вадим Михайлович

Оглавление

Введение

Глава 1. Классификация задач раскроя-упаковки

Глава 2. Задача линейного целочисленного раскроя (N=1)

2.1 Постановка задачи линейного раскроя

2.2 Алгоритм генерации прутков с возвратом (ГПВ) (переборный алгоритм)

2.3 Эквивалентность планов раскроя

2.4 Доминантность

2.5 Оптимизация смеси

2.6 Коэффициент разветвленности

2.7 Свойства задачи линейного целочисленного раскроя

2.8 Использование на практике свойств Ш11Р

2.9 Группировка

2.10 Эксперимент для одномерной упаковки. 45 Глава 3. Задача № мерной прямоугольной упаковки (N>2)

3.1 Математическая модель Ы-мерной прямоугольной упаковки

3.2 Задача заполнения

3.3 Алгоритм связанных заполнений (СЗ). 59 Глава 4. Задача упаковки прямоугольников в полубесконечную полосу

4.1 Математическая модель

4.2 Схема СЗ алгоритма для N=2

4.3 Эксперимент для двумерной упаковки. 64 Заключение. 66 Литература. 68 Приложение 1. 75 Приложение 2

Введение диссертации (часть автореферата) на тему «Модели и методы оптимизации упаковки N-мерных параллелепипедов»

Введение

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

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

Диссертационная работа посвящена построениям точных алгоритмов решения задач раскроя-упаковки. Методы, нацеленные на получение оптимального решения этой проблемы, до сих пор остаются мало изученными. Причиной этого является КР- полнота рассматриваемой задачи в сильном смысле (задача линейного целочисленного раскроя в частном случае дает задачу 3-РАЗБИЕНИЕ), так что мало надежды на отыскание

даже псевдополиномиального точного алгоритма решения этой задачи. На данный момент теория ЫР задач говорит, что для нахождения оптимального решения рассматриваемых задач существует только один путь - полный перебор всех допустимых вариантов и выбор из них оптимального [37].

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

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

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

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

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

■ разработана математическая модель задач упаковки 1М-мерных прямоугольных объектов (N>2) в полубесконечную область.

■ разработан метод решения задач упаковки Ы-мерных прямоугольных объектов.

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

прямоугольников в полубесконечную полосу. Это и составляет практическую значимость работы.

Результаты работы и отдельные её разделы докладывались и обсуждались: на 10-й Байкальской школе-семинаре «Методы оптимизации и их приложения» (1995, г. Иркутск), на семинаре в Институте вычислительной математики Дрезденского технического университета (1996г. г. Дрезден ФРГ), на международной конференции по исследованию операций (1998, г. Новосибирск),на семинарах кафедры Вычислительной математики и кибернетики Уфимского авиационного технического университета.

В первой главе диссертации изложена общая классификация задач раскроя-упаковки. Приводится краткий обзор методов решения задачи раскроя- упаковки (11-11).

В основу классификации моделей положены известные работы Л.В. Канторовича и В.А. Залгаллера, Э.А. Мухачевой , И. Терно и Дикхофа .

С учетом. приведенной классификации задачи, рассматриваемые в диссертационной работе, могут быть представлены как 1/У/1/М. [5]

Среди работ, посвященных линейному раскрою, выделяется статья Г. Вешера [33], в котором приводятся результаты вычислительных экспериментов для ряда алгоритмов с указаниям для них наиболее трудных классов задач.

Вторая глава посвящена задаче линейного целочисленного раскроя. Для её решения разработан точный (переборный) алгоритм. Приводится предложенная А. Кацевым схема генерации допустимых планов. На базе этой схемы рассмотрены методы построения дополнительных отсечений неперспективных ветвей. Показан механизм совместного использования точного алгоритма и симплекс метода для решения задач с большой

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

Задача линейного целочисленного раскроя состоит в следующем:

Одномерные материальные предметы одинаковой длины Ь (прутки) должны быть разделены на меньшие части (заготовки) требуемых длин /1,/2,...,/т, так чтобы удовлетворить заказанные потребности Ь1,Ь2,...,Ьт. При этом требуется минимизировать общее количество используемого материала.

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

а11 а21 %1 1 ак1

а12 а22 а32 1 ак2

Е1п а2п а3п 1 акш

а,, - количество г-о вида заготовок в]-м раскрое прутка ; К - количество прутков в раскрое;

Как уже было отмечено, данная задача является №>- полной в трудном смысле. Поэтому для её решения приемлем только один подход- полный перебор всех допустимых вариантов и выбор из них оптимального.

Идея базовой схемы , предложенной А.Кацевым [47], состоит в следующем : методом полного перебора ищется такое размещение заготовок в прутках, чтобы суммарный остаток не превосходил допустимого резерва. Если это удаётся, то рассчитывается новое значение допустимого резерва затем перебор продолжается. В случае когда достигнута нижняя граница или перебор не дал результата, работа

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

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

просматриваемых вариантов, и при этом не потерять оптимум.

1 2 План раскроя А считается эквивалентным плану А в том случае, если

они состоят из одних и тех же карт раскроя и отличаются только порядком

их расположения.

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

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

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

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

где:

к- количество карт раскроя, входящих в план;

т- общее количество заготовок.

т/к - среднее количество заготовок, входящих в одну карту раскроя.

Определим еще одно свойство, которым обладает задача ЛЦР: Назовем Р-задачей такую задачу линейного целочисленного раскроя, где комплектность каждой заготовки равна 1.

Очевидно, что любая классическая задача, где каждой заготовке 4 соответствует некоторая комплектность Ьк > легко преобразуется в Р-задачу путем включения заготовки длины 1к- Ък раз.

Пусть даны две задачи Р 1={Ь,1п,т1) и ¥г=(Щ2рт2), ге 1..ть]е 1..т2 где Ь- длина'прутка;

т/, т2- количество заготовок в задачах Р1, Р2; 1Н,12] - длины заготовок в задачах Р1,Р2.

Задача Р1 доминирует над Р2, если каждой заготовке из Р1 можно сопоставить заготовку из Р2, чтобы для каждой из получившихся пар выполнялось условие 1ц <12] для всех ге 1..т\ и некоторых{1,2, ... , т2} при этом каждой заготовке из Р2 сопоставляется не более чем одна из Р1.

Пусть Х*(Р) - количество прутков в оптимальном целочисленном решении задачи Р. Тогда очевидным является утверждение : Если задача Р1={Ь,1ц,т/) доминирует над У2-(Ь,12],т2), то выполняется неравенство Ъ*{Р1)<Х*(Р2).

Данное свойство означает, что решив некоторую задачу Р1 можно выделить множество задач оптимальные решения которых «не лучше» чем уР1.

Базируясь на этом свойстве задачи ЛЦР, можно построить дополнительное отсечение. Идея его заключается в том , что бы на каждом

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

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

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

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

Известно, что задача линейного целочисленного раскроя (ЛЦР) является задачей линейного целочисленного программирования (ЛЦП) с неявно заданной матрицей ограничений.

Обозначим через: Е = (1,т,1,Ь ) задачу ЛЦР, где Ь- длина прутка, т-количество типов заготовок, 1=(11,12--, 11Г) и Ь=(Ь1,Ь2>... Ьгп) - длины и комплектности заготовок соответственно.

Тогда отвечающая ей задача ЛЦП можно сформулировать следующим образом :

Требуется найти совокупность раскроев г\-> г2^, их количество п и вектор интенсивностей их применения х = (х1,х2,...,хп) удовлетворяющих условиям:

1°. > О, целые у = 1 ,...,п;

п

п

3° ,г(х) = . достигает минимума.

7 = 1 7

Где, известны всевозможные способы раскроя прутка (карты раскроя) a(rj) = {aj\->aj2>-~>ajm) J= каждый из которых представляет собой

т — мерный вектор и - количество заготовок вида i, вырезаемых в j -м способе раскроя.

Данную задачу можно представить как частный случай модели стандартной линейной целочисленной минимизации:

z = cTXmitl^ÄX = b,x > 0, целые,

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

z = сТх —> min, Ax>b,x> 0.

Обозначим :

z (Е) - оптимальное значение целочисленной задачи;

zc(E)~ оптимальное значение соответствующей задачи линейного программирования (ЛП).

Говорят, что задача линейного целочисленного раскроя Е обладает свойством округления до целого вверх (IRUP) [23], если

z\E) = [zc(E)1

Для проверки свойств IRUP некоторой задачи ЛЦР эффективно построение так называемой остаточной задачи. Имеем некоторую задачу раскроя E = (m,L,l,b) и пусть Xе- интенсивности планов раскроев, определяемые "из оптимального решения соответствующей задачи ЛП:

z = eTxc —> min,Ах = b,xc > 0.

Тогда задача Е = (l, т, 1,Ь-а[хс J) является остаточной к е.

И. Терно [26] было показано, что для выполнимости свойства IR "U Р некоторой задачи Е, достаточно доказать IR U Р для соответствующего

остаточного случая Е.

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

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

1. Симплекс- алгоритмом решается соответствующая ей задача ЛП

z = етх -» min, Ах = b, х > 0.

2. Исходя из решения задачи ЛП формируется задача остатка

E = (m,l,L,b-A[_xc J)

3. Решается задача остатка переборным алгоритмом.

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

Описанная схема во многих случаях позволяет находить оптимальные решения для задач с большой комплектностью заготовок. Однако, когда число типов заготовок велико (>100), а требуемая их комплектность мала (<5), данная схема будет работать неэффективно, т.к. задача остатка практически не будет отличатся от исходной задачи и применение ЛП не

позволит сократить размерность задачи Е которую необходимо решать переборным алгоритмом.

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

Идея метода группировки заключается в следующем: Из исходной задачи Е генерируется некоторая другая задача Ег, которая содержит меньшее число типов заготовок, при увеличении их комплектности. При этом общее число заготовок Е и Ег одинаково. Генерируемая задача Ег должна отвечать следующим условиям :

1. Е доминирует над Ег.

2. Выполняется условие

3. Задача Ег - обладает свойством Ш1/Р.

Если задача Ег удовлетворяет условиям 1,2,3, то значения оптимального целочисленного решения задач Е и Ег совпадают т.е (2*(Ег)=£*(Е)).

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

Е , а следовательно, время, затрачиваемое на её решение, уменьшается.

Очевидно, что из решения 2*(Ег) и соответствующего ему плана раскроя получается план раскроя, удовлетворяющий условию задачи Е, с выполнением условия (2*(Ег)=2*(Е)). Это следует из доминантности задачи Е над Ег. (Получение окончательного решения осуществляется путем замены заготовок в плане раскроя для задачи Ег на парные им , но имеющим не большею длину из Е ).

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

В третей главе рассматривается задача 1\Г-мерной упаковки. Приводится постановка задачи и её математическая модель. Для возможности

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

В общем случае задачу И-мерной прямоугольной упаковки можно описать в следующем виде : Дано :

1. N >1 - мерность евклидова пространства.

2. Полубесконечный КГ- мерный прямоугольный параллелепипед с основанием 0=(01,02,...,0н-1).

3. Набор состоящий из т Ы-мерных прямоугольных параллелепипедов Р1=(р1Ьр12,..,рш), Р2=(р2ьР22,",Р2к), - , Рт=(ртьРт2,--,Рты) (заготовки), где ру-длины ребер.

Назовем прямоугольной упаковкой Р1,Р2,..Рт в О такое расположение заготовок внутри О (когда ни одна из заготовок не выходит за пределы области О), при котором выполняются следующие условия :

1. Грани заготовок расположены параллельно граням О.

2. Заготовки между собой не пересекаются.

положительное число, отвечающее условию, что все заготовки упаковываются в прямоугольный параллелепипед (01,02,.■ 1 .

Требуется: найти такую упаковку заготовок в О, в которой принимает наименьшее значение.

Для решения поставленной задачи было введено понятие задачи заполнения:

Для заданных значений Мг(<Р>^о), где

г- натуральное число от 1 до Ы;

<Р>~ набор, состоящий из ш Ы-мерных векторов Р;

Ъо- действительное положительное число; требуется найти бинарную матрицу Аг(ш х к) и вектор отвечающие определенным условиям:

• к<ш;

• гг0=0;гг1>0 1=1..к

}-1 _

• ^ = 1ШП К *рп *2гд

(;=1..т,а,у=1) /=1 к _

• IX =Ри -1с1"к

¡=1 к

• У г. <г

/ ^ П - О

¡=1

• Не существует такого X и что ай.]=1, %=0, для 1=1...к и к>ц>0. (Условие непрерывности расположения «единиц» в строках матрицы А) .

Геометрический смысл матрицы А заключается в следующем: Каждый столбец (кортеж) матрицы А характеризует некоторое сечение параллелепипеда О (1\Г-1)-мерной гиперплоскостью, где Аг(1^)=1 означает, что ]-тая плоскость пересекает заготовку Р^.

- это расстояние между двумя соседними секущими плоскостями. Секущие плоскости проводятся по г-тым «задним» граням.

Для установления связи между задачей заполнения и искомой упаковкой вводится следующее определение:

Множество задач (М^^Р^О, М2(<Р>,г2), ..., Мм(<Р>,гн)) называется связанным, если не существует таких 1 и что для любого г=1.ЛЧ найдется такое 8Г , при котором будут верны следующие условия АГ(8ГД)=1 и

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

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

Теорема 1. Любую М-мерную упаковку X можно представить в виде связанного множества (М1(<Р>,01), М2(<Р>,02),...,МК(<Р>,2Н(Х)). Теорема 2. Каждому связанному множеству (М}(<Р>,01), М2(<Р>,02),...,Мм(<Р>,2м)) соответствует некоторая упаковка X, в которой

Теорема 3. Связанное множество, при котором достигается минимальное значение Ъц, соответствует оптимальной упаковке.

Следствие: расчет оптимальной упаковки сводится к нахождению связанных множеств задач заполнения.

Нахождение допустимых матриц А,. и2гв задаче заполнения Мг (<Р>, сводится к решению задачи линейного раскроя (ЛР) с дополнительными ограничениями, накладываемыми на план раскроя: 1°. Матрица плана раскроя должна быть бинарной.

2°. Непрерывность заполнения по строкам - все единицы в строках должны располагаться друг за другом.

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

Получившийся план раскроя и будет искомая матрица Аг, а интенсивности карт раскроя - вектор Ъг

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

1. Основные действия выполняются с бинарными матрицами (особенно важно при реализации на ЭВМ).

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

3. Гибкость- возможность модификации при изменении геометрии рассматриваемых объектов или целевой функции.

В четвертой главе дана конкретизированная постановка задачи двумерной прямоугольной упаковки в полубесконечную полосу. Приведен алгоритм для случая N=2. В алгоритм так же были введены дополнительные отсечения, базирующиеся на геометрических свойствах рассматриваемых объектов и позволяющие существенно повысить производительность. Приведены результаты вычислительных экспериментов, проведено сравнение с методом зон Липовецкого [50].

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Картак, Вадим Михайлович

Заключение.

Диссертационная работа посвящена разработки точных алгоритмов упаковки 14- мерных прямоугольных параллелепипедов. Отдельно были рассмотрены случае когда N=1 и N>2 и показана сводимость второй ситуации к первой. Программная реализация представленных алгоритмов позволяет решать большой круг практических задач. Основные научные результаты диссертационной работы состоят в следующем :

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

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

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

4. Разработана математическая модель И-мерной прямоугольной упаковки параллелепипедов (N>2).

5. Введены понятия- задача заполнения и связанное множество задач заполнения. Показано, что задача заполнения является задачей ЛЦР с дополнительными ограничениями.

6. Доказан ряд теорем, показывающий связь между связанным множеством задач заполнения и задачей 14-мерной прямоугольной упаковки параллелепипедов (N>2).

7. Разработан алгоритм связанных заполнений (СЗ) для точного решения задачи Ы-мерной прямоугольной упаковки параллелепипедов (N>2).

8. Программно реализован СЗ-алгоритм для случая N=2. Проведены вычислительные эксперименты, подтверждающие перспективность данного подхода.

Список литературы диссертационного исследования кандидат физико-математических наук Картак, Вадим Михайлович, 1999 год

СПИСОК ИСПОЛЬЗУЕМЫХ источников

1. Adamowicz М., Allano A. Nesting Two-dimensional shapes in rectangular modules. Comput. Aided Des., 1976, 8,Nl,p.27-33.

2. Baum and L.E. Trotter, Jr. . Integer rounding for polymatroid and branching optimization problems. SIAMJ. Alg. Disc. Meth., 2(4): 416-425, 1981.

3. Blazewicz, P. Hawryluk, R. Walkowiak. Using a tabu search approach for solving the two-dimensional irregular cutting problem. -Annals of OR, 41(1-4), 1993, pp. 313-325.

4. Daniels К. M., Milenkovic V. J. Multiple Translational Containment: Approximate and Exact Algorithms /Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms.- San Francisco, CA, January 22-24, 1995, pp. 205-214.

5. Dycknoff H. A typology of cutting and packing problems. F.R.Germany., 1991,-41p.

6. Gau. Quasi-exact and heuristic algorithms for the standard one-dimensional cutting stock problem. Working Paper, 1994.

7. Gilmory P.C. and R.E. Gomory. A linear programming approach to the cutting-stock problem (Part 1). Oper. Res., 9:849-859, 1961.

8. Gilmory P.C., Gomory R.E. Multistage cutting stock problem of two and more dimensions.: Operat.Res., 1965, v.l3,nl.

9. Heckmann R., Lengauer T. Computing closely matching upper and lower bounds on textile nesting problems. - European Journal of Operational Research, 1997, pp. 101-117.

10.Heesch H., Kinzle O. Fluchenschlub System der Formen luckenlous aneinanduschliebenden Flachenteile. - Berlin -Heilberg, 1963.

11.Heesch H. Zur Klassification der ebenen kongruenten Abbildungen.- Der Mathem. und Natirwiss.Untersicht. 1959/60,12, 1.

12.Heesch H. Der topologisch gleichwertige Kristallein -dungen.- Zeitschrift fur Kristallographic., 1933/84, 5, 6.

13.Kartack V.M. (1997) Combinatorial algorithms for solving linear cutting.Decision Making under Conditions of Uncertainty (Cutting - Packing Problems). The International Scientific Collection, Ufa, Russia, 33-40.

14.Kartack V.M. Mukhametzyanov R.Z. «Method of rectangular packing calculation» «Decision marking under conditions of uncertainty» Ufa 1997

15.Lipski W. Kombinatoryka dla programistow.- Warszawa: Wydawnictwa naukowa - techniczne, 1982.-213c.

16.Luffissa H., McMillin B. Composite Stock cutting through simulated annealing. Technical report: Report Numbers CSC 91-09 and ISC 91-04, 50 p.

17.M.Fieldhouse. The duality gap in trim problems. SICUP-Bulletin, 5, 1990.

18.Marcotte. The cutting stock problem and integer rounding. Mathematical Programming, 33(l):82-92, 1985.

19.Martello S. and Toth P. (1990) Knapsack problems: Algorithms and Comruter Implementations.John Wiley, Chichester. Ong H.L., Magazine M.J. and WeeT.S. (1984) Probabilistic analysis of bin pasking heuristics. Operations Research, 32,983-998.

20.Mukhacheva E.A., Zalgaller W.A. Linear programming cutting problems: International Journal of Software Engineering and Knowledge Engineering. Vol.3., N4(1993),p.463-476.

21.Nemhauser and L.A. Wosley. Integer and combinatorial optimization. John Wiley & Sons, New York, 1988.

22.Nitsche, G. Scheithauer and J.Terno. New relaxations for the cutting stock problem. Technical Report MATH-NM-01 -1997, TU Dresden, 1997.

23.0.Marcotte. An instance of the cutting stock problem for which the rounding property does not hold. OR Letters, 4(5):239-243, 1986.

24.Riehme, G. Scheithauer and J.Terno. Numerical investigations on the MIRUP of the 2-stage guillotine cutting stock problem. Technical Report MATH-NM-17-1995, TU Dresden, 1995.

25.Scheithauer and J.Terno. A branch-and-bound algorithm for solving one-dimensional cutting stock problem exactly. Applications Mathematical, 23:2:151-167, 1995.

26.Scheithauer and J.Terno. The modified integer round-up property of the one-dimensional cutting stock problem. European J. Oper. Res., 84:562-571,1995.

27.Scheithauer and J.Terno. Theoretical investigations on the Modified integer Round-Up Property for the one-dimensional cutting stock problem. Technical Report MATH-NM-12-1993, TU Dresden, 1993 (to appear in OR letters).

28.Scheithauer. A new LP bound for the rectangle packing problem. Technical Report MATH-NM-23-1995/TU Dresden, 1995.

29.Scheithauer. New bounds for the container and multi-container loading problem. In Operations Research Proceedings 1996, Berlin, 1997. Springer.

30.Scheithauer..On the MAXGAP problem for cutting stock problems. J. Inform. Process. Cybernet. (EIK), 30:111-117, 1994.

31.Schwerin P. and Wascher G. (1997) The Bin-Packing Problem: Aproblem Generator and Some Numerical Experiments with FFD Packing and MTP. International Transactions in Operational Research, 4,№ 5/6, 337-389.

32.Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre prakti- sche Losung.- Leiprig, 1987, -p.207.

33.Wascher and T. Gau. Generating almost optimal solutions for the integer one-dimensional cutting stock problem. Technical report, Arbeitsbericht-Nr. 94/06, TU Braunschweig, 1994.

34.Беллман P., Дрейфус С. Прикладные задачи динамического программирования. - М.: Наука,!965.-458с.

35.Будников Ю.А., Гудылин С.П., Пазюк В.А. Автоматизация проектирования карт раскроя для термической резки металла// Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Материалы Всесоюзной конференции.-Уфа,1988.-С. 140-146.

36.Вайнштейн А.Д. Задачи об упаковке прямоугольников в полосу (Обзор). - В кн.: Дискретные задачи оптимизации. Управляемые системы , Новосибирск, 1984, №25, с. 17-37.

37.Гери М.П., Джонсон Д.С. Вычислительные машины и трудноразрешимые задачи. - М.; Мир, 1982. - 416 с.

38.Герман К.Г., Мухачева Э.А. Принцип организации АСТП рационального раскроя материала в условиях гибкого автоматизированного производства Журн. Авиационная промышленность,

39.Гилл Ф., Мюррей У., Кайт М. Практическая оптимизация. -М.:Мир,1985. - 509с.

40.3алгаллер В.А. Раскрой линейных материалов. -Л.: Егоровец,-220с.

41.Иванов Г.А. Проектирование размещения плоских геометрических объектов методами нелинейного программирования: Автореф.дисс... канд.техн.наук. - Йошкар-Ола:МарПИ, 1993 .-16с.

42.Картак В.М. Мухачева Э.А. «Плотная упаковка прямолинейных объектов» //Тез. докл. 10-й Байкальская школа-семинар «Методы оптимизации и их приложения» (1995, г. Иркутск).

43.Картак В.М. Розонова Л.Ф. «Метод последовательного уточнения оценок в линейном и прямоугольном раскрое» //Депонированная статья. Уфа 1995г.

44.Картак В.М. «Комбинаторные методы для получения оптимального целочисленного решения в задачах одномерного раскроя» // «Принятие решений в условиях неопределенности» Уфа 1997 г.

45.Канторович JI.B., Залгаллер В.А. Рациональный раскрой промышленных материалов.-Новосибирск.: Наука СО, 1971.-320с.

46.Канторович Л.В.,Залгаллер В.А. Расчет рационального раскроя промышленных материалов.- Л.:Лениздат,1951.~199с.

47.Кацев С.Б. Об одном классе дискретных минимаксных задач: Кибернетика, 1979, №5,с.139-141.

48.Компьютер и задачи выбора/Автор предисл.Ю.И.Журавлев.-М:Наука,1989.-208с.(Серия "Кибернетика - неограниченные возможности и возможные ограничения").

49.Кофман А. Введение в прикладную комбинаторику. М. : Наука, 1975.

50.Липовецкий А.И. К оптимизации свободного размещения прямоугольников. - В кн.: автоматизация проектирования в машиностроении, Минск,1985, с. 80-87.

51.Моденов П.С., Пархоменко A.C. Геометрические преобразования. - М: МГУ, 1961.-232с.

52.Мухачева Э.А. Поиск рационального решения в двухкритериальной задаче гильотинного раскроя. - Новосибирск: Оптимизация 33, с.56-63.

53.Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. - М.: Машиностроение, 1984, - 176с.

54.Мухачёва Э.А., Ибатуллина С.М. Оптимизация раскроя материала в заданном ассортиментном отношении. В кн.: Оптимизация 34 (51), Новосибирск, СО АН СССР, 1984, с. 122-128.

55.Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. -Новосибирск: Наука СО, 1987.-272с.

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

57.Рвачев Л.В. Геометрические приложения алгебры логики.- Киев: Техника,-212с.

5 8.Романовский И.В. Алгоритмы решения экстремальных задач.-М.: Наука, 1977.-351с.

59.Скатерной В. А. Оптимизация раскроя материалов в легкой промышленности. - М.: Легпромбытиздат, 1989.- 144 с.

60.Стоян Ю.Г. Об оптимальном размещении геометрических объектов: Автореф.дис....докт.техн.наук.-М.:МАИ,1970.-Збс.

61.Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. - Киев: Наук, думка, 1976. -247с.

62.Стоян Ю.Г., Панасенко A.A. Периодическое размещение геометрических объектов. - Киев: Наук, думка, 1978. -178с.

63.Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. - Киев. : Науч. думка, 1986. -286 с.

64.Тарасова Т.Д., Розанова Л.Ф. Метод последовательного улучшения оценок для решения задач раскроя в условиях единичного и мелкосерийного производства. // Принятие решений в условиях неопределенности: Сб. науч. работ Уфимского авиационного института. -Уфа, 1990,-с.112-116.

65.Фаддеев Д.К., Фаддева Д.Н. Вычислительные методы линейной алгебры. - М.: Физматгиз, 1963.-453с.

66.Федоров Е.С. Начала учения о фигурах. - Л.:АН СССР, 1953.-411с.

67.Фесенко А.Г. Решетчатая укладка плоских геометрических объектов с поворотом на угол тг. - Киев: ИК АН УССР, 1980.- 23 с. - /АН УССР. Ин-т кибернетики: Препринт - 80-53.

По теме диссертации опубликованы следующие работы.

1. Мухачева Э.А. Картак В.М. Плотная упаковка прямолинейных объектов // Методы оптимизации и их приложения: Тез. докл. 10-й Байкальской школы-семинара.- Иркутск, 1995. С.43.

2. Мухачева Э.А. Тарасова Т.Д. Картак В.М. Теория и методы решения задач прямолтнейного раскроя в условиях единичного производства (целочисленный раскрой) //Рук. Деп. в ВИНИТИ №1666-В95 от 06.06.1995.27 с.

3. Картак В.М. Комбинаторные методы для получения оптимального целочисленного решения в задачах одномерного раскроя // Принятие решений в условиях неопределенности: Межвузовский сборник- Уфа: УГАТУ, 1996. С. 40-46

4. Kartack V.M. Combinatorial algorithms for solving linear cutting problems // Decision marking under conditions of uncertainty: The International Scientific Collection .- Ufa: УГАТУ, 1997.- C.33-40.

5. Kartack V.M. Mukhametzyanov R.Z. Method of rectangular packing calculation // Decision marking under conditions of uncertainty: The International Scientific Collection .- Ufa: УГАТУ, 1997.- С. 178-188.

6. Мухачева Э.А. Белов Г.Н. Картак В.М. Мухачева А.С. Задачи линейной упаковки: вычислительные эксперименты с методом последовательного уточнения оценок и модифицированного метода ветвей и границ // Исследование операций: Тез. докл. Международной конференции. -Новосибирск, 1998,- С.56.