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

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

ВАЛИАХМЕТОВА Юлия Ильясовна

МУЛЬТИМЕТОДНАЯ ТЕХНОЛОГИЯ МОДЕЛИРОВАНИЯ ОРТОГОНАЛЬНОЙ УПАКОВКИ И РАЗМЕЩЕНИЯ ПРЯМОУГОЛЬНО-ОРИЕНТИРОВАННЫХ ЗАГОТОВОК

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

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

О 2 ОПТ 2008

Уфа 2008

003448349

Работа выполнена в ГОУ ВПО «Уфимский государственный авиационный технический университет» на кафедре вычислительной математики и кибернетики и кафедре компьютерной математики

Научный руководитель

д-р техн наук, доц Филиппова Анна Сергеевна

Официальные оппоненты

д-р техн. наук, профессор Норепков Игорь Петрович

д-р физ -мат наук, профессор Спивак Семен Израильевич

Ведущая организация

ГОУ ВПО «Самарский государственный аэрокосмический университет им акад СПКоролева»

Защита состоится 17 октября 2008 г в 14.00 часов

на заседании диссертационного совета Д-212 288.03

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

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

Автореферат разослан «_»_

2008г

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

В.В. Миронов

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

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

Сложность решения задач размещения обусловлена их принадлежностью к ОТ-трудным задачам комбинаторной оптимизации Исследуемые задачи являются ^-трудными в сильном смысле, так как содержат в качестве подзадач также трудные задачи Во многих случаях применение точных методов для их решения невозможно из-за больших затрат вычислительного времени В связи с этим большое значение приобретает разработка и исследование эвристических методов оптимизации, в том числе метаэвристик Важную роль выполняют и способы кодирования и дешифровки упаковок Однако классические алгоритмы оставляют желать лучших результатов Интерпретация генов как прямоугольников, а хромосом - как списков, устанавливающих порядок их подачи на упаковку, является эффективной не всегда, о чем свидетельствуют исследования многих ученых (Е Ро1кепаиег, А ВоЛГе1сИ3 И П Норенков, Э А Мухачева)

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

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

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

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

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

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

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 Предложен мультиметодный одноточечный эволюционный алгоритм (1+1)-МЕА и расширенная версия генетического алгоритма И П Норенкова, которые используют мультиметодную интерпретацию элементов эволюции, что позволяет сократить вычислительное время и добиться лучшего приближения получаемых решений к нижней границе

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

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

5 Математическое и программное обеспечение, реализующее работу мультиметодных алгоритмов с возможностью выбора декодеров ММ1) и ММВ(1лЬ) для решения задач загрузки транспортного средства и задач размещения прямоугольно-ориентированных заготовок при проектировании картонной тары

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

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

жения» (Иркутск, 2005), Международная уфимская зимняя школа-конференция по математике и физике для студентов, аспирантов и молодых ученых (Уфа, БГУ, 2005), Зимняя школа для аспирантов и молодых ученых (Уфа, УГАТУ, 2006, 2007), 1-я Всероссийская научно-практическая конференция молодых ученых Молодые ученые в реализации приоритетного национального проекта «Развитие АПК» (Уфа, 2006), 3-я Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2006), научные семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета

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

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

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Различают задачи одномерной упаковки (ID Вт Packing, 1DBP) и раскроя (ID Cutting stock, 1DCS), задачи прямоугольной упаковки в полубесконечную полосу (1 5DBP) (термин 1 5D ввел в 1980г А Нншгап) и задачи прямоугольной упаковки в листы (2DBP) Задачи упаковки и гильотинного раскроя различаются технологией разрезания материала Также выделяют задачи упаковки в открытую область (квадрант), задачи трехмерной загрузки контейнеров и задачи о максимальном покрытии Выделяются в отдельный класс задачи размещения сложных геометрических фигур

Задачи упаковки (BP) являются типичными представителями NP-трудных проблем и для их решения применяются методы полного перебора с отсечением неперспективных вариантов Ввиду NP-трудности размерность решаемых задач невелика (<200 для 1D и <20 для 1 5D и 2D) Поэтому наряду с точными приме-

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

Исследуемый в диссертации генетический алгоритм разработан на основе блочных технологий, начало которых получено в работах А С Мухачевой В диссертации разработаны новые декодеры - MMD и MMD(Lib)

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

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

Во второй главе приводятся постановки и математические модели рассматриваемых технических проблем, задачи загрузки транспортного средства и задачи размещения прямоугольно-ориентированных предметов Они сводятся к модели ортогонального размещения прямоугольников при дополнительных ограничениях. Приводятся формулировки задач ортогональной упаковки в полубесконечную полосу (1 5DBP) и на листы (2DBP) Глава посвящена рассмотрению способов кодирования и декодирования упаковок Описаны основные принципы генетических и эволюционных алгоритмов, приведены описания общих стратегий работы этих алгоритмов. Приведены описания некоторых алгоритмов-декодеров блочной технологии, а также декодера комбинирования эвристик (Heuristics Combination Decoder, HCD) И П Норенкова

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

В реальных ситуациях представляет интерес технологический раскрой, о котором можно судить по времени технической подготовки, связанной с расчетом рациональных карт раскроя, а также по экономии материальных ресурсов за счет плотного размещения заготовок На сегодняшний день в России около 30% печатной продукции составляет картонная и бумажная тара для различной продукции Одним из предприятий, занимающихся изготовлением картонной тары, является ООО «Европак»

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

ветствующих справочниках Тип картона определяет величину технических припусков, размеры клапанов и прочие характеристики упаковок

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

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

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

Постановка задачи Имеется множество Q из т прямоугольно-ориентированных многоугольников, представляющих собой развертку картонной упаковки

Исходная информация <W,L,m,e, п, х, у, w, I >, где W ~ ширина, L - длина листа картона, т - количество заготовок, s - вектор флагов разрешения на поворот заготовок на 90°, 180°, 270°;я = (л} ,я2> ,nj, ,пт), где п} - количество

прямоугольников в прямоугольно-ориентированной заготовке с номером J ,x = {xj),y = (jj), где (Xj ,yj) - координаты левого нижнего угла прямоугольника с номером к, входящего в заготовку с номером j, к-\,n.j, j = l,m, при задании входных данных каждая заготовка описывается в своей системе координат, w = (wj),l = (lj), где (Wj , lj ) - длина и ширина прямоугольника с номером к, входящего в заготовку с номером j, к=\,пj, j = \,т

Выходная информация минимальные координаты (Xj,yj) каждого "прямоугольника в прямоугольно-ориентированных заготовках в единой системе координат полубесконечной полосы или листа, k-\,rij,j = \,m

Требуется минимизировать отходы материала. ц(х,у)-1¥ L-'у ,

т к

к — 1, п ., j -1, т при условиях допустимости упаковки

1° ортогональное размещение прямоугольников в упаковке для (х,,;уг)и любой другой вершины (х^, у^) г-го прямоугольника

((*,* = *,) ■V (*,* = Хг + /г)) Л ((?* = Л ) V О* = Л + Щ)),

2° неперекрытие заготовок для I ф ] 1,_/ = 1,т

((х, >XJ+lJ)v(xJ>x¡ + /г)) V >уу + и>у) >yI+wlУ)vs¡

3° неперекрытие заготовок с гранями объектов для всех 1 = \,т

(*, > 0) А (у, >0)л ((*+«*) +1,)<Ь)

Задача загрузки транспортного средства. Предположим, что условное предприятие путем организации регулярных рейсов осуществляет поставки в Россию крупногабаритных грузов промышленного назначения с нескольких складских центров, расположенных в Европе Очередной рейс заключается в последовательном прохождении транспортным средством (ТС) задействованных складов для загрузки товаров, последним пунктом является склад разгрузки в г. Москве Необходимо составить заказ на доставку рейсом, максимизирующим прибыль, которую получит предприятие от его реализации. Адаптируя данную схему к конкретным условиям, следует отметить, что компания использует однотипные ТС с фиксированными параметрами грузового отсека Модуль выбора ТС в данном случае является незначимым, его можно исключить из схемы Работа модуля расчета маршрута будет заключаться только в решении задачи коммивояжера, т е определении порядка прохождения складов, необходимого для соблюдения требования комфортности размещения, и в подсчете затрат, пропорциональных пробегу

Основным звеном схемы становится модуль размещения Будем считать, что каждому грузу соответствует прямоугольный контейнер, имеющий длину, ширину и высоту В силу специфики поставляемых товаров кантовка контейнеров запрещена, т е их не разрешается переворачивать и ставить друг на друга При этом повороты контейнеров в плоскости основания возможны. Высота каждого контейнера не превосходит высоту Н грузового отсека ТС Данные замечания позволяют представлять контейнеры в виде их двумерных проекций на плоскость оснований, грузовой отсек ТС — в виде прямоугольной области, а всю задачу можно свести к двумерной задаче упаковки контейнеров 2БВР [11] Важной здесь является интерпретация требования комфортности размещения, т к мы имеем дело не с последовательной разгрузкой транспортного средства, а с его последовательной дозагрузкой, порядок которой определяется порядком прохождения ТС задействованных складских пунктов

Исходная информация задается в виде (5,я;с), где 5 - площадь основания грузового отсека ТС, $ - вектор площадей оснований контейнеров, с - вектор стоимостей Исходная информация где Ж-ширина, £-

длина грузового отсека ТС, £? - количество потребителей, т - количество грузов,

m = ^mk,k = \,Q, w = (wj),l = (lj), trz(Wj,Ij) - длина и ширина груза g* с

номером j, входящего в заявку от пункта с номером к, k = l,Q, j - ,

Z = (zj ), j = 1, m^, А = I, Q - матрица весов грузов, G - грузоподъемность ТС,

g = (gj), k = l,Q, j - \,тк - матрица наименований грузов

к к

Выходная информация (Xj,)>j) - минимальные координаты грузов, k = l,Q,j = l,mk

Требуется минимизировать свободное пространство в грузовом отсеке

ТС ju(x,y)-W L - -»mmпри условиях

J к

• допустимость упаковки, выполнение (10),(2° ),(3°),

• комфортность разгрузки если порядок обхода клиентов (1,2,3, ,Q),

gk = {gf, ,gk } - неупорядоченное множество грузов, предназначенных для дос-Щ

тавки в пункт с номером к, то порядок загрузки отсека ТС % - (g®, ,gk,

причем gk ng1 =(3k,t = \,Q,k#t

• Суммарная масса грузов не превышает грузоподъемности ТС Q Щ ,

¿Ы/=1

Под комфортностью разгрузки здесь понимается то, что при загрузке ТС необходимо учитывать, в каком порядке придется выгружать контейнеры Порядок, в котором контейнеры будут разгружаться, определяется очередностью обхода пунктов разгрузки

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

Наиболее известным представителем алгоритмов, базирующихся на без-уровневой технологии, является декодер «нижний-левый» (Bottom Left, BL)

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

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

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

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

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

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

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

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

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

!

Рис. 1 - Размещение компонента в очередном участке

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

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

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

51) выбирается еще не упакованная деталь, обеспечивающая минимальный вертикальный зазор gap > 0, если gap > 0, то деталь размещается вплотную к тому краю участка, на котором меньше (по абсолютной величине) горизонтальный зазор z, если деталей с gap > 0 нет, то участок ширины а и длины h объявляется пустотелым и заполняется фиктивным элементом (рис 1),

52) го неразмещенных деталей с неотрицательным значением вертикального зазора gap выбирается деталь, обеспечивающая минимальный горизонтальный зазор z при исходной ориентации, если таких деталей нет, то делается попытка найти подходящую деталь при повернутой ориентации, в противном случае, если заготовок с gap > 0 нет, то участок ширины а и длины h объявляется пустотелым и заполняется фиктивной деталью,

53) то же, что и в 52, но сначала исследуются заготовки повернутыми на

90°,

54) выбирается деталь с наибольшей площадью и с неотрицательным зазором gap

Полученный конструктивный алгоритм является декодером комбинирования эвристик (Heuristics Combination Decoder, HCD). Задача сводится к поиску и использованию рациональной последовательности эвристик, применяемых в подзадачах Направленный перебор решений осуществляется с помощью генетического алгоритма Главная особенность заключается в том, что аллелями служат не значения проектных параметров, а имена эвристик, используемых для определения этих значений i-й ген соответствует г-й подзадаче, аллелями являются имена эвристик, именно среди них генетический алгоритм и выбирает объекты последовательности, приближаясь к оптимальной перестановке

Разработан мультиметодный декодер (Multi-Method Decoder, MMD), включенный в среду генетического мультиметодного алгоритма GMA, а затем и в эволюционный одноточечный алгоритм (1+1)-МЕА, и представляющий расширение списка эвристик Помимо предложенных в оригинальном алгоритме были до-

бавлены следующие

55) выбирается еще не размещенная деталь, обеспечивающая минимальный горизонтальный зазор gapi? > 0 при повороте на 90°, если gapi? > 0, то деталь размещается вплотную к тому краю участка, на котором меньше (по абсолютной величине) вертикальный зазор z, если деталей с gapi? > 0 нет, то участок шириной а и высотой h объявляется пустотелым и заполняется фиктивным элементом,

56) выбирается деталь с наибольшей площадью и с неотрицательным зазором gapi? при повороте на 90°, если таковых нет среди еще не размещенных деталей, то рассматриваемая область объявляется пустотелой.

Мулътиметодный декодер с либеральными эвристиками (Multi-Method Decoder with Liberal heuristics, MMD(Lib)) был разработан на базе декодера MMD Этот декодер также получен расширением перечня простых эвристик При работе он использует уже не только SI-S6, но еще и набор «либеральных» эвристик

Sil) выбирается деталь, обеспечивающая максимальный вертикальный зазор gap>0, если gap > 0, то деталь размещается вплотную к тому краю участка, на котором больше (по абсолютной величине) горизонтальный зазор z,

SIL) из деталей с неотрицательным значением вертикального зазора gap выбирается деталь, обеспечивающая максимальный горизонтальный зазор z при исходной ориентации если таких деталей нет, то делается попытка найти подходящую деталь при повороте на 90°;

S3L) то же, что и в S2L, но сначала исследуются заготовки повернутыми на 90°,

S4L) выбирается деталь с наименьшей площадью среди еще не размещенных заготовок и с неотрицательным зазором gap,

S5L) выбирается деталь, обеспечивающая максимальный вертикальный зазор gapi? > 0 при повороте на 90°, если gapi? > 0, то деталь размещается вплотную к тому краю участка, на котором больше (по абсолютной величине) горизонтальный зазор zR ,

SGL) выбирается деталь с наименьшей площадью кис неотрицательным зазором gapi?

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

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

Метод форсирования простых эвристик Экспериментальное исследова-

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

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

Цель проведенных исследований в следующем: 1). определение рационального набора входных параметров алгоритма СМА; 2). исследование эффективности алгоритмов-

декодеров при использовании различных генетических алгоритмов; 3). сравнение результатов численного эксперимента, полученных генетическим алгоритмом вМА и эволюционным одноточечным алгоритмом (1+1)-МЕА; 4). сравнение результативности декодеров ММВ и ММБ(1лЬ) при решении задач размещения на листы и в полосу между собой, а также с другими известными алгоритмами в рамках применения генетического метода; 5). сравнение результатов, полученных декодерами МЗУГО и ММ1)(1лЬ) при решении задач размещения на листы и в полосу между собой, а также с другими известными алгоритмами в рамках применения эволюционного одноточечного алгоритма (1+1)-МЕА; 6). определение целесообразности включения в состав декодеров «либеральных» эвристик; 7). определение эффективности метода дискриминации простых эвристик.

Исследование эффективности алгоритмов-декодеров при использовании генетических алгоритмов и алгоритма (1+1)-МЕА. Целью этого численного эксперимента являлось сравнение эффективности генетического мультиметодного алгоритма (СМА) с эволюционным одноточечным алгоритмом с декодером замещения (Ш(8иЬ)) как двух представителей генетических алгоритмов, а также с алгоритмом муравьиной колонии (АСР) и с мультиметодным эволюционным алгоритмом ((1+1)-МЕА). Для тестирования использовались примеры из библиотеки задач ОЯ-иЬгагу, предложенные 8.Реке1е и Т.ЗсЬерегя, для которых известны значения нижних границ. В алгоритме АСР количество итераций - 500, а количество агентов составило 30; количество итераций для алгоритма СМА - 4000. Эти

Среднее отклонение от нижней границы [%)

3,6 ., . ...., ,,-г—г,«™.-: 1.Л ., ., ■- V...'. ,-■

класс! класс2 классЗ

Рис. 2 - Результаты численного эксперимента

результаты сравнивались с нижнеи границей Л^. Показателем эффективности алгоритма служит информация вида N(S,t), где N - полученное число использованных листов, S - номер последней результативной итерации, t ~ затраты времени (в секундах) Диаграмма, иллюстрирующая среднее отклонение от нижней границы для каждого из алгоритмов, приведена на рис 2

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

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

Все 500 задач из статей Berkley и Wang, задачи из статей Martello и Vigo (задачи размещения в полубесконечной полосе), а также задачи, предложенные S Р Fekete и J Schepers (задачи размещения на листах) были решены каждой из эвристик в отдельности, и для каждой из них было определено значение /л (относительное отклонение полученного решения от нижней границы) по формуле

//(%) = ———100%, где L - длина упаковки, Л - значение нижней границы.

Л

Вероятность выбора эвристики должна быть обратно пропорциональна величине относительного отклонения, полученного этой эвристикой при решении задач В то же время все эвристики образуют полную группу несовместных событий С учетом этих условий по формуле P(S,) =-^—— были рассчитаны

значения вероятностей

Эксперимент показал, что с помощью метода дискриминации эвристик удается существенно повысить эффективность общего алгоритма решения задач размещения в полосе декодером MMD Однако декодер MMD(Lib) при дискриминации эвристик показал результаты, значительно уступающие предыдущим, когда эвристики применялись с одинаковой вероятностью В связи с этим было решено лишь приблизительно рассчитывать значения вероятностей для определения характера соотношения их величин Так, например, эвристика S1 в обоих декодерах

работает эффективнее остальных За ней следующая по эффективности - S4, и на третьем месте - S2. Значит, можно искусственно увеличить вероятность появления S1 и соответственно уменьшить вероятность появления остальных эвристик Вероятности «либеральных» эвристик можно уменьшить, чтобы снизилось количество ухудшающих решение шагов Такое «искусственное» завышение вероятности появления для лучшей на данном классе задач эвристики получило название форсирования эвристик.

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

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

« MMD. p(Sl) = 0 883, p{S2) = 0 046, p{S4) = 0 071, « MMD(Lib) = 0 8, p(S2) - 0 042, р(54) = 0064, p(S\L) = 0 027, p{S2L) = 0 036, p(S4I) = 0 031

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

• MMD p{Sl) = 0 076, p(S2) = 0 073, p(S4) = 0851 ■ MMD (Lib). p(Sl) = 0 071, p(S2) = 0 069, p(S4) = 0 8, p(SlL) = 0 022, p{S2L) = 0 021, p(S4L) = 0 017

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

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

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

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

горитмы решения задач упаковки и размещения

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

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

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

СПИСОК ПУБЛИКАЦИЙ

Б периодических изданиях из списка ВАК

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

В других изданиях

2 Алгоритмы декодирования прямоугольных упаковок краткий обзор современных подходов / Э.А Мухачева, А С Мухачева, Ю И Алентьева (Валиахме-това) // Методы оптимизации и их приложения 13-я Байкальская международная школа-семинар труды шк -сем 2005 Т 1. Математическое программирование С 543 - 549

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

4 Сравнительный анализ алгоритмов упаковки прямоугольно-ориентированных многоугольников в полубесконечную полосу / Ю И Алентьева (Валиахметова), Л И Васильева, Л М Карамова // Принятие решений в условиях неопределенности сб науч тр Уфа УГАТУ, 2005 С.253 - 259

5 Эвристический алгоритм для решения задач комбинаторной оптимизации на базе методик И П Норенкова / Ю И Алентьева (Валиахметова) // Интеллектуальные системы обработки информации и управления сб ст Per зимн шк -сем. аспирантов и молодых ученых, 16-19 февраля 2006 Уфа Технология, 2006 Т 1 С 253-259.

6 Обзор алгоритмов упаковки прямоугольно-ориентированных многоугольников в полубесконечную полосу / Ю И Алентьева (Валиахметова), Л И Васильева, Л М Карамова // Принятие решений в условиях неопределенности. Уфа. УГАТУ, 2005 Вып 2, ч 1. С. 88 - 92

7 Программный продукт для решения задач раскроя-упаковки с применением генетического алгоритма И П Норенкова / Ю И Алентьева (Валиахметова), В И Карамов // Молодые ученые в реализации приоритетного национального проекта «Развитие АПК» . материалы 1-й Всерос науч -пракг конф молодых ученых Ч 2 С 29-36

8 Применение эвристических подходов И П Норенкова в составе гибридного алгоритма для решения задач раскроя-упаковки прямоугольных заготовок / Ю И Алентьева (Валиахметова) // Проблемы оптимизации и экономические приложения 3-я Всерос конф матер конф (Омск, 11-15 июля 2006) Омск, филиал Ия-та математики им С Л Соболева СО РАН Омск Изд-во ОмГТУ, 2006 С 72

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

10 Мультиметодные алгоритмы в задачах ортогональной упаковки / Ю И Валиахметова, Л И.Васильева, Л.М Карамова // Фундаментальная математика и ее приложения в естествознании . сб тр Всерос шк.-конф. для студентов, аспирантов и молодых ученых Математика Уфа РИЦ БашГУ, 2008 Т 2 С.49 -58

Диссертант

j^J^j^ Ю.И.Валиахметова

Валиахметова Юлия Ильясовна

МУЛЬТИМЕТОДНАЯ ТЕХНОЛОГИЯ МОДЕЛИРОВАНИЯ ОРТОГОНАЛЬНОЙ УПАКОВКИ И РАЗМЕЩЕНИЯ ПРЯМОУГОЛЬНО-ОРИЕНТИРОВАННЫХ ЗАГОТОВОК

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

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

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

ГОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К. Маркса, 12

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

Введение

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% интенсивнее традиционной.

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.ща