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

СПИСОК ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОРТОГОНАЛЬНОЙ УПАКОВКИ И РАСКРОЯ.

1.1. Основные модели упаковки и раскроя.

1.2. Обзор методов решения задач одномерной, двухмерной и трехмерной упаковки и раскроя.

1.2.1. Использование методов математического программирования.

1.2.2. Применение методов комбинаторной оптимизации.

1.2.3. Приближенные и эвристические методы.

1.2.4. Вероятностные методы локального поиска оптимума.

Выводы по первой главе.

Задачи, решаемые в диссертационной работе.

ГЛАВА 2. КОНСТРУКТИВНЫЙ МЕТОД ДИНАМИЧЕСКОГО ПЕРЕБОРА ДЛЯ РЕШЕНИЯ ЗАДАЧ ОРТОГОНАЛЬНОЙ УПАКОВКИ.

2.1. Метод динамического перебора для решения задачи одномерной упаковки.

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

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

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

2.3. Метод динамического перебора для решения задачи параллелепипедной упаковки.

Выводы по второй главе.

ГЛАВА 3. КОНСТРУКТИВНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ПРЯМОУГОЛЬНОЙ УПАКОВКИ НА БАЗЕ МЕТАЭВРИСТИКИ МУРАВЬИНОЙ КОЛОНИИ.

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

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

Выводы по третьей главе.

ГЛАВА 4. НЕКОТОРЫЕ ЭВРИСТИЧЕСКИЕ МЕТОДЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО И ГИЛЬОТИННОГО РАСКРОЯ.

4.1. Метод перебора с усечением для решения задач одномерной упаковки.

4.2. Метод на базе процедур алгоритма имитация отжига для решения задач прямоугольного гильотинного раскроя.

4.3. Практическое применение метода перебора с усечением и метода на базе процедур имитации отжига.

Выводы по четвертой главе.

ГЛАВА 5. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ И АНАЛИЗ РАЗРАБОТАННЫХ МЕТОДОВ УПАКОВКИ И РАСКРОЯ.

5.1. Анализ и выбор методик исследования предлагаемых алгоритмов упаковки и раскроя.

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

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

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

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

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

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

Выводы по пятой главе.

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

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

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

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

Фундаментальные научные результаты в области решения задач раскроя в условиях массового производства принадлежат JI.B. Канторовичу и В.А. Залгал-леру. Результаты дальнейших исследований в этой области отражены в работах В.А. Булавского и М.А. Яковлевой, Э.А. Мухачевой, И.В. Романовского, В.А.

Кузнецова, а за рубежом П. Гилмори и Р. Гомори, И. Терно и Г. Шайтхауэра и др.

Задачи раскроя и упаковки, ориентированные на единичное производство, относятся к классу М>-трудных задач комбинаторной оптимизации, т.е. для их решения нет методов и алгоритмов, находящих точное решение за полиномиальное время. Существующие точные методы решения задач упаковки и раскроя основаны на схеме полного перебора, поэтому они оказываются мало пригодными для решения задач, встречающихся на практике. Асимптотически точные методы решения задачи одномерной и двухмерной упаковки разработаны Э.Х. Гимади, В.В. Залюбовским и другими авторами.

В связи с /^-трудностью задач раскроя-упаковки одним из актуальных направлений исследований в настоящее время является разработка эффективных приближенных и эвристических методов. Среди них выделяются конструктивные методы, решение задачи строится покомпонентно, добавлением нового компонента к частично построенному решению до тех пор, пока оно не построено полностью и методы локального поиска оптимума, поиск локально оптимальных решений ведется в некоторой окрестности допустимого решения. Разработке эвристических методов локального поиска оптимума при решении задач упаковки и раскроя посвящены работы М. Дориго, И.П. Норенкова, Ю.А. Кочетова, Э.А. Мухачевой, Э. Фолкенауэра Э. и др.

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

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

Цель и задачи исследования

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

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

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

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

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

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

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

Методы исследования

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

Основные научные результаты, полученные автором и выносимые на защиту

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

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

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

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

5. Математическое и программное обеспечение, реализующее разработанные конструктивные методы и позволяющее решать задачи «-мерной упаковки (,п = 1,2,3), возникающие в условиях единичного производства. Результаты анализа эффективности разработанного математического обеспечения для решения задач одномерной, прямоугольной и параллелепипедной упаковки, полученные на базе численного эксперимента.

Научная новизна результатов

1. Разработана теоретическая база создания нового унифицированного метода высокой эффективности для решения задачи ортогональной «-мерной упаковки («=1,2,3).

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

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

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

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

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

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

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

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

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

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

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

• методического, алгоритмического и программного обеспечения решения задач поиска оптимальных решений упаковки и раскроя промышленных объектов, позволяющего сократить в 1,5-2 раза сроки подготовки оптимальных решений при упаковке и раскрое и повысить показатели эффективности при решении задачи ресурсосбережения на 5-10%.

Результаты диссертационной работы внедрены в виде методов, алгоритмов, методик и программного обеспечения на ООО «Уралтехнопроект» (г. Екатеринбург), ООО «ВИВ-ФАРМ» (г. Москва), ГУП УАП «Гидравлика» (г. Уфа), а также в учебном процессе Уфимского государственного авиационного технического университета.

Связь исследований с научными программами

Исследования проводились в рамках научных проектов №01-01-00510, №0301-07002 Российского Фонда Фундаментальных исследований. Апробация работы

Основные научные и практические результаты диссертации докладывались и обсуждались на следующих конференциях:

• Международной научно-технической конференции «Актуальные проблемы математического моделирования и автоматизированного проектирования в машиностроении: МОДЕЛЬ-ПРОЕКТ 95», Казань, 1995;

• Конференции «Комплексный анализ, дифференциальные уравнения, численные методы и приложения. Геометрические задачи», Уфа, ИМВЦ РАН,

I 1996;

• 1-Й Сибирских конгрессах по прикладной и индустриальной математике (ИНПРИМ-96,98), Новосибирск, 1996,1998;

• 16-ой Европейской конференции по исследованию операций, Брюссель, Бельгия, 1998;

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

• Международной конференции «Поддержка жизненного цикла в производственных системах», Бремен, Германия, 1998;

I • Конференции «Математическое программирование и приложения», УрО

РАН, Екатеринбург, 1999,2003;

• Первой Всероссийской научно-практической конференции по вопросам решения оптимизационных задач в промышленности «Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования», С-Петербург, 2001;

• Международной конференции «Дискретный анализ и исследование операций» (DAOR), Новосибирск, 2000, 2002, 2004;

• 16-ой международной конференции по исследованию операций, Эдинбург, Великобритания, 2002;

• Международной конференции «Компьютерные науки и информационные технологии» (CSIT), Уфа, 2003-2005;

• 13-й Байкальской международной школе-семинаре, Иркутск, 2005;

• Международной уфимской зимней школе-конференции по математике, Уфа, 2005;

• Международном семинаре европейской группы по раскрою и упаковке (EuroSICUP), Порто, Португалия, 2006;

• III Всероссийская конференция «Проблемы оптимизации и экономические приложения», Омск, 2006.

Публикации

Результаты диссертационной работы отражены в 80 публикациях, в том числе в одной монографии (в соавторстве), учебном пособии (в соавторстве), 31 статье, в том числе 8 статьях в изданиях из списка ВАК, 40 материалах международных и российских конференций, 2 свидетельствах государственной регистрации программ для ЭВМ.

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

Диссертация состоит из введения, пяти глав основного материала, библиографического списка и содержит 265 страницы основного текста. Библиографический список включает 191 наименование литературы.

Выводы по пятой главе

На основании проведенных численных экспериментов в работе сделаны следующие выводы:

1. Для задачи одномерной упаковки на рассматриваемых тестовых наборах из библиотеки тестовых задач OR-library при проведении эксперимента для тестовых наборов «средние предметы» алгоритмы ST и HGGA решили оптимально практически все задачи, алгоритм DSR решил оптимально 64% задач. Для тестовых наборов «триплеты» алгоритм ST решает оптимально практически все задачи, алгоритм DSR - 68% задач, HGGA решил оптимально только две задачи из 80.

2. Для задачи прямоугольной упаковки в полосу результаты эксперимента показали, что на наборах «средние предметы» коэффициент раскроя КРА, полученный методом DSR, составил КРА от 98% до 99% и превышает коэффициент раскроя сравниваемых методов на 6-16%; на наборах «малые предметы» результаты DSR (КРА от 92% до 96%) также превышают КРА сравниваемых методов на 4-14%; на наборах «малые и большие предметы» метод DSR (КРА от 92% до 94%) уступает алгоритму GCA&.BD примерно на 1%. Для тестовых примеров большой размерности лучшие результаты алгоритмом DSR были получены в классе «средние предметы», при этом КРА составил от 95.58% до 99.58%.

3. При тестировании алгоритма муравьиной колонии АСР анализ результатов

N-A экспериментов показал, что средние отклонения //(%) =-х 100% решений N, т полученных алгоритмом АСР для трех типов тестовых задач от нижней границы Л , составляют: для задач первого типа ц =2.88 %; для задач второго типа //=2.33 %; для задач третьего типа //=1.59 %. Алгоритм АСР показал лучшие результаты для задач второго и третьего типа. При увеличении количества итераций наблюдались улучшения решений для АСР, однако время решения индивидуальной задачи заметно увеличивалось.

4. При тестировании алгоритмов параллелепипедной упаковки в классах «мелкие» и «разнородные предметы» лучшие результаты показали МБА, GABD и EABD соответственно. Классы с «мелкими предметами» наиболее эффективно были решены алгоритмами МБА, GABD. В классах, где имелись предметы со «средними» и «разнородными предметами», лучшим был алгоритм МБА (КРА -от 75% до 90%.), а в классе «мелкие предметы» - алгоритм GABD.

Предложенные методы и алгоритмы для решения задачи ортогональной п-мерной упаковки ВРР (п= 1,2,3) инвариантны к технологическим ограничениям, возникающим в единичном производстве. Предложенные методы решения задачи одномерной упаковки применялись при решении задачи «Использование отходов по цехам» (ГУП УАП «Гидравлика»), что позволяет обеспечить экономию материалов и сокращение сроков при проектировании планов упаковки деталей в составе автоматизированного рабочего места технолога планово-заготовительного производства. Предложенные методы решения задачи параллелепипедной упаковки применялись при упаковке железнодорожных платформ и вагонов разногабаритными ящиками (ООО «Уралтехнопроект», ОАО «Урал-химмаш»), а также при размещении ящиков с медикаментами и изделиями медицинского назначения на фармацевтическом складе (ООО «ВИВ-ФАРМ»).

ЗАКЛЮЧЕНИЕ

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

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

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

2. Разработан высокоэффективный конструктивный метод динамического перебора для решения задач одномерной и прямоугольной упаковки в детерминированном и рандомизированном вариантах, основанный на декомпозиции задачи на множество задач 0-1 рюкзак. Этот метод послужил основой унификации решения задач ортогональной упаковки. Данный метод для задачи одномерной упаковки показывает лучшие результаты в трудном классе задач «средние предметы» по сравнению с другими методами. При решении задач прямоугольной упаковки по сравнению с классическими генетическими алгоритмами рандомизированный метод динамического перебора превосходит их на классах "средние предметы" и "малые предметы" (коэффициент раскроя от 96.4% до 99.4%). Для очень трудных задач (триплетов) прямоугольной упаковки коэффициент раскроя предлагаемого метода составляет от 96.54% до 100%. Разработанные алгоритмы на основе этого метода позволяют сократить отходы материала в 2-3 раза. Показана эффективность применения метода динамического перебора для решения задачи упаковки параллелепипедов. Разработанные методы параллелепи-педной упаковки на базе метода динамического перебора по сравнению с эволюционными алгоритмами позволяют улучшить коэффициент раскроя, а, следовательно, и коэффициент использования материала в классах «средние предметы» и «разнородные предметы» (до 5%-15%). Кроме того, метод динамического перебора позволяет получать множество квазиоптимальных решений исходной задачи, что позволяет в случае необходимости выбирать лучшее приемлемое решение с учетом технологических ограничений.

3. Разработан эффективный конструктивный метод перебора с усечением на базе перебора различных вариантов упаковки путем обмена предметов между контейнерами, что позволяет получать рациональные решения задачи одномерной упаковки контейнеров без ограничений на размерность задачи с минимальными затратами времени. Данный метод для решения задачи одномерной упаковки превосходит тестируемые методы по времени вычислений, причем его результативность (достижение оптимума) близка к 100% при количестве предметов от 20 до 1000 практически на всех классах задач. Рандомизированный метод динамического перебора превосходит результаты метода перебора с усечением лишь на наборах "средние предметы".

4. Разработан эффективный метод решения задач прямоугольной упаковки на базе конструктивной метаэвристики муравьиной колонии, успешно применяемой для решения задач комбинаторной оптимизации. Как показал численный эксперимент, проведенный на тестовых примерах из электронной библиотеки тестов для решения трудных задач комбинаторной оптимизации, отклонение решений от нижней границы составило в среднем 2,23%. Однако этот метод требует больших затрат времени и поэтому значительно уступает методу динамического перебора. Разработаны эвристические алгоритмы с применением процедур метаэвристики имитация отжига для решения задач гильотинного прямоугольного раскроя, что позволяет получить рациональные решения для раскроя промышленных материалов в условиях единичного производства. Лучшие результаты по сравнению с тестируемыми методами, были получены в классах «большие предметы», «мелкие предметы», «триплеты» (КРА от 90.93% до 98.08%).

5. Предложенные в работе теоретические положения для решения задач упаковки и раскроя промышленных объектов в условиях единичного производства реализованы в виде методик, алгоритмов и прикладного программного обеспечения в среде программирования Borland Delphi 3.0. Разработанное программное обеспечение имеет развитый интерфейс и может использоваться как автономно, так и в составе комплексов программ упаковки и раскроя. Результаты диссертационной работы приняты к внедрению в виде алгоритмов, методик и программного обеспечения на ООО «Уралтехнопроект» (г. Екатеринбург), ООО «ВИВ-ФАРМ» (г. Москва), ГУП УАП «Гидравлика» (г. Уфа). Полученные в работе результаты используются в Уфимском государственном авиационном техническом университете в учебном процессе при выполнении курсовых и дипломных работ, в исследованиях аспирантов, а также отражены в учебном пособии, рекомендованном УМО по образованию в области экономики, статистики, информационных систем и математических методов.

1. Аккуратов Г.В., Березнев В.А., Брежнева О.А. О методе решения уравнения с булевыми переменными // Принятие решений в условиях неопределенности. Межвузовский научный сборник. Уфа: УАИ. 1990. С. 145-154.

2. Батищев Д.Ю. Генетические алгоритмы решения экстремальных задач // Учебн. пособие под ред. Я.Е.Львовича. Воронеж: Воронежский гос. техн. ун-т, Нижегородский ун-т. 1995. 96 с.

3. Борисовский П.А., Еремеев А.В. О сравнении некоторых эволюционных алгоритмов//Автоматика и телемеханика. 2004. №З.С. 3-9.

4. Булавский В.А., Яковлева М.А. О решении задач оптимального раскроя линейных материалов на ЭВМ // Математические методы в технико-экономических расчетах: Материалы научного совещания. Т. IV. М.: АН СССР. 1961. С. 83-87.

5. Бухвалова В.В. Задача прямоугольного раскроя: метод зон и другие алгоритмы // С.Петербург: Государственный университет. 2001.

6. Валеева А.Ф. Алгоритм построения прямоугольной упаковки и применение его к задаче фигурного раскроя II Труды международной конференции по прикладной и индустриальной математике, Новосибирск, ИМ СО РАН, 1997. С.23-30.

7. Валеев С.С., Валеева А.Ф. Программа плотной упаковки прямоугольных объектов. Свидетельство об официальной регистрации программы для ЭВМ №940280 от 11.07.1994. РосАПО.

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

9. Валеева А.Ф. Методы частичного перебора локального поиска оптимума в задаче двухмерной упаковки // Информационные технологии. 2004. № 1. С. 36-43.

10. Валеева А.Ф. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки // Информационные технологии. 2005. № 10. С. 3643.

11. Валеева А.Ф. Стохастические методы локального поиска для задач упаковки // Труды международной конференции «Моделирование, вычисления, проектирование в условиях неопределенности-2000». УГАТУ. 2000. С.25-31.

12. Валеева А.Ф. Конструктивная эвристика для задачи прямоугольной упаковки // Вестник Башкирского университета. 2006. № 3. С. 5-6.

13. Валеева А.Ф. Конструктивные эвристики в задачах раскроя-у паковки // Труды «Международной уфимской зимней школы-конференции по математике и физике для студентов, аспирантов и молодых ученых». Т. 1. Математика. Уфа. 2005. С. 109-119.

14. Валеева А.Ф., Мухаметзянов Р.З, Тихомиров С.К, Юлдыбаева Ж.Л. Алгоритмы решения задачи плотной упаковки геометрических объектов // Принятие решений в условиях неопределенности. Межвузовский научный сборник. Уфа. 1996. С.23-28.

15. Валеева А.Ф. Алгоритм построения прямоугольной упаковки и применение его к задаче фигурного раскроя // Труды международной конференции по прикладной и индустриальной математике. Новосибирск, ИМ СО РАН. 1997. С.47-57.

16. Валеева А.Ф., Тоцков И.Е, Гареев И.Р. Методы решения задачи прямоугольной упаковки // Интеллектуальное управление в сложных системах 99: Труды респ. науч.-техн. конф. Уфа. 1999. С.36-38.

17. Валеева А.Ф, Гареев И.Р, Габитов В.А. Метод динамического перебора для решения задачи одномерной упаковки // Моделирование, вычисления,проектирование в условиях неопределенности 2000: Тр. междунар. науч. конф. Уфа. 2000. С. 369-373.

18. Валеева А.Ф., Гареев И.Р. Задача одномерной упаковки: вычислительный эксперимент с методом динамического перебора // Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа. 2000. С.74-79.

19. Валеев С.С., Валеева А.Ф., Чуен Лин. Оптимальное планирование работ в вычислительных системах реального времени. Международное научное издание «Интеллектуальные автономные системы»: УГАТУ. Уфа, Карлсруе. 1996. С. 135-139.

20. Валеева А.Ф., Тоцков И.Е. Решение задачи трехмерной упаковки // Комплексный анализ, дифференциальные уравнения, численные методы и приложения. Геометрические задачи. Уфа: ИМВЦ УИЦ РАН. 1996. С. 30-36.

21. Валеева А.Ф., Тоцков И.Е. Разработка методов трехмерной упаковки // Международное научное издание «Проблемы принятия решений в условиях неопределенности». Уфа. 1997. С. 198-206 (на англ. языке).

22. Валеева А.Ф., Валеев С.С. Получение множества квазиоптимальных решений в задаче рационального использования ресурса / Труды межд. конф. «Поддержка жизненного цикла в производственных системах». Уфа. 1998. С. 125-127 (на англ. языке).

23. Валеева А.Ф. Стохастические методы локального поиска для задач упаковки // Труды международной конференции «Моделирование, вычисления, проектирование в условиях неопределенности-2000». УГАТУ. 2000. С. 25-31.

24. Валеева А.Ф., Аглиуллин М.Н. Алгоритм муравьиной колонии для задачи двухмерной упаковки: численный эксперимент // Труды межд. конф. «Компьютерные науки и информационные технологии». Уфа. 2003. С. 110-114 (на англ. языке).

25. Валеева А.Ф., Поляковский С.Ю. Классы нижних границ для задач двухмерной упаковки // Труды межд. конф. «Компьютерные науки и информационные технологии». Уфа. 2005. С. 152-158 (на англ. языке).

26. Валеева А.Ф., Аглиуллин М.Н. Моделирование прямоугольной упаковки на базе метаэвристики муравьиной колонии // Межвузовский научный сборник «Принятие решений в условиях неопределенности». Уфа. Вып.2. 2005. С. 55-63.

27. Валеева А.Ф., Аглиуллин М.Н. Алгоритмы муравьиной колонии для задач двухмерной упаковки: результаты численного эксперимента // Труды 13-й Байкальской международной школы-семинара. Математическое программирование. Том 1. 2005. С. 429-443.

28. Валеева А.Ф. Конструктивные эвристики в задачах раскроя-упаковки // Труды «Международной уфимской зимней школы-конференции по математике и физике для студентов, аспирантов и молодых ученых». Т.1. Математика. Уфа. 2005. С. 109-119.

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

30. Верхотуров М.А. Задача нерегулярного раскроя плоских геометрических объектов: моделирование и расчет рационального раскроя // Информационные технологии. 2000. № 5. С. 37-42.

31. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982. 416 с.

32. Гимади Э.Х, Залюбовский В.В. Задача упаковки в контейнеры: асимптотически точный подход // Известия вузов. Математика. 1997. № 12. С. 25-33.

33. Гимади Э.Х, Залюбовский В.В, Шарыгин П.И. Задачи упаковки в полосу: асимптотически точный подход // Известия высших учебных заведений. Математика. №12(427). 1997. С. 34-44.

34. Гончаров Е.Н, Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискретный анализ и исследование операций. 1999. Серия 2. 6. №1. С. 12-32.

35. Грицюк Ю. Регулярне размщувания прямокутних объеьспв вздовж смуг односиоронньо обмежено! стр1чки // Льв1в. УкрДЛТУ. 2002. 220с.

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

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

38. Кокотов В.З. Алгоритм плотного размещения разногабаритных элементов на плате // Информационные технологии. 1998. №11. С. 16-21.

39. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сибирский журнал исследования операций. 1994. № 2. С. 18-39.

40. Кочетов Ю, Младенович Н, Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет, анализ и исслед. операций. Сер. 2. 2003. Т. 10. № 1. С. 11-43.

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

42. Кофман А. Введение в прикладную комбинаторику. М.: Наука, Гл. ред. физ.-мат. лит. 1975. 447 с.

43. Леванова Т.В., Лореш М.А. Алгоритмы муравьиной колонии и имитации отжига для задачи о р-медиане // Автоматика и телемеханика. 2004. №3. С. 80-89.

44. Лернер Э.Ю., Фазылов В.Р. Функция гильотинного размещения для набора прямоугольников // Исследования по прикладной математике. Казань: Унипресс. 1999. Выпуск 21. С. 187-196.

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

46. Липский В. Комбинаторика для программистов. М.: Мир. 1988. 213 с.

47. Мухачева Э.А., Валеева А.Ф., Мухачева А.С. Методы локального поиска в дискретных задачах оптимального распределения ресурса: Учеб. пособие. Уфа: УГАТУ. 2001. 103 с.

48. Мухачева А.С., Валеева А.Ф., Картак В.М. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. М.: МАИ. 2004. 193 с.

49. Мухачева Э.А., Валеева А.Ф. Метод динамического перебора в задаче двухмерной упаковки // Информационные технологии. 2000. №5. С. 3037.

50. Мухачева ЭЛ., Валеева А.Ф., Тоцков И.Е. Методы решения задачи параллелепипедной упаковки на базе алгоритма динамического перебора // Информационные технологии. 2001. №1. С. 21-29.

51. Мухачева Э.А., Валеева А.Ф., Картак В.М., Мухачева А.С. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур // Информационные технологии. Приложение. 2004. №5. 31с.

52. Мухачева Э.А., Валеева А.Ф., Филиппова А.С., Поляковский С.Ю. Задача двухмерной контейнерной упаковки: нижние границы и численный эксперимент с алгоритмами локального поиска оптимума // Информационные технологии. 2006. №4. С. 45-52.

53. Мухачева Э.А., Валеева А.Ф., Розанова Л.Ф., Тарасова Т.Д. Математическое обеспечение интеллектуальной системы поддержки решений в задачах плотной упаковки / Деп. в ВИНИТИ 06.06.95, № 1665. 10 с.

54. Мухачева Э.А., Валеева А.Ф., Мухачева А.С. Решение задач прямоугольной упаковки на базе ее блочной структуры // Труды межд. конф. «Компьютерные науки и информационные технологии». Уфа. 2000. С. 43-51 (на англ. языке).

55. Мухачева Э.А., Валеева А.Ф. Метод динамического перебора в задаче двухмерной упаковки // Информационные технологии. 2000. № 5. С. 3037.

56. Мухачева Э.А. Методы условной оптимизации в задаче рационального раскроя листового проката // Оптимизация: Сб. научн. трудов СО АН СССР. 1978. Вып. 22. С. 83-93.

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

58. Шабрина Л.М. К разработке линейного алгоритма решения задачи трехмерной упаковки // Математическое моделирование в решении научных и технических задач. Уфа. 1994. С. 3-5.

59. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов // Уфа: УГАТУ. 1998. 216 с.

60. Мухачева Э.А., Ермаченко А.И., Сиразетдинов Т.М., Усманова А.Р. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя//Информационные технологии. 2001. №6. С. 25-31.

61. Мухачева Э.А., Мухачева А.С., Чиглинцев А.В. Генетический алгоритм блочной структуры в задачах двухмерной упаковки // Информационные технологии. 1999. №11. С. 13-18.

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

63. Новожилова М.В. Решение задачи поиска глобального экстремума линейной функции цели на структуре линейных неравенств // Препринт. АН УССР. Ин-т проблем машиностроения. Харьков. 1988. 48 с.

64. Норенков И.П., Косачевский О.Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации // Информационные технологии. 1999. №2. С. 2-8.

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

66. Панюкова Т.А. Синтез программ управления процессом раскроя. // Обозрение прикладной и промышленной математики. Т.8. Вып.2 / Под ред. Прохорова Ю.В. М.: Научное изд-во «ТВП». 2001. 664с.

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

68. Поляковский С.Ю., Валеева А.Ф. и др. Программа решения задачи двухмерного прямоугольного раскроя материалов. Свидетельство об официальной регистрации программы для ЭВМ №2006612022 от 14.06.2006. Москва.

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

70. Романовский И.В. Пакетный вариант симплекс-метода. Эволюционное описание основных конструкций // Л.: Исследование операций и статистическое моделирование: Изд-во ЛГУ. 1979. Вып. 5. С. 55-71.

71. Романовский И.В. Решение задачи гильотинного раскроя методом переработки списка состояний//Кибернетика. 1969. №1. С. 102-104.

72. Романовский И.В., Христова Н.П. Решение дискретных минимаксных задач методом дихотомии // ЖВМ и МФ. 1973. 13(5). С. 1200-1209.

73. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. М.: ФИЗМАТЛИТ. 2002. 240с.

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

75. Тоцков И.Е., Валеева А.Ф. Метод отсечения для решения задачи трехмерной упаковки //Межвузовский научный сборник «Принятие решений в условиях неопределенности». Уфа. 1999. С. 112-118.

76. Хуббутдинов А.З., Аглиуллин М.Н., Валеева А.Ф., Никитин Ю.В. Применение алгоритмов локального поиска оптимума для проектирования СБИС // Труды межд. конф. «Компьютерные науки и информационные технологии». Уфа. 2005. С. 175-180 (на англ. языке).

77. Ant Colony Optimization / Dorigo M., Stutzle Т., MIT Press. 2004.

78. Aurts E, Lenstra J, edit. Local Search in Combinatorial Optimization // John Wiley&Sons. 1996.

79. Adamovicn A, Albano A. Nesting two-dimensional shapes in rectangular Modules // Comput. Aeded Design. 1976. 8(1). P.27-33.

80. Arenales M. and Morabito R. An overview of AND/OR-graph approaches to cutting and packing problems // Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa. 1997. P. 207-225.

81. Beasley J.E. An algorithm for solving large capacitated warehouse location problems // European Journal of Operational Research. 1988. N 33. P. 314325.

82. Baker B.S., Goffman Jr. E.G., Riverst R.L. Orthogonal packing in two dimensions// SIAM J. Comput. 9 (1980). P. 846-855.

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

84. Belov G. A branch-and price algorithm for one-and-two dimensional two-stage cutting (stock) problems. // Technical report MATH-NM-03-03. Dresden University. 2003. URL: www/math.tu-dresden.de/~capad.

85. Belov G, Scheithauer G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths // European Journal of Operational Research. 2002. N141. P. 274-294.

86. Berkey J.O, Wang P.Y. Two dimensional finite bin packing algorithms.// J. Oper. Res. Soc. 38 (1987). P. 423-429.

87. Bischoff E, Wascher G, edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1995. 84p.

88. Bischoff E.E, Marriott M.D. A comparative evaluation of heuristics for container loading // European Journal of Operation Research. 44(1990). P. 267-276.

89. С. Blum, A. Roli. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison//TR/IRIDIA/2001. 37 p.

90. Bortfeldt A., Gehring H. Applying tabu search to container loading problems // Operations Research Proceedings 1997. Springer. Berlin. 1998. P. 533-538.

91. Boschetti M.A. The Two-Dimensional Finite Bin Packing Problem // Quaterly Journal of the Belgian, French and Italian Operations Research Societies. 2002.

92. Bronshtein E.M. Rectangulars packing and planar graphs // The International Scientific Collection "Decision making under conditions of uncertainty (cutting -packing)problems. Ufa:USATU. 1997. P. 172-178.

93. Burke E., Kendall G. Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem // Accepted for the 1999 International Conference on Artificial Intelligence, Monte Carlo resort. Las Vegas. Nevada. USA. 1999.

94. Chazelle B. The bottom-left bin packing heuristic: An efficient implementation //IEEE Trans, on Comput. 2(1983). P. 697-707.

95. Chen P., Chen Y., Goel M., Mang F. Approximation of Two-Dimensional Rectangle Packing//CS270 Project Report. Spring 1999.

96. Chung F.K.R., Garey M.R., Johnson D.S. On packing two-dimensional bins // SI AM J. Algebraic Discrete Meth. 3 (1982). P. 66-76.

97. Coffman E., Garey M., Jchonson D. Approximation algorithms for bin packing an updated survey // Algorithm Design for Computer System Design (Ausiello G., Lucertini M., Serafini P.eds) Berlin etal. N1. 984 p.

98. Coffman E.G. Jr., Garey M.R., Johnson D.S., Tarjan RE. Performance bounds for level-oriented two-dimensional packing algorithms // SIAM J. Comput. 9(1980). P. 801-826.

99. Colorny A., Dorigo M., Maniezzo V., Trubian M. Ant system for jobshopscheduling // Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL). N34. 1994. P. 30-39.

100. Dell'Amico M., Martello S. and Vigo D. A Lower Bound for the Non-Oriented Two-Dimensional Bin Packing Problem. Elsevier science B.V. 2001.

101. Diegel A. Integer LP solution for large trim problems. // University of Natal. South Africa. Working Paper. 1988.

102. Dorigo M., Di Caro G., Gambardella L.M. Ant Algorithms for Discrete Optimization//Artificial Life. 1999. Vol.5. N3. P. 137-172.

103. Dorigo M., Gambardella L.M. Ant Colonies for the traveling salesman problem// BioSystems. N 43. 1997. P. 73-81.

104. Dorigo M., Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation. 1997. Vol.1. N1. P. 53-66.

105. Dousland K.A., Dousland W.B. Packing problems. // European Journal of Operational Research. 1992. N56. P. 2-14.

106. Dyckhoff H., Scheithauer G., Terno J. Cutting and Packing // Annotated Bibliographies in Combinatorial Optimization, edited by M.Dell'Amico, F.Maffioli and S.Martello. John Wiley&Sons. 1997. P. 393-412.

107. Dykhoff H. A typology of cutting and packing problems // Evropean Journal of Operational research. 1990. Vol. 44. P. 145-159.

108. Dykhoff H., Wascher G., edit. Special issue: Cutting and Packing // European Journal of Operational Research. 1990. 44(2).

109. Eley M. Solving container loading problems by block arrangement // European Journal of Operational Research. 2002. N141. P. 393-409.

110. Gambardella L.M., Taillard E.D., Dorigo M. Ant colonies for the QAP // Journal of the Operational Research Society (JORS), 50(2). 1999. P. 167-176.

111. Faroe O., Pisinger D., Zachariasen M. Guided local search for the three-dimensional bin packing problem // Tech. Rep. 99/13, DIKU, University of Copenhagen, Denmark. Dept. of Computer Science: University of Copenhagen.

112. Fekete S.P., Schepers J. New Classes of Fast Lower Bounds for Bin Packing Problems. Technical report. № 97.265a. Angewandte Mathematik und Informatik Universitat zu Koln. 1998.

113. Fekete S.P., Schepers J. A new exact algorithm for general orthogonal d-dimensional knapsack problems. In Algorothms-ESA'97. Springer Lecture Notes in Computer. Science. D-10623. Berlin. Germany(1997), revised (2000).

114. Folkenauer E. A hybrid Grouping Genetic Algorithm for Bin Packing // Journal of Heuristics. 1998. 2(1). P. 5-30.

115. Folkenauer E. Tapping the full power of genetic algorithm through suitable representation and local optimization: Application to bin packing // Evolutionary Algorithms in Management Applications. Berlin. 1995. P. 167182.

116. Forster H., Wascher G. (1997) Simulated annealing for order spread minimization sequencing cutting patterns // European Journal of Operational Research. 1998. N110. P. 272-281.

117. Frenk J.B., Galambos G.G. Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem // Computing. 39 (1987). P. 201-217.

118. Gehring H., Bortfeld A. A Genetic Algorithm for Solving the Container Loading Problem // International transactions in operational research. 1997. V.4. №5/6. P. 401-418.

119. Gilmore P., Gomory R. Multistage cutting stock problem of two and more dimensions// Operat.Res. 1965. 13(1). P. 94-120.

120. Gilmore P., Gomory R. The theory and computation of knapsack functions. // Oper.Res. 1966. V.14. P. 1045-1075.

121. Gilmore P.C. and Gomory R.E. A Linear Programming Approach to the Cutting-stock Problem, Operations Research. 9(1961). P. 849-859.

122. Glover F. Tabu search and adaptive memory programming advances, applications and challenges // Interfaces in Computer Science and Operations Research. 1996. P. 1-75.

123. Hifi M. Exact algorithms for the guillotine strip cutting/packing problem // Computers and Operations Research. 1998. N25. P. 925-940.

124. Hinxman A. The Trim-Loss and assortment problems: a survey // European Journal of Operational Research. 1980. N11. P. 863-888.

125. Holthaus O. Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard of lengths // European Journal of Operational research. 2002. N141. P.295-312.

126. Hopper E., Turton B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. // EJOR. N 128. 2001. P. 3457.

127. Imahori S., Yaguira M., Ibaraki T. Local Search Heuristics for the Rectangle Packing Problem With General Spatial Costs // MIC'2001 4th Metaheuristics International conference. P. 471-476.

128. Johnson D.S. Near-optimal bin packing algorithms // PhD Thesis. MIT: Cambridge. 1973.

129. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing //Science. V. 220. 1983. P. 671-680.

130. Keller H., Kotov V. An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing // Operations Research Ketters. V.31. N 1. 2003.

131. Kochetov Yu., Usmanova A. Probabilistic Tabu Search with Exponential Neighborhood for Bin Packing Problem // Proceedings MIC'2001. Porto. 2001. P. 619-624.

132. Laguna M, Glover F, Bandwing Packing: A Tabu Search Approach // Management Science. Vol. 39. № 1. P. 36-81.

133. J. Levine and F. Ducatelle. Ant Colony Optimization and Local Search for Bin Packing and Cutting Stock Problems// Proceedings of the 4-th Metaheuristics International Conference MIC'2001. Porto. July 16-20. 2001.

134. HO.Lirov Y, edit. Special issue: Geometric Resource Allocation // Mathematical and Computer Modeling. 1995. 16(1).

135. Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. // European Journal of Operation Research. 1999. N112. P. 413-420.

136. Lodi A, Martello S, Vigo D. Heuristic algorithms for the three-dimensional bin packing problem // European Journal of Operational Research. 2002. N 141. P. 410-420.

137. Lodi A, Martello S, Vigo D. Recent advances on two-dimensional bin packing problems.//Discrete Applied Mathematics 123. 2002. P. 379-396.

138. Lodi A, Martello S, Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems Algorithms // INFORMS J. Comput. 11 (1999). P. 345-357.

139. Loris Faina. An application of simulated annealing to the cutting stock problem // European Journal of Operational Research. 1999. N 114. P. 532556.

140. Marcotte O. The cutting stock problem and integer rouding. // Math.Program. 1985. N33/1. P. 82-92.

141. Marcotte O. The cutting stock problem and integer rounding // Math. Program. 1985. N33(1). P. 82-92.

142. Martello S, edit. Special issue: Knapsack, Packing and Cutting, Part II: Multi Dimensional Knapsack Problem. // INFOR. 1994. N 32(3).

143. Martello S, edit. Special issue: Knapsack, Packing and Cutting, Part I: One Dimensional Knapsack Problem. // INFOR. 1994. N 32(4).

144. Martello S., Toth P. Knapsack problems: Algorithms and Computer Implementations. // YOHN WILEY&SONS. Chichester. 1990.

145. Martello S., Vigo D. Exact solution of two-dimensional finite bin packing problem//Management Science. 1997. N35. P.64-68.

146. Morabito M., Arenales M. Staged and constrained two-dimensional guillotine cutting problems: an and/or-graph approach. // European Journal of Operational Research. 1996. N94. P.548-560.

147. Morabito R., Arenales M. An AND/OR graph approach to the container loading problem // International Transactions in Operational Research. N 1. 1994. P. 59-73.

148. Mukhacheva E., edit. Special issue: Decasion Making under Conditions of Uncertainty (Cutting-Packing Problems)/ The International Scientific Collection. 1997. Ufa. Russia.

149. Mukhacheva E.A., Zalgaller V.A. Linear Programming Cutting Problems // International Journal of Software Engineering and Knowledge Engineering. 1993. V.3. N4. P. 463-476.

150. Murata H., Fujiyoshi K., Nakatane S. and Kajitani Y. Rectangle-Packing-Based Module Placement // Proc. IEEE/ACM International Conf. on Computer-Aided Design. 1995. P. 472-479.

151. Nitsche C., Scheithauer G., Terno J. New cases of the cutting stock problem having MIRUP //Math. Meth. Oper. Res. 1998. Vol.48. P. 105-115.

152. Pisinger D. Heuristics for the container loading problem // European Journal of Operational Research. 2002. N141. P. 382-392.

153. Reeves C.R. Genetic Algorithms for the Operations Researcher // INFORMSJ on Computing. 1997. Vol.9. №3. P. 231-250.

154. Sakanushi К., Kajitani Y. The Quarter-State (Q-sequence) to Represent the Floorplan and Applications to Layout optimization // IEEE Asia Pacific Conference on Circuits and systems. 2000. P.829-832.

155. Scheithauer G. and Terno J. A Branch-and-Bound Algorithm for Solving One-dimensional Cutting Stock Problems Exactly, Applicationes Mathematicae. 1995. P.151-167.

156. Scheithauer G. and Terno J. About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem. Oper. Res. Proc. 1991: Springer-Verlag. Berlin. P. 439-444.

157. Scheithauer G. and Terno J., Theoretical Investigations on the Modified Integer Roundup Property for the One-dimensional Cutting Stock Problem. Operations Research Letters. N 20. 1997. P. 93-100.

158. Scheithauer G., Terno Y. Muller A., Lindeman R. Zuschnitprobleme und ihre prakti-sche Losung. Leiprig. 1987. P.207.

159. Scholl A., Klein R., Juergens G. BISON: A fast hybrid procedure for exactly solving the one-dimensional Bin-Packing Problem. // Computers and Operational Research. 1997. 24(7). P. 627-645.

160. Schwerin P., Wascher G. A New Lower Bound for the Bin-Packing Problem and its integration to MTP//Pesquisa Operational. 1999. 19(2). P.l 11-131.

161. Schwerin P., Wascher G. The Bin-Packing Problem: a Problem Generator and Some Numerical Experiments with FFD Packing and MTP 11 International Transactions in Operational Research. 1997. N4. P.337-389.

162. Sergeyeva O.Y., Scheithauer G. and Terno J. The value correction method for packing of irregular shapes // Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa. 1997. P. 261-270.

163. Soma N., Toth P. On the Critical Item for Subset Sum Problems // Pesquisa Operacional. 1999. 19(2). P. 279-285.

164. Stoyan Yu., Novozhilova M. Non-guillotine Placement of Rectangles into a Strip of Given Width // Pesquisa Operational. 1999. 19(2). P. 189-211.

165. Stoyan Yu., Pankratov A. Regular packing of congruent polygons on the rectangular sheet. // European Journal of Operational Research. 1999. N 113. P. 653-675.

166. Stiitzle Т., Hoos H.H. MAX-MIN Ant System and Local Search for the Traveling Salesman Problem // Proceedings of the IEEE International Conference on Evolutionaiy Computation (ICEC'97). 1997. P. 309-314.

167. Stiitzle Т., Hoos H.H. MAX-MIN Ant System // Future Generation Computer Systems. 2000. № 16. P. 889-914.

168. Takahashi T. A New Encoding Scheme for Rectangle Packing Problem // Graduate School of Science and Technology. Niigata University. IEEE. 2000. P. 175-178.

169. Tarnowski A.G. Advance polynomial time algorithm for guillotine generalized pallet loading problem // Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection. Ufa. 1997. P. 93-125.

170. Tarnowski Т., Terno J., Scheithauer G. A polynomial time algorithm for the guillotine pallet loading problem. INFOR32. 1994. P. 275-287.

171. Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische Losung. Leipzig. 1987.

172. Umatani S., Jagiura M., Ibaraki T. One-dimensional cutting stock problem to minimize the number of different patterns // European Journal of Operational Research. 2003. V. 146. N 2.

173. Valerio de Carvalho J.M. LP models for bin packing and cutting stock problems // Eur. Jour, of Oper. Res. N 141. 2002. P. 253-273.

174. Valeyeva A.F., Valeyev S.S. Method of dynamic sorting and neuralnetworks applied for rational use problem solution // The International Scientific Collection

175. Decision making under conditions of uncertainty (cutting-packing ) problems. Ufa: USATU. 1997. P. 188-198

176. Valeyeva A.F., Totskov I.E. Development of three-dimensional packing methods // The International Scientific Collection «Decision making under conditions of uncertainty (cutting-packing) problems». Ufa: USATU. 1997. P. 198-207.

177. Valeyeva A.F., Valeyev S.S. Dynamic sorting algorithm for obtaining a set of quasi-optimal solutions in rational resource use problem//^ European Conference on Operational Research. Belgium. 1998.

178. Valeyeva A.F., Agliullin M.N. Ant Colony Algorithm for the 2-D Bin-Packing Problem: Numerical Study // Proceedings of the 5th International Workshop on Computer Science and Information Technologies. 2003. P. 110-114.

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

180. Vanderbeck F., Exact algorithm for minimizing the number of setups in the one-dimensional cutting stock problem, Research Papers in management Studies: University of Cambridge. № 10. 1998.

181. Verhoturov M.A., Sergeyeva O.Y. The sequential value correction method for the two-dimensional irregular cutting stock problem // Pesquisa Operacional. 2000. V. 20. N 2. P. 233-247.

182. Wang P., Valenzeva L. Data set generation for rectangular placement problems // European Journal of Operational Research. 2001. 134(2). P. 378391.

183. Wang P., Wascher G., edit, it Special issue: Cutting Packing Problems // European Journal of Operational Research. 141 (2002).

184. Yanasse H., edit. Special issue: Cutting and Packing Problems// Pesquisa Operacional. 1999. 19(2).