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

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

БЕЛОВ Глеб Николаевич

МОДЕЛИРОВАНИЕ И РЕШЕНИЕ ЗАДАЧИ ОДНОМЕРНОГО РАСКРОЯ МАТЕРИАЛА РАЗЛИЧНЫХ ДЛИН МЕТОДОМ ОТСЕКАЮЩИХ ПЛОСКОСТЕЙ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

Уфа-2003

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

Научный руководитель — доктор технических наук, профессор

Мухачева Элита Александровна

Официальные оппоненты — доктор физико-математических наук, доцент

Газизов Рафаил Кавыевич

доктор технических наук, доцент Фроловский Владимир Дмитриевич

Ведущая организация — Институт математики с вычислительным

центром Уфимского научного центра РАН

Защита состоится__ октября 2003 г. в_часов на заседании

диссертационного совета Д212.288.03 Уфимского государственного авиационного технического университета по адресу: 450000, Уфа- центр, ул. К. Маркса 12, УГАТУ.

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

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

/В.В. Миронов/

Общая характеристика работы

Актуальность проблемы. Задачи раскроя-упаковки вызывают широкий интерес как в производстве, так и в теоретических исследованиях. Классическая задача одномерного раскроя (one-dimensional cutting stock problem, 1DCSP) рассматривается во множестве публикаций. Эта задача состоит в минимизации количества идентичных прутков материала, используемых для раскроя определенного набора заготовок. В диссертации изучается обобщенный случай, когда имеется материал различных длин.

В последние годы в связи со значительным развитием вычислительной техники в практическом применении точных методов достигнуты значительные успехи. В большинстве случаев это модификации метода ветвей и границ. Наиболее успешен метод ветвей и границ с генерацией столбцов (branch-and-price, F. Vanderbeck, P. Vance, Y. Kupke, V. de Carvalho, Z. Degraeve & M. Peeters, И. Романовский, В. Картак).

В 1951 г. JIB. Канторович и В.А. Залгаллер предложили подход, ' основанный на непрерывной релаксации с генерацией столбцов. В англоязычном пространстве это сделали в 1961 г. Р.С. Gilmore & R.E. Gomory. В 1963 г. они реализовали непрерывную релаксацию с округлением до целого решения и для задачи с несколькими типами материала. Они же установили, что возможность комбинации нескольких длин обеспечивает очень хорошую утилизацию материала. Было отмечено, что поведение целевой функции очень сложно, так как она определяется линейными комбинациями цен материала, и поэтому трудно найти оптимум или доказать его оптимальность с помощью нижней границы. Для 1DCSP с несколькими длинами материала в литературе содержатся экспериментальные результаты практически только по эвристикам.

Другой распространенный в дискретной оптимизации точный метод — это метод отсекающих roi0CK0CTefi(cutting plane algorithm, CPA). Таким образом, добавление отсечений к ограничениям непрерывной репяк^гц^ ггри-Ктгягяет

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

С.Петер6ург 09 )005 м

J~iy

решение релаксации' к целочисленному оптимуму. Однако добавление отсечений в модели с генерацией столбцов не так просто. Дело в том, что при генерации новых столбцов приходится учитывать коэффициенты отсечений для этих столбцов с нелинейными зависимостями. Э.А. Мухачева и С.М. Ибатуллина применили непрерывную релаксацию с генерацией столбцов для раскроя материала нескольких типов в заданном ассортиментном отношении. Они не ставили целью получение целочисленного решения. Исходя из вышеизложенного, представляет интерес моделирование функции цели и изучение её поведения, разработка метода отсекающих плоскостей (cutting plane algorithm, CPA) для решения задачи раскроя прутков различной длины и его программная реализация, которая позволила бы решать производственные задачи в приемлемое время. Тогда разработанное алгоритмическое и программное обеспечение становится конкурентоспособным в ряду точных и эвристических подходов. В этом состоит актуальность данной диссертационной работы.

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

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

1. Разработать и исследовать математическую модель задачи 1DCSP для материала различных длин;

2. Разработать эффективный метод моделирования раскроев(столбцов) при наличии прутков различной длины и сечений Гомори.

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

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

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

На защиту выносятся:

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

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

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

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

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

Апробация работы. Работа выполнялась в рамках заданий РФФИ, проекты 99-01-00937, 01-01-00510 и долгосрочного совместного научного исследования по проблемам раскроя-упаковки между УГАТУ(кафедра вычислительной математики и кибернетики) и Дрезденским техническим университетом (институт вычислительной математики). Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:

• ХХХХУП Теоретическая конференция молодых ученых "Нефть и газ".

Уфа, 1997;

• Сибирская конференция по исследованию операций. Новосибирск, 1998;

• CSIT-2000, The 2nd International Workshop on ComputerScience and Information Technologies. Ufa, Russia (на англ. яз.);

• The 3rd Siemens Workshop on Applied Discrete Optimization. Wuerzburg, Germany, 2000 (на нем. яз.);

• CSIT-2001, The 3rd International Workshop on Computer Science and Information Technologies. Ufa, Russia (на англ. яз.);

• The 24th International Workshop on Discrete Optimization. Lutherstadt Wittenberge, Germany, 2002 (на англ. яз.);

• IFORS 2002 "OR in a globalised, networked world economy". www.ifors2002.org (на англ. яз.);

• Конференция "Математическое программирование и приложения". Екатеринбург. ИММ УРО РАН. 2003;

• Семинарах кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета;

• Семинарах института вычислительной математики Дрезденского технического университета;

• Семинаре института математики с вычислительным центром Уфимского научного центра РАН.

Публикации

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

Структура и объем работы

Диссертация состоит из введения, пяти глав, заключения и приложений. Объем работы составляет 124 страницы машинописного текста, включая 8

рисунков на 5 страницах, 4 примера на 5 страницах, 2 приложения на 30 страницах, библиографию, содержащую 49 названий.

Содержание диссертации

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

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

Задача определяется следующим информационным вектором: (т, М, I=(/, ...1т+м), Ь = (b,... bm+u), p-(pi... рм))- Здесь т — количество типов заготовок, М—количество типов материала, п := т+М—размерность задачи, /;.../„ — длины заготовок каждого типа, /„+/... 1„ — длины прутков материала, bj... Ът и bm+i... Ь„ — комплектности заготовок и прутков (т.е. требуемые количества заготовок и количества имеющихся прутков каждого типа), р/ ...рм —цены материала.

Вектор а = (а;.....я„)т € описывает карту pacKpoR(cutting pattern, CP).

Компоненты щ для 1 < i < т определяют количество экземпляров заготовки типа i. Компоненты а, для т< i < п — булевые переменные: а, = 1, если используется пруток типа г. Карта раскроя а называется допустимой, если

Пусть г) обозначает количество допустимых СР. Матрица А~(а,;)^

называется раскройной матрицей. Пусть выражение "а е А" обозначает "а является столбцом А", то есть а — карта раскроя.

Матрица А задается неявно, так как на практике количество столбцов очень велико. Например, если среднее количество заготовок в карте раскроя равно 10, всего 100 типов заготовок и комплектности всех заготовок равны 1 (это сильное допущение), то количество различных карт раскроя имеет порядок Поэтому только необходимые СР должны генерироваться в ходе решения.

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

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

Ал горят;.; глетода отсекающих плос«я»етей для задачи одномерного раскроя материала различных длин Шаг 0 Установить Ъ° := Ь, к:=0 и г := ®.

Шаг 1 Непрерывная релаксация: снять требование целочисленности и вычислить оптимальное решение хк е ¡С*"*" .

Шаг 2 На основе хк- сконструировать допустимое целочисленное решение

х е путем эвристического решения задачи остатка. Если ст х < г, тогда ~ —

2 := с х.

Шаг 3 Если г равно наименьшей линейной целочисленной неотрицательной комбинации / цен материала, большей или равной тогда стоп — оптимальное решение найдено.

Шаг 4 Сконструировать сечения, добавить их к (Л^ Ък) (этим определяется Ь )), удалить излишние (неактивные) сечения, установить к:-к+1 и перейти к шагу 1.

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

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

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

Далее описывается добавление отсекающих плоскостей к формулировке непрерывной релаксации. Для генерации сечений Гомори в моделях с неявной матрицей ограничений можно использовать процедуру округления Чватала-Гомори. Пусть задан многогранник Р ={Ах = Ъ : х > 0, х е И},и Q — множество целочисленных точек в Р : Q = {Ах = Ь: х > 0; х б Ъ }, а 5 =сопу(0 —выпуклая оболочка <2. Сечения, описывающие Я, можно получить

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

Процедура округления Чватала-Гомори

Известно, что для каждого и е имеет место итАх =ит Ь.

Округление вниз ведет к I итл] х и Ъ, т.к. х > 0. И наконец, для целочисленных неотрицательных х выполняется I итА] х > [г/ Ь]. Эти неравенства добавляются к имеющимся ограничениям. В качестве ¡¡-векторов берутся строки оптимальной обратной базисной матрицы(базисные сечения). Это гарантирует, что последнее непрерывное решение становится недопустимым при данных сечениях. В общем случае сечения, произведенные из первогр непрерывного решения, недостаточны для оптимального решения. В этом случае из оптимального базиса расширенной матрицы ограничений создаются сечения более высокого порядка, чьи коэффициенты щ зависят от более ранних сечений и у-й коэффициент г-го сечения:

. ТЛ+М Г—I .

1=1 5-1

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

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

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

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

тах-^с(а) :=с1Та-с(а): а е . С помощью динамического программирования можно решить эту задачу сразу для всех типов рюкзака (прутка). Так как в раскройной матрице приняты только собственные карты, уравнения динамического программирования усложняются. Поэтому в работе предлагаются критерии устранения повторов в прямой стратегии динамического программирования. Прямая стратегия реализована по принципу Никольсона: это означает, что список заготовок динамически разделяется на две части, что помогает уменьшить количество состояний. Значение целевой функции для общего списка строится из двух частей. Чтобы сэкономить память, информация для восстановления решения не сохраняется. Решение восстанавливается методом ветвей и границ по известной целевой функции с некоторым численным допуском.

Далее рассматривается генерация столбцов при наличии сечений. Пусть й е — двойственные оценки. Собственные карты раскроя составляют мультирюкзачную задачу

Функция с (а) не сепарабельна по компонентам вектора а, так как коэффициенты сечений к^а), 1 < ?- < ¡л нелинейны. Поэтому динамическое программирование неприменимо, возможен только метод ветвей и границ. Решение мультирюкзачной задачи было реализовано через решение задачи с фиксированным размером прутка для каждого типа прутка Ь := Ц, 1 <J <М.

т и

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

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

Далее моделируется критерий оптимальности задачи одномерного раскроя с несколькими типами прутка. Следующие два случая не требуют проверки оптимальности: когда базисные переменные симплекс-решения целочисленны> или значение непрерывной целевой функции г* равно значению эвристического решения г (нижняя граница достигнута). В противном случае (гк < 2 ) нужно проверить, нет ли потенциально лучшего значения целочисленного решения между и г . Тогда г сравнивается с линейной комбинацией гг цен материала. Если г = г , то г - оптимум.

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

временного поведения алгоритма. Поведение алгоритма задокументировано на представительном наборе задач средней и большой размерности (100-400 типов заготовок).

Широко известный точный метод для одномерной задачи раскроя — это branch-and-price. В каждом узле дерева решений к непрерывной релаксации добавляются ограничения ветвления. Пока не известны результаты применения branch-and-price к задаче с несколькими типами прутка. Поэтому сравнение произведено только для случая Af=l. Тесты на отдельных задачах показывают, .что CPA имеет преимущества на задачах с большим разрывом оптимальности.

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

Важный фактор эффективности теста оптимальности — это дискретизация цен материала. Чем гуще растровые точки, тем труднее поднять нижнюю границу а так, что между z* и оптимальным целочисленным г* не остается растровых точек. Густота зависит от наибольшего общего делителя цен материала НОД({р,}). Пусть параметр D характеризует дискретизацию таким образом, что D зависит от абсолютных значений цен материала:

D-.=pmaJHOR(p).

Рисунки 1 и 2 показывают некоторые статистические характеристики процесса решения в зависимости от времени. Это следующие: доля нерешенных задач (т.е. количество задач в среднем не решенных оптимально за данное время); количество растровых точек между нижней границей & и лучшим известным целочисленным решением z ; относительный разрыв

оптимальности (z - zî)/Lmai. Вычисления выполнялись на рабочих станциях Sun Ultra 60, 360 MHz. Рис. 1 показывает долю нерешенных примеров. Каждая линия представляет усредненную производительность серии с тп=40 для разного количества типов материала (М=2,4,8). Как можно видеть, чем больше типов материала, тем больше свободы выбора решения имеет алгоритм. Если снизить D от 100 до 10, то гораздо меньше примеров требуют введения сечений (см. левую сторону графиков при / = 0). На рисунке 2 изображены результаты аналогичных расчетов с т=20 .

07,

I

06

05,

I M | 03

| 02 01

X,

V-

-О- М-2 & 0-100

- -а М-410=100

• -в ■ м=е s d=ioo

-é- М-2» 0-10

»0 9 0 E^'frfi-tH

0 5j : 04 0 3?, 02

-О- М=2 & 0=100 о.. М«4&0=100 • -в • М=В & D-100 —M-4&040

N

Ж

1С?

.-я--.»,.

орв-и,« время, сек

Рис. 1 :т — 40, доля нерешенных Рис. 2: т = 20, доля нерешенных примеров из всей серии примеров

Чтобы задокументировать поведение алгоритма на широком наборе задач и дать материал для сравнения другим исследователям, был сделан анализ чувствительности по параметрам задачи и алгоритма. Задачи с большим количеством типов прутка (М= 8,16) гораздо легче для разработанного подхода, чем с малым количеством.

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

1. Разработана и исследована математическая модель задачи ШСБР для материала различных длин. Задача описана моделью целочисленного программирования с неявно заданной информацией. Это позволило

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

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

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

4. Модифицированы некоторые методы дискретной оптимизации, направленные на повышение эффективности метода отсечений, а именно:

• вариация остаточной задачи позволила в среднем в 10 раз снизить количество примеров, где необходимы сечения;

• проверка • доминантности заготовок снижала размер задачи генерирования раскроя в среднем до 50% без сечений и до 90% с сечениями;

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

5. Разработано алгоритмическое и программное обеспечение и проведен численный эксперимент. На этой базе

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

• проанализирована эффективность метода на широком наборе классов задач. Крупные задачи (100 типов заготовок) решаются оптимально за 1 минуту в 50% случаев. В нерешенных задачах расстояние до оптимума не превышает 2-3% цены наибольшего прутка;

• проведено сравнение с точным методом branch-and-price, показаны преимущества метода отсекающих плоскостей на задачах с большим разрывом оптимальности и более слабые результаты на задачах с малыми комплектностями.. Сравнение с эвристиками показало улучшение полезного использования материала в среднем на 7-8% цены наибольшего прутка, а также возможность улучшения решения с течением времени.

Список публикаций

1. Г.Н. Белов, Т.Д. Тарасова и Л.Ф. Розанова. Метод дихотомии для решения 1 задач гильотинного раскроя. // Математическое программирование и , приложения.: Материалы конференции. Екатеринбург,: ИММ УРО АН РАН, V 1997. - С. 95-97.

2. Г.Н. Белов,. Т.Н. Григорчук. Об одном методе уменьшения динамической шкалы в задаче рюкзака. //XXXXVTI Теоретическая конференция молодых ученых "Нефть и газ". Уфа,: УГНТУ, 1997. - С. 43-44.

3. Г.Н. Белов. Модифицированный метод последовательного уточнения оценок для задачи одномерного раскроя. //Принятие решений в условиях

I неопределенности. Задачи раскроя-упаковки.: Сборник научных трудов; Уфа,:

УГАТУ, 1997. - С. 56-61. (на англ. яз.). ^ 4. Э.А. Мухачева, Г.Н. Белов, В.М. Картак, и А.С. Мухачева. Задачи линейной упаковки: численный эксперимент с методом последовательного уточнения оценок и модифицированным методом ветвей и границ. //Сибирская конференция по исследованию операций.: Новосибирск,: ИМ СО РАН, 1998. -С. 21-23.

5. Г.Н. Белов. Псевдослучайное генерирование тестовых задач раскроя-упаковки: методы и представительность эксперимента.//Принятие решений в условиях неопределенности.: Сборник научных трудов; Уфа,: УГАТУ, 1998. -С.-23-27.

6. Г.Н. Белов. Точное решение одномерных задач раскроя методом отсекающих плоскостей. //The 23rd International Workshop on Discrete Optimization. Holzhau, Germany, 2000. - P. 85-88. (на англ. яз.)

7. Г. Шайтхауэр, Й. Терно и Г.Н. Белов . Метод отсекающих плоскостей для задачи одномерного раскроя. //CSIT-2000, The 2nd International Workshop on Computer Science and Information Technologies. Ufa, Russia. - P. 66-70 (на англ. яз.)

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

9. Э.А. Мухачева, Г.Н. Белов, В.М. Картак и А.С. Мухачева. Задачи линейной упаковки: численный эксперимент с методом последовательного уточнения ч оценок и модифицированным методом ветвей и границ. //Pesquisa Operacional. Vol.20. No.2. 2000. - P.153-168. (на англ. яз.)

10. Г.Н. Белов. Метод отсекающих плоскостей для задачи одномерного раскроя материала различных длин. //CSIT-2001, The 3rd International Workshop on Computer Science and Information Technologies. Ufa, Russia. - P. 34-37 (на англ. яз.). ,

11. Г. Шайтхауэр, Й. Терно, А. Мюлер и Г.Н. Белов. Точное решение одномерных задач раскроя методом отсекающих плоскостей./Яоигпа! of the Operational Research Society 52,2001. - Р.1390-1401.(на англ. яз.)

12. Г.Н. Белов. Некоторые аспекты метода отсекающих плоскостей для задач раскроя-упаковки. /'/The 24th International Workshop on Discrete Optimization. Lutherstadt Wittenberge, Germany: 2002. - P.43-45. (на англ. яз.)

13. Г.Н. Белов, Г. Шайтхауэр. Метод отсекающих плоскостей для задачи одномерного раскроя материала различных длин. //European Journal of Operational Research, Special Issue on Cutting and Packing, 141(2), 2002. - P. 274-294.(на англ. яз.)

Белов Глеб Николаевич

МОДЕЛИРОВАНИЕ И РЕШЕНИЕ ЗАДАЧИ ОДНОМЕРНОГО РАСКРОЯ МАТЕРИАЛА РАЗЛИЧНЫХ ДЛИН МЕТОДОМ ОТСЕКАЮЩИХ ПЛОСКОСТЕЙ

Л

Специальность 05.13.18 - Математическое моделирование, у численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

)

Подписано в печать 03.09.03 Формат 60x84 1/16 Бумага писчая №1. Печать плоская. Гарнитура Times New Roman Усл. печ.л. 1,0. Уч.-изд.л. 0,9 Тираж 100 экз. Заказ № 285

Уфимский государственный авиационный технический университет Уфимская типография №2 Министерства печати и массовой информации Республики Башкортостан 450000, Уфа-центр, ул. К.Маркса, 12

113656

Использованные обозначения

Введение

1 Постановка задачи и схема метода

1.1 Постановка задачи одномерного раскроя материала различных длин.

1.2 Классификация методов решения задач раскроя-упаковки

1.3 Схема решения.

1.4 Выводы. о 2 Непрерывная релаксация

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

2.2 Метод секущих плоскостей на базе непрерывной релаксации

2.3 Удаление сечений: меры против циклов.

2.4 Генерация сечений.

1 2.5 Выводы. i 3 Генерация столбцов

3.1 Генерация столбцов без сечений

3.1.1 Постановка задачи генерирования столбцов.

3.1.2 Динамические уравнения для генерирования карты раскроя

3.1.3 Прямая стратегия динамического программирования

3.1.4 Принцип Никольсона в динамическом программировании

3.1.5 Расчет решения.

3.2 Генерирование столбцов при наличии сечений

3.2.1 Постановка задачи. ф 3.2.2 Несколько типов прутка.

3.2.3 Сортировка заготовок.

3.2.4 Предварительный останов.

3.3 Доминантность заготовок.

Ф 3.3.1 Проверка доминантности заготовок при наличии сечений

3.4 Выводы.

4 Построение целочисленных решений и тест оптимальности

4.1 Построение целочисленных решений.

4.1.1 Округление непрерывного решения

4.1.2 Расширение задачи остатка.

4.2 Метод последовательного уточнения оценок

4.3 Тест оптимальности целочисленного решения.

4.3.1 Описание задачи.

4.3.2 Генерация растровых точек цен материала.

4.4 Выводы.

5 Вычислительный эксперимент ф 5.1 Реализация программного обеспечения

5.1.1 Концепция ПО.

5.1.2 Модифицированная трансформация базиса в симплекс-методе

5.1.3 Переполнение мантиссы.

5.1.4 Погрешности вычислений. Рестарт.

5.2 Несколько типов прутка: сравнение с другими алгоритмами

5.3 Генерирование тестовых задач.

5.4 Количество задач с сечениями.

5.5 Сравнение с методом branch-and-price. у. 5.6 Несколько типов прутка: характеристики алгоритма.

5.7 Графический анализ производительности.

5.8 Эталонные результаты.

5.9 Управляющие переменные.

5.10 Фиксированные выходные параметры.

5.11 Целочисленная трансформация базиса.

5.12 Оценка серии т — 40, М = 5.

5.13 Наблюдения относительно свойства MIRUP.

5.14 Таблицы в приложении.

5.15 Восстановление карты посредством branch-and-bound.

5.16 Выводы по тестам и направления дальнейшей работы.

5.17 Внедрение.

6 Заключение

Актуальность проблемы. Задачи раскроя-упаковки вызывают широкий интерес как в производстве, так и в теоретических исследованиях. Классическая задача одномерного раскроя (one-dimensional cutting stock problem, 1DCSP) рассматривается во множестве публикаций [4, 25, 26, 31, 21]. Эта задача состоит в минимизации количества идентичных прутков материала, используемых для раскроя определенного набора заготовок. В диссертации изучается общий случай, когда имеется материал различных длин.

Еще в 1951 году JI.B. Канторович и В.А. Залгаллер предложили подход, основанный на непрерывной релаксации с генерацией столбцов (карт раскроя). Независимо аналогичный метод был обоснован и подробно описан Гил мор и Гомори в [25]. Требование целочисленности интенсивностей раскроя опускается и можно применить симплекс-метод. Однако из-за большого количества столбцов приходится генерировать только их подмножество, т.е. матрица ограничений задана неявно. При этом (под-)задача генерирования столбцов является задачей рюкзака и решается методом ветвей и границ или с помощью динамического программирования. Решение непрерывной релаксации можно округлить и решить задачу остатка с помощью эвристик. В случае с единственным типом материала в подавляющем большинстве примеров разрыв между значением непрерывной релаксации и значением полученного целочисленного решения не превышает 1 длины материала, то есть округленное решение оптимально. В остальных случаях автору не известно разрыва более чем 2. В условиях массового производства, где значения интенсивностей раскроя велики, этот подход можно назвать рациональным. Но в единичном производстве необходимы более эффективные методы.

Более того, если решать задачу оптимально, то в большинстве случаев оказывается, что разрыв между значением непрерывной релаксации и значением целочисленного оптимума не достигает 1 (т.н. свойство целочисленного округления, integer round-up property IRUP). Известны также примеры, где этот разрыв превышает 1. Есть гипотеза о том, что этот разрыв не может достигать 2 (модифицированное свойство целочисленного округления, modified integer round-up property MIRUP).

Существует-множество эвристик различной сложности. Самые простые — это первый подходящий (First Fit, FF), первый подходящий с упорядочиванием (First Fit Decreasing, FFD) и их вариации. Большего усердия при разработке и исследовании требуют такие методы, как жадный алгоритм и его вариация, метод последовательного уточнения оценок (sequential value correction method SVC, Мухачева и Залгаллер [31]), эволюционные алгоритмы, методы частичного перебора. Очень много эвристических схем подключают непрерывную релаксацию с генерацией столбцов для вычисления нижней границы и получения округленного решения. Существуют различные оценки качества эвристик, например вероятностные характеристики или доказательства асимптотической точности на определенном классе задач (см. Гимади и Залюбовский [3]).

Долгое время применение точных методов для 1DCSP не было успешным. Однако в последние годы в связи со значительным развитием вычислительной техники, а также из-за приспособления точных методов к задаче (например, специфические методы ветвления) в практическом применении точных методов достигнуты значительные успехи. В большинстве случаев эти методы — модификации метода ветвей и границ. Наиболее успешен метод ветвей и границ с генерацией столбцов, т.н. branch-and-price. Ветвление производится посредством добавления ограничений (разбиения множества решений) в непрерывной релаксации. Для задачи Bin Packing (требуемые комплектности всех заготовок равны 1) разработаны специальные границы целевой функции и модификации метода ветвей и границ [43, 44].

Другой распространенный в дискретной оптимизации точный метод — это метод секущих плоскостей (cutting plane algorithm, CPA). Секущие плоскости (отсечения) описывают выпуклую оболочку целочисленных решений. Таким образом, добавление отсечений к ограничениям непрерывной релаксации уточняет нижнюю границу целевой функции и приближает решение релаксации к целочисленному оптимуму. Последний часто может быть найден с помощью эвристических процедур округления непрерывного решения. Однако добавление отсечений в модели с генерацией столбцов не так просто. Дело в том, что при генерации новых столбцов приходится учитывать коэффициенты отсечений для этих столбцов. Коэффициенты нелинейно зависят от предыдущих ограничений. Эту проблему впервые решили Scheithauer et al (2001), в том числе и автор данной работы. К сожалению, генерация столбцов не позволяет применять вариации метода, отличающиеся строгой сходимостью. Ранее был реализован следующий метод: в ходе решения непрерывной релаксации генерировалось множество столбцов и на этом множестве применялся метод секущих плоскостей. Однако оптимум может требовать других столбцов.

В 1963 Гилмор и Гомори описали реализацию непрерывной релаксации с округлением для задачи с несколькими типами материала [26]. Они не рассматривали границы комплектности материала, т.е. количество прутков каждого типа было неограниченным. Они установили, что возможность комбинации нескольких длин обеспечивает очень хорошую утилизацию материала (мало отхода). Они отметили, что поведение целевой функции очень сложно, так как она определяется линейными комбинациями цен материала, и поэтому трудно найти оптимум или доказать его оптимальность с помощью нижней границы (настоящая работа подтверждает оба вывода). Для 1DCSP с несколькими длинами материала литература содержит экспериментальные результаты практически только по эвристикам. Исходя из вышеизложенного, проблема является актуальной.

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

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

0 1. Разработать и исследовать математическую модель задачи 1DCSP для материала различных длин.

2. Разработать эффективный метод моделирования раскроев (столбцов) при наличии прутков различной длины и сечений Гомори.

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

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

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

На защиту выносятся:

1. Математическая модель задачи одномерного раскроя с несколькими типами прутка с неявной матрицей ограничений;

2. Критерий оптимальности решения задачи одномерного раскроя материала различных длин;

3. Вычислительная схема метода отсекающих плоскостей для решения задачи одномерного раскроя материала различных длин;

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

• Метод генерации столбцов при наличии сечений;

• Метод округления непрерывного решения;

• Метод генерации растровых точек для критерия оптимальности;

• Критерий доминантности заготовок в задаче рюкзака;

• Конкретизация принципа Никольсона в динамическом программировании для генерирования раскроя материала различной длины;

• Модификация прямой стратегии в динамическом программировании;

5. Компьютерная программа, реализующая разработанный алгоритм;

6. Численный эксперимент на основе созданного алгоритмического и программного обеспечения.

Научная новизна работы.

Новыми в работе являются:

• Точный метод отсекающих плоскостей для решения задачи одномерного раскроя материала различных длин, разработанный на базе метода Гомори решения целочисленных задач линейного программирования;

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

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

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

• Критерий доминантности заготовок в задаче рюкзака с верхними границами (ранее был известен только для задачи без верхних границ);

• Модификация принципа Никольсона в динамическом программировании для генерирования раскроя материала различной длины (ранее применялся для задачи без верхних границ);

• Критерий доминантности состояний в прямой стратегии динамического программирования.

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

Апробация работы. Работа выполнялась в рамках заданий РФФИ, проекты 99-01-00937, 01-01-00510 и долгосрочного совместного научного исследования по проблемам раскроя-упаковки между УГАТУ (кафедра вычислительной математики и кибернетики) и Дрезденским техническим университетом (институт вычислительной математики). Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:

• XXXXVII Теоретическая конференция молодых ученых "Нефть и газ". Уфа, 1997;

• Сибирская конференция по исследованию операций. Новосибирск, 1998;

• CSIT-2000, The 2nd International Workshop on Computer Science and Information Technologies. Ufa, Russia (на англ. яз.);

• The 3rd Siemens Workshop on Applied Discrete Optimization. Wuerzburg, Germany, 2000 (на нем. яз.);

• CSIT-2001, The 3rd International Workshop on Computer Science and Information Technologies. Ufa, Russia (на англ. яз.);

• The 24th International Workshop on Discrete Optimization. Lutherstadt Wittenberge, Germany, 2002 (на англ. яз.);

• IFORS 2002 "OR in a globalised, networked world economy". www.ifors2002.org (на англ. яз.);

• Конференция "Математическое программирование и приложения". Екатеринбург. ИММ УРО РАН. 2003;

• Семинарах кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета;

• Семинарах института вычислительной математики Дрезденского технического университета;

• Семинаре института математики с вычислительным центром Уфимского научного центра РАН.

Публикации

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

Содержание диссертации

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

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

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

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

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

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

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

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

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

4. Модифицированы некоторые методы дискретной оптимизации, направленные на повышение эффективности метода отсечений, а именно:

4.1 Вариация остаточной задачи позволила в среднем в 10 раз снизить количество примеров, где необходимы сечения;

4.2 Проверка доминантности заготовок снижала размер задачи генерирования раскроя в среднем до 50% без сечений и до 90% с сечениями;

4.3 Устранение неперспективных состояний и применение принципа Ни-кольсона в динамическом программировании сделало его применение конкурентноспособным по сравнению с другими методами генерации столбцов.

5. Разработано алгоритмическое и программное обеспечение и проведен численный эксперимент. На этой базе:

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

5.2 Проанализирована эффективность метода на широком наборе классов задач. Крупные задачи (100 типов заготовок) решаются оптимально за 1 минуту в 50% случаев. В нерешенных задачах расстояние до оптимума не превышает 2-3 % цены наибольшего прутка;

5.3 Проведено сравнение с точным методом branch-and-price, показаны преимущества метода отсекающих плоскостей на задачах с большим разрывом оптимальности и более слабые результаты на задачах с малыми комплектностями. Сравнение с эвристиками показало улучшение полезного использования материала в среднем на 7-8% цены наибольшего прутка, а также возможность улучшения решения с течением времени.

6 Заключение

В данной работе метод секущих плоскостей для линейного раскроя, предложенный в Scheithauer et al (2001), обобщается на задачу с несколькими типами прутка и численно исследуется. Для генерации столбцов при наличии сечений были разработаны: верхняя граница нелинейной целевой функции и эффективные критерии предварительной остановки поиска. Предварительный останов необходим из-за неточной границы. Необходимые результаты из теории многогранников были переняты из Scheithauer et al (2001) и [34]. Внесены эффективные модификации в различные составные части метода.

Один из возможных способов целочисленной трансформаций базиса в симплекс-методе был реализован и сравнен с классическим. Новый способ имеет преимущества только при малых размерностях, где не происходит переполнения мантиссы. Критерий доминантности заготовок был обобщен для задачи рюкзака с верхними границами. Это вызвало значительное уменьшение размера задач генерации столбцов, до « 50% без сечений и до w 90% с сечениями. В динамическом программировании (генерация столбцов без сечений) была модифицирована прямая стратегия. Принцип Никольсона в динамическом программировании был впервые применен в задаче генерирования раскроя (т.е. столбцов).

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

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

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

2. Белов Г.Н. Псевдослучайное генерирование тестовых задач раскроя-упаковки: методы и представительность эксперимента. //Принятие решений в условиях неопределенности.: Сборник научных трудов; Уфа,: УГАТУ, 1998. С. 23-27.

3. Гимади Э.Х., Залюбовский В.В. Задача упаковки в контейнеры: асимптотически точный подход. Известия высших учебных заведений, Математика. N12 (427) 1997. С. 25-33.

4. Канторович JI.B., Заллгаллер В.А. Расчет рационального раскроя материалов // Лениздат. 1951.-54 с.

5. Картак В.М. Оптимальная упаковка N-мерных параллелепипедов в полубесконечность // 12-я Байкальская международная конференция, методы оптимизации и их приложения. Иркутск. 2001. С. 18-22.

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

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

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

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

10. Мухачева Э.А., Картак В.М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя // Информационные технологии. N.9. 2000.- С. 15-22.

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

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

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

14. S. Baum and L. Е. Trotter, Jr. Integer rounding for polymatroid and branching optimization problems. SIAM J. Alg. Disc. Meth.y 2(4). 1981.-P.416-425.

15. G. Belov and G. Scheithauer (2002). A Cutting Plane Algorithm for the One-Dimensional Cutting Stock Problem with Multiple Stock Lengths. European Journal of Operational Research, Special Issue on Cutting and Packing, 141(2). -P.274-294.

16. E.G. CofFman, M.R. Garey, D.S. Johnson. Approximation algorithms for bin-packing.- An updated surey. Algorithm Design for Computer System Design. CISM courses and lectures, No 284, 1984.- P.49-106.

17. De Carvalho, V. LP models for bin packing and cutting stock problems. Eur. Jour, of Oper. Res. 141. 2002. -P.253-273.

18. Z. Degraeve, M. Peeters, Optimal integer solutions to industrial cutting stock problems: Part 2, Benchmark Results, Technical Report, Katholieke Universiteit Leuven, 2000.-38 p.

19. H. Dykhoff. A typology of cutting and packing problems. F.R. Germany, 1991.257 p.

20. H. Dyckhoff and U. Finke. Cutting and packing in production and distribution. Physica Verlag, Heidelberg, 1992.-382 p.

21. H. Dyckhoff, G. Scheithauer, J. Terno, Cutting and packing, in: M. Dell'Amico, F. Maffioli, S. Martello (Eds.), Annotated Bibliographies in Combinatorial Optimization, John Wiley & Sons, Chichester, 1997.- P.393-412.

22. E. Falkenauer. A hybrid grouping genetic algorithm for bin packing. Journal of heuristics. 2(1). 1998. -P. 5-13.

23. O. Holthaus. Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths. Eur. Jour, of Op. Res. 141 (2002) -P.295-312.

24. Garey M.R. and Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco. 1979. -324 p.

25. P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting-stock problem (Part I). Oper. Res., 9. 1961. -P.849-859.

26. P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock problem (Part II), Operations Research 11. 1963. -P.863-887.

27. D.C. Johnson, A. Demers, J.D. Ullman, M.R. Garey, R.L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms // SIAM J. Comput. 1974. V.3. N.4. -P. 299-325.

28. J. Kupke, Losung von ganzzahligen Verschnittproblemen mit Branch-and-Price, Diplomarbeit, Universitat zu Koln, 1998.-100 p.

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

30. S. Martello and P. Toth. Knapsack Problems Algorithms and Computer Implementations. John Wiley & Sons, Chichester et al., 1990.-178 p.

31. E.A.Mukhacheva, V.A. Zalgaller. Linear programming cutting problems. International journal of software engineering and knowledge engineering. Vol. 3. N4 1993. -P. 463-467.

32. A. Mtiller. Anwendung der Polyedertheorie auf das eindimensionale Zuschnittproblem. Diplomarbeit, TU Dresden, Mathematik, 1998.-122 p.

33. G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. John Wiley & Sons, New York, 1988. -657 p.

34. T.A.J. Nicholson, Finding the shortest route between two points in a network, Computer Journal 9. 1966. -P.275-280.

35. C. Nitsche, G. Scheithauer, and J. Terno. Tighter relaxations for the cutting stock problem. EJOR, 112/3. 1999. -P.654-663.

36. J. Riehme. Guillotine-Zuschnittprobleme mit extrem unterschiedlichen Stiickzahlforderungen. Diplomarbeit, TU Dresden, Mathematik, 1994.-154 p.

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

38. G. Scheithauer and J. Terno. A branch-and-bound algorithm for solving one-dimensional cutting stock problems exactly. Applicationes Mathematicae, 23(2), 1995. -P.151-167.

39. G. Scheithauer and J. Terno. Facet-defining inequalities for the cutting stock problem. Technical Report MATH-NM-10-1997, TU Dresden, 1997.-28 p.

40. G. Scheithauer and J. Terno. Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problems. Oper. Res. Lett., 20, 1997. -P.93-100.

41. G. Scheithauer, J. Terno, A. Miiller and G. Belov. Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm. Journal of the Operational Research Society 52, 2001. -P.1390-1401.

42. A. Scholl, R. Klein, C. Jurgens. BISON: A fast hybrid procedure for exactly solving the one-dimensional bin-packing problem. Computers and Ops.Res. Vol. 24, No 7, 1997. -P.627-645.

43. P. Schwerin, G. Wascher, A new lower bound for the bin-packing problem and its integration to MTP, Pesquisa Operacional 19 (2) 1999. -P.lll-130.

44. P. Schwerin, G. Wascher, The bin-packing problem: a problem generator and some numerical experiments with FFD packing and MTP. In: International Transactions in Operational Research, 4, N 5/6, 1997. -P. 377-389.

45. J. Terno, R. Lindemann, G. Scheithauer. Zuschnittprobleme und ihre praktische Losung. Verlag Harri Deutsch Thun und Frankfurt/Main, 1987.210 p.

46. P. Vance, Branch-and-price algorithms for the one-dimensional cutting stock problem, Computational Optimization and Applications 9 (3) 1998. -P.212-228.

47. F. Vanderbeck, Computational study of a column generation algorithm for bin packing and cutting stock problems, Mathematical Programming 86 (Ser.A) 1999. -P.565-594.

48. G. Wascher and T. Gau. Heuristics for the one-dimensional cutting stock problem: A computational study. OR Spektrum, 18, 1996. -P.131-144.