Мультиметодная технология моделирования ортогональной упаковки и размещения прямоугольно-ориентированных заготовок тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Валиахметова, Юлия Ильясовна

• Валиахметова, Юлия Ильясовна
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Валиахметова, Юлия Ильясовна

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

Введение

1. Проблемы раскроя-упаковки. Комбинаторные методы решения

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

1.2. Методы решения задач размещения

1.3. Выводы по главе

2. Моделирование схем прямоугольного размещения

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

2.2 Математические модели конструирования упаковки в полосу и на } листы

2.3. Краткие характеристики основных технологий моделирования ортогональных размещений'.

2.4. Способы кодирования упаковок

2.5. Алгоритмы-декодеры

2.6. Эволюционные алгоритмы

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

2.8. Выводы по главе

3. Мулътиметодная технология моделирования ортогональной упаковки

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

3.2. Модификации алгоритма комбинирования эвристик

3.3. Методы дискриминации и форсирования простых эвристик-декодеров

3.4. Мультиметодные алгоритмы для решения задачи размещения прямоугольно-ориентированных предметов

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

3.6. Выводы по главе

4. Численные эксперименты

4.1 Программная реализация алгоритмов

4.2. Определение рационального количества итераций

4.3. Оценка эффективности алгоритмов. Нижние границы

4.4. Подготовка исходной информации

4.5. Исследование эффективности мультиметодного генетического алгоритма GMA и мультиметодного эволюционного алгоритма (1+1)-МЕА

4.6. Сравнение результатов работы различных декодеров в составе мультиметодного эволюционного алгоритма

4.7. Выводы по главе

5. Исследование эффективности методов дискриминации и форсирования эвристик

5.1. Анализ решения задач упаковки в полубесконечную полосу

5.2. Анализ решения задач упаковки в контейнеры

5.3. Выводы по главе

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

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

Сложность решения задач ортогонального размещения обусловлена их принадлежностью к классу NP-трудных задач комбинаторной оптимизации. Исследуемая проблема является NP-трудной в сильном смысле, так как содержит в качестве подзадачи также NP-трудную задачу. Во многих случаях применение точных методов для ее решения невозможно из-за больших затрат вычислительного времени. В связи с этим большое значение приобретает разработка и исследование эвристических методов оптимизации, в том числе метаэвристик. В их числе широкое применение получили эволюционные алгоритмы, в том числе - генетические. Известна асимптотическая сходимость таких методов. Однако практически оптимум достигается не всегда. Кроме того, до сих пор не известны способы построения нижних границ, приближенных к оптимуму и позволяющих констатировать его достижение. Вместе с тем на практике некоторые метаэвристики хорошо себя зарекомендовали. Качество полученного решения зависит не только от выбранного метода расчета. Важную роль выполняют и способы кодирования и дешифровки упаковок. Однако классические алгоритмы оставляют желать лучших результатов. Интерпретация генов как прямоугольников, а хромосом - как списков, устанавливающих порядок их подачи на упаковку, является не всегда эффективной, о чем свидетельствуют исследования многих ученых (E.Folkenauer, A.Bortfeldt, И.П.Норенков, Э.А.Мухачева).

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

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

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

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

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

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

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

2. Разработать мультиметодную технологию моделирования ортогональной упаковки и размещения прямоугольно-ориентированных заготовок.

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

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

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

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

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

2. Мультиметодная технология моделирования ортогональной упаковки, включающая в себя новые декодеры - мультиметодный декодер (Multi-Method Decoder, MMD) и мультиметодный декодер с либеральными эвристиками (Multi-Method Decoder with Liberal heuristics, MMD(Lib)), и методики дискриминации и форсирования эвристик.

3. Методы и алгоритмы расчета ортогональной упаковки и размещения прямоугольно-ориентированных заготовок с использованием мультиметодной технологии: одноточечный мультиметодный алгоритм (1+1)-МЕА и генетический мультиметодный алгоритм GMA.

4. Анализ результатов численных экспериментов и рекомендации по использованию созданных алгоритмов.

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

Научная новизна работы. Новыми в работе являются:

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

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

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

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

3. Модифицированные эволюционные алгоритмы: мультиметодный одноточечный алгоритм (1+1)-МЕА и мультиметодный генетический алгоритм, в которых используется мультиметодная интерпретация элементов эволюции, что позволяет сократить вычислительное время и добиться лучшего приближения получаемых решений к нижней границе при решении задач загрузки транспортного средства и размещения прямоугольно-ориентированных заготовок, а также для задач ортогональной упаковки полубесконечной полосы и листов, что подтверждается результатами обширного численного эксперимента.

Практическая значимость работы: программная реализация эволюционных алгоритмов на основе мультиметодной технологии показала целесообразность ее развития, а также преимущества в сравнении с известными классическими способами применения эвристических методов к задачам размещения на достаточно широком классе задач. Это позволяет использовать разработанные алгоритмы при практических расчетах. По полученным результатам разработанный алгоритм может быть рекомендован к решению задач прямоугольно-ориентированного размещения на листовой и рулонный материал с определенным набором диапазонов значений вероятностных показателей для входящих в состав декодера эвристик. Разработанный комплекс внедрен на ряде предприятий, в том числе на ООО «Европак» и ООО «Матрица-Трейд», а также в учебном процессе, в том числе на факультете информатики и робототехники УГАТУ, и в БГАУ на факультете информационных технологий и факультете механизации сельского хозяйства.

Апробация работы.

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

1. 13-я Байкальская международная школа-семинар «Методы оптимизации и их приложения» (Иркутск, 2005);

2. Международная уфимская зимняя школа-конференция по математике и физике для студентов, аспирантов и молодых ученых (Уфа, БГУ, 2005)

3. Зимняя школа для аспирантов и молодых ученых (Уфа, УГАТУ, 2006, 2007);

4. 1-я Всероссийская научно-практическая конференция молодых ученых. Молодые ученые в реализации приоритетного национального проекта «Развитие АПК» (Уфа, 2006);

5. 3-я Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2006);

6. Научные семинары кафедры Вычислительной Математики и Кибернетики Уфимского Государственного Авиационного Технического Университета.

По теме диссертации опубликовано 10 работ, в том числе 1 статья в рецензируемом журнале из списка ВАК. Правовая сторона программного продукта защищена «Свидетельством об официальной регистрации программ для ЭВМ» № 2008613940 и №2008613941.

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

Диссертация состоит из введения, пяти глав и заключения. Объем работы составляет 176 страниц машинописного текста, включая 25 рисунков, 16 таблиц, и библиографию, содержащую 120 названий.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Валиахметова, Юлия Ильясовна

5.3. Выводы по главе 5

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

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

• Задачи размещения в полу бесконечной полосе: при исходных данных задач классов С1 и С2:

MMD: p(S\) = 0.883, p(S2) = 0.046, />(S4) = 0.071;

MMD(Lib): p(S\) = 0.8, p(S2) = 0.042, p(S4) = 0.064, p(SlL) = 0.027, p(S2L) = 0.036, p(S4L) = 0.031.

• Задачи размещения на листы: при исходных данных задач 2-го и 3-го типов:

MMD: p(S\) = 0.076, p(S2) = 0.073, p(SA) = 0.851

MMD(Lib): p(Sl) = 0.071, p(S2) = 0.069, p(54) = 0.8, p(S\L) = 0.022, p{S2L) = 0.021, piSAL) = 0.017.

Заключение

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

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

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

2. Разработана мультиметодная технология (Multi-Method Technology, ММТ) моделирования ортогональной упаковки и размещения прямоугольно-ориентированных заготовок, основанная на генетическом методе комбинирования эвристик и идеях их ранжирования, отличающаяся от существующих технологий использованием новых способов декодирования с дискриминацией и форсированием. Мультиметодная технология позволяет создавать новые эволюционные алгоритмы решения задач упаковки и размещения.

3. Разработан мультиметодный одноточечный эволюционный алгоритм ((1+1) - Multi-Method Evolution Algorithm, (1+1)-МЕА) и модификация генетического алгоритма - мультиметодный генетический алгоритм (Genetic Multi-method Algorithm, GMA) с мультиметодной интерпретацией элементов эволюции, основанный на использовании новых мультиметодных алгоритмов-декодеров. Их особенностью является представление упаковки в виде последовательности применения эвристик. Для эвристик, входящих в состав декодеров, определены вероятностные параметры и реализованы их дискриминация и форсирование с целью улучшения получаемых решений. Экспериментально подтверждена высокая эффективность алгоритмов при решении задач загрузки транспортных средств и размещения прямоугольно-ориентированных заготовок на листах при проектировании картонной тары, а именно для задачи размещения заготовок на листах мультиматодные методы показывают лучшие результаты в классе примеров «мелкие предметы» и «мелкие и крупные предметы» по сравнению с традиционными методами. Разработанные алгоритмы на основе мультиметодной технологии позволяют при загрузке ТС сократить свободные области в 2-3 раза, а при размещении прямоугольно-ориентированных заготовок - в 4-5 раз.

4. Поставлена серия численных экспериментов, направленных на определение эффективности разработанных декодеров в составе генетического мультиметодного алгоритма (Genetic Multi-method Algorithm, GMA) и мультиметодного одноточечного эволюционного алгоритма (1+1)-МЕА, а также на сравнение их с другими ранее известными алгоритмами. Результаты численных экспериментов показали, что при использовании разработанных алгоритмов коэффициент использования материала повышается на 5-10% по сравнению с традиционными методами, а в сравнении с лучшими современными алгоритмами - на 1.5-2.5%.

5. Предложена методика использования мультиметодной технологии для решения задач составления расписания, задач ортогональной трехмерной упаковки, задач фигурного раскроя, задачи покрытия и др. Мультиметодная технология реализована в виде алгоритмов и прикладного программного обеспечения в среде программирования Borland Delphi 7.0. Разработанное программное обеспечение имеет развитый интерфейс и может использоваться как автономно, так и в составе комплексов программ упаковки и размещения. Результаты диссертационной работы приняты к внедрению в виде алгоритмов и программного обеспечения в производственный процесс на 000«ЕвроПак» и 000«Матрица-Трейд» (г.Уфа). В результате внедрения отходы материала при раскрое картона снижены на 14%, а загрузка грузового отсека на 5-7% интенсивнее традиционной.

Список литературы диссертационного исследования кандидат технических наук Валиахметова, Юлия Ильясовна, 2008 год

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

2. Алентьева Ю.И. (Валиахметова) Модификация мультиметодного генетического алгоритма для решения задач ортогональной упаковки. / Ю.И.Алентьева (Валиахметова), Л.И.Васильева // Принятие решений в условиях неопределенности. Уфа: УГАТУ, 2007.С.64 72.

3. Батищев Д.И. Топологический синтез аналого-цифровых микроэлектронных устройств / Д.И.Батищев, В.Ф.Морозов, С.Е.Власов, И.В.Булгаков // Информационные технологии, 1996, №2. С. 39 43.

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

5. Борисовский П.А. О сравнении некоторых эволюционных алгоритмов / П.А.Борисовский, А.В.Еремеев // М.: Изд-во «Наука». Автоматика и телемеханика №3. 2004. С. 3 9.

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

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

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

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

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

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

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

13. Ермаченко А.И. Метод поиска с запретами для решения задач прямоугольного гильотинного раскроя. / А.И.Ермаченко, Т.М.Сиразетдинов // Дискретный анализ и исследование операций: сб. тр. всерос. конф. Новосибирск: НГТУ, 2002. С. 230.

14. Ермаченко А.И. Рекурсивный метод для решения задачи гильотинного раскроя / А.И.Ермаченко, Т.М.Сиразетдинов // Уфа: Принятие решенийв условиях неопределенности. Сб. научн. статей. УГАТУ. 2000. С.35 -39.

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

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

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

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

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

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

21. Мухачева А.С. Технология блочных структур локального поиска оптимума в задачах прямоугольной упаковки / А.С.Мухачева // Информационные технологии. 2004. No.5. Прил.18 32.

22. Мухачева А.С. Конструирование алгоритмов локального поиска оптимума прямоугольной упаковки на базе двойственных задач линейного раскроя. / А.С.Мухачева, Э.А.Мухачева // Информационные технологии. №6, 2002. С. 25 30.

23. Мухачева А.С. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя. / А.С.Мухачева, А.В.Чиглинцев // Информационные технологии. 2001. №3. С. 27 32.

24. Мухачева А.С. Задачи упаковки прямоугольников: рандомизированная эвристика на базе двойственной схемы локального поиска оптимума / А.С.Мухачева, Р.Р.Ширгазин // Информационные технологии. 2003. №5. С. 18-23.

25. Мухачева Э.А. Метод динамического перебора в задаче двумерной упаковки. / Э.А.Мухачева, А.Ф.Валеева // Информационные технологии. 2000. №5. С. 30 37. Работа поддержана РФФИ: проект 99-01-00947.

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

27. Мухачева Э.А. Рациональный раскрой прямоугольных листов на прямоугольные заготовки / Э.А.Мухачева // Оптимальное планирование: Сб. научных трудов СО АН СССР. 1966. Вып. 6. С. 43 -115.

28. Мухачева Э.А. Декодирование прямоугольных упаковок: основные направления разработки алгоритмов. / Э.А.Мухачева, Ю.И. Алентьева (Валиахметова) // Принятие решений в условиях неопределенности: Сб. науч. тр. УГАТУ. 2005. С. 76 81.

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

30. Мухачева Э.А. Модели и методы расчета раскроя-упаковки геометрических объектов. / Э.А.Мухачева, М.А.Верхотуров,

31. B.В.Мартынов // Уфа. УГАТУ. 1998. С. 216.

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

33. C. 15 22. Работа поддержана РФФИ: проект 99-01-00947.

34. Мухачева Э.А. Метод перестройки для решения задачи прямоугольной упаковки / Э.А.Мухачева, А.С.Мухачева // Информационные технологии. 2000 №4. С. 30 36. Работа поддержана РФФИ, проект 9901-00947.

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

36. Мухачева Э.А. Проектирование прямоугольных упаковок с использованием декодеров блочной структуры. / Э.А.Мухачева, Д.А.Назаров, А.С.Филиппова // М.: Наука. Автоматика и телемеханика. 2006, №6. С. 161-173.

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

38. Норенков И.П. Генетические методы структурного синтеза проектных решений. / И.П.Норенков // Информационные технологии, 1998, №1. С.9 -13.

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

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

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

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

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

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

45. Усманова А.Р. Вероятностные жадные эвристики для задачи упаковки в контейнеры. / А.Р.Усманова // С.Петербург: ОПТИМ-2001. С. 141 146. Работа поддержана РФФИ: проекты 99-01-00947, 01-01-00510.

46. Филиппова А.С. Моделирование эволюционных алгоритмов решения задач прямоугольной упаковки на базе технологии блочных структур. / А.С.Филиппова // М.: Новые технологии. Информационные технологии. №6. 2006. Прил. С. 31.

47. Филиппова А.С. Мультиметодный генетический алгоритм для решения задач ортогональной упаковки. / А.С.Филиппова, Ю.И.Валиахметова // Информационные технологии, №12, 2007. С. 50 57.

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

49. Aurts E. Local Search in Combinatorial Optimization. / E.Aurts, J.Lenstra, edit. // John Wiley&Sons. 1996. P. 10 15.

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

51. Bortfeldt A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. / A.Bortfeldt // University of Hagen. Germany. Preprint. 2004. P.29-67.

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

53. Bruns R. Direct Chromosome Representation and Advanced Genetic Operators for Production Scheduling. / R.Bruns // Proc. Of 5th Int. Conf. on GA, 1993. P. 289-356.

54. Chazelle B. The Bottom-Left Bin Packing Heuristic: An Efficient Implementation. / B.Chazelle // IEEE Translations on Computers. 1983. 32(8). P. 697 707.

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

56. Chung F.K.R. On packing two-dimensional bins. / F.K.R.Chung, M.R.Garey,

57. D.S.Johnson // SIAM J. Algebraic Discrete Meth. 3 (1982) P. 66 76.

58. Coffman E. Approximation algorithms for bin-packing-an updated survey. /

59. E.Coffman, M.Garey, D.Jchonson // Algorithm Design for Computer System Design (Ausiello G., Lucertini M., Serafini P.eds) Berlin etal. 1984. P. 67-89.

60. Dorigo M. Ant Algorithms for Discrete Optimization. / M.Dorigo, Di

61. G.Caro, L.M.Gambardella I I Artificial Life. 1999. Vol.5. No.3. P.137 172.

62. Dorigo M. Ant Colonies for the traveling salesman problem. / M.Dorigo, L.M.Gambardella// IRIDIA, Technical Report 1996. P. 3.

63. Dorigo M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. / M.Dorigo, L.M.Gambardella // IEEE Transactions on Evolutionary Computation. 1997. Vol.l. No.l. P. 45-68.

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

65. Dyckhoff H. Special issue: Cutting and Packing / H.Dyckhoff, G.Wascher, edit. // European Journal of Operational Research. 1990. 44(2). P. 156-189.

66. Esbensen H. Finding (Near-)Optimal Steiner Trees in Large Graphs. /

67. H.Esbensen // Proc. Of 6th Int. Conf. on GA, Morgan Kaufinann Publ., San Francisco, 1995. P. 89-134.

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

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

70. Folkenauer E. Tapping the full power of genetic algorithm through suitable representation and local optimization: Application to bin packing. /

71. E.Folkenauer // Evolutionary Algorithms in Management Applications. Berlin. 1995. P. 167- 182.

72. Garey M.R. Computers and Intractability: A guide to the Theory of NP-Completeness / M.R.Garey, D.S.Johnson // San-Francisco, Freemau. 1979. P. 321 -338.

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

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

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

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

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

78. Hopper E. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. / E.Hopper, B.Turton // EJOR 128. 2001. P. 34-57.87. http://mscmga.ms.ic.ac.uk/ieb/orlib/ngcutinfo.html

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

80. Ishibuchi H. Effectiveness of Genetic Local Search Algorithms. / H.Ishibuchi, D.Murata, S.Tomioka // Proc. Of 7th Conf. on GA, 1997. P. 673 -708.

81. Jhonson D.S. Worst-case performance bounds for simple one-dimensional packing algorithms. / D.S.Jhonson, A.Demers, J.D.Ullman, M.R.Garey, R.L.Graham // SIAM J. Comput. V. 3. N4. 1974. P.299 325.

82. Kalyanmoy D. Car Suspension Design for Comfort Using Genetic Algorithms. / D.Kalyanmoy, V.Saxena // Proc. Of 7th Conf. on GA, 1997. P.320 358.

83. Kirkpatrick S. Optimization by simulated annealing. / S.Kirkpatrick, C.D.Gelatt, M.P.Vecchi // Science. v220 (1983), P. 671 680.

84. Kobayashi S. An Efficient Genetic Algorithm for Job Shop Scheduling Problem. / S.Kobayashi, I.Ono, M.Yamamura // Proc. Of 6th Int. Conf. on GA, Morgan Kaufmann Publ., San Francisco, 1995. P. 211 245.

85. Lirov Y. Special issue: Geometric Resource Allocation. / Y.Lirov, edit. // Mathematical and Computer Modelling. 1995. 16(1). P. 144-203.

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

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

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

89. Loris Faina. An application of simulated annealing to the cutting stock problem / Loris Faina // European Journal of Operational Research. 1999. 114. P. 532-556.

90. Martello S. Special issue: Knapsack, Packing and Cutting, Part II: Multidimensional Knapsack and Cutting Stock Problems. / S.Martello, edit. // INFOR. 1994. 32(4). P. 44 67.

91. Martello S. Special issue: Knapsack, Packing and Cutting, Part I: One Dimensional Knapsack Problem. / S.Martello, edit.// INFOR. 1994. 32(3). P. 32-48.

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

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

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

95. Morabito R. An AND/OR graph approach to the container loading problem. / RMorabito, M.Arenales // International Transactions in Operational Research 1 (1994). P. 59 73.

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

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

98. Nakano R. Convertional Genetic Algorithm for Job Shop Problems / R.Nakano // Proc. Of 4th Int. Conf. on GA, Morgan Kaufmann Publ., San Francisco, 1991. P. 378 402.

99. Norenkov I.P. Genetic Method for Satisfiadility Problem Solving. / I.P.Norenkov, O.T.Kosahevsky // Proc. Of EWITD'96. Moscow: ICSTI, 1996. P. 155- 169.

100. Rechenberg I. Evolutions strategic: Optimerung Technischer Systeme nach Prinzipen der Biologischen Evolution. / I.Rechenberg // Stuttgart: Formann -Holzboog Verlag. 1973. P. 44 92.

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

102. Schewerin P. The Bin-Packing Problem: a Problem Generator and some numerical Experiments with FFD Packing and MTP. / P.Schewerin,

103. G.Waescher 11 International Transactions in Operational Research. 1997. Vol. 4. P. 337-389.

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

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

106. Terno J. Zuschnitprobleme und ihre praktische Losung. / J.Terno, R.Lindeman, G.Scheithauer//Leipzig. 1987. P. 215.

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

108. Wang P. Special issue: Cutting Packing Problems. / P.Wang, G.Wascher, edit.// Europen Journal of Operational research. 141 (2002). P. 158.

109. Whitley D. Scheduling Problems and Traveling Saleman: the Genetic Edge Recombination Operator. / D.Whitley, T.Starkweather, D.Fuduay // Proc. Of 3d Int. Conf. on GA, 1989. P. 233 266.

110. Yanasse H. Special issue: Cutting and Packing Problems. / H.Yanasse, edit. // Pesquisa Operacional. 1999. 19(2). P. 14-27.ща