Моделирование и решение задачи одномерного раскроя материала различных длин методом отсекающих плоскостей тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Белов, Глеб Николаевич

• Белов, Глеб Николаевич
• кандидат технических наук
• 2003

Оглавление диссертации кандидат технических наук Белов, Глеб Николаевич

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

Введение

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 в литературе, поэтому для этого случая было сделано сравнение производительности. Для случая нескольких длин произведено сравнение по эвристикам. Поведение алгоритма было задокументировано на представительном наборе задач.

Список литературы диссертационного исследования кандидат технических наук Белов, Глеб Николаевич, 2003 год

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.