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

На правах рукописи 0046ИЭС

ПОЛЯКОВСКИЙ Сергей Юрьевич

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

(В ДЕРЕВООБРАБАТЫВАЮЩЕЙ И МЕБЕЛЬНОЙ ПРОМЫШЛЕННОСТИ)

05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

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

2 4 ['Юн

Уфа - 2010

004605729

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

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

Валеева Аида Фаритовна

Официальные оппоненты д-р техн. наук, проф.

Михеева Татьяна Ивановна проф. каф. организации и управления перевозками на транспорте Самарского гос. аэрокосм, ун-та

канд. техн. наук.

Сиразетдинов Тимур Маратович

заведующий лабораторией

ООО "Уфимский Научно-Технический

Центр"

Ведущая организация Институт проблем управления

сложными системами РАН, г. Самара

Защита диссертации состоится « 2 » июля 2010 г. в 12:30 часов на заседании диссертационного совета Д-212.288.03 при Уфимском государственном авиационном техническом университете по адресу: 450000,Уфа-центр, ул. К.Маркса, 12

С диссертацией можно ознакомиться в научной библиотеке университета Автореферат разослан « 31 » мая 2010 г.

Ученый секретарь

диссертационного совета, 1К

д-р техн. наук, проф. с " В. В. Миронов

ОБЩАЯ ХАРАКТЕРИСТИКА ИССЛЕДОВАНИЯ

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

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

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

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

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

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

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

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

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

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

5. Исследовать эффективность предложенных методов и алгоритмов с помощью численного эксперимента. Выработать рекомендации по их применению в реальном производстве.

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

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

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

2. Методика повышения эффективности управления раскроем листового материала в условиях неопределенности.

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

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

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

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

Научная новизна результатов диссертационного исследования:

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

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

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

3.1. Задача выделения критических областей оперативно-календарного плана;

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

3.3. Задача построения карт раскроя, минимизирующих локальное взвешенное опережение-запаздывание;

3.4. Задача распределения карт раскроя по параллельным режущим машинам для их'обработки.

Практическую ценность имеют следующие полученные результаты:

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

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

Внедрение результатов работы в виде методики повышения эффективности управления раскроем листового материала при производстве заготовок и рабочего прототипа программного обеспечения для оптимизации стадии предварительного распила осуществлено в ООО «ДИП» («Двери и пиломатериалы»), г. Ростов-на-Дону.

Апробация работы. Основные материалы диссертационной работы докладывались и обсуждались на следующих научно-технических конференциях: 7-й международный симпозиум по информатике и информационным технологиям CSIT' 2005 (Россия, Уфа-2005); 3-я международная конференция по раскрою и упаковке 3rd ESICUP Meeting 2006 (Португалия, Порто - 2006); 20-я международная конференция по промышленным, инженерным и другим приложениям в области прикладных интеллектуальных систем (Япония, Киото -2007); 22-я европейская конференция по исследованию операций EURO XXII (Чехия, Прага - 2007); Международная конференция Германского общества по исследованию операций Operations Research 2007 (Германия, Саарбрюккен -2007); 9-й международный симпозиум по информатике и информационным

технологиям CSIT' 2007 (Россия, Уфа - 2007); 5-я международная конференция по раскрою и упаковке 5th ESICUP Meeting 2008 (Италия, Л'Аквилла - 2008); 23-я европейская конференция по исследованию операций EURO XXIII (Германия, Бонн - 2009).

Публикации. Основные результаты по теме диссертации опубликованы в 13 статьях, в том числе 3 - в рецензируемых журналах из списка ВАК, 1 - свидетельство о регистрации программы для ЭВМ.

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

Структура и объем работы. Диссертация состоит из введения, 4 глав, выводов и списка литературы. Работа изложена на 152 страницах машинописного текста, кроме того, содержит 42 рисунка и 2 таблицы. Библиографический список включает 151 наименование и занимает 14 страниц.

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

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

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

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

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

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

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

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

Современные методы решения указанных задач оптимизации представлены в работах отечественных и зарубежных ученых (J1. В. Канторовича, Э. А. Мухачевой, И. В. Романовского, А. Ф. Валеевой, Т. М. Сиразетдинова, J. О. Berkey и P. Y. Wang, A. Lodi, S. Martello и D. Vigo, S. P. Fekete и J. Schepers, D. Pisinger, A. Clautiaux, E. Hopper и С. H. Turton, К. R. Baker и G. D. Scudder, J. J. Kanet, L. A. Wolsey, D. Biskup и T. C. Cheng и других) и позволяют получать хорошие решения. Однако известные методы решают задачи рационального раскроя и составления расписания отдельно друг от друга, а известные математические постановки покрывают лишь часть описанной практической проблемы. В реальных условиях, как правило, требуется комплексное рассмотрение проблемы и ее решение как задачи многокритериальной оптимизации. Этот главный недостаток существующих методов обосновывает необходимость разработки и применения новых методов и алгоритмов.

Во второй главе «Постановка задачи раскроя листового материала с учетом опережения-запаздывания производства заготовок и методы ее решения» предложена математическая модель динамической задачи гильотинного раскроя листового материала с учетом опережения-запаздывания производства заготовок (JIT-2BP). В отличие от известных работ, предлагаемая модель полностью описывает рассматриваемую проблему как задачу двухкритериальной оптимизации.

Пусть задано:

• множество параллельных гильотинных режущих машин k&Q={l,...,q};

• множество прямоугольных заготовок /е/={],...,ri), имеющих длину /, и ширину W/, (/,, w,ejV);

• множество прямоугольных листов jeB={l,...,m}, имеющих длину Lj и ширину Wj, (Lh WjeN);

• множество карт раскроя s<aR={\,...,m'}, т '< т, формируемых во времени на основании листа jeB.

Каждая заготовка i определяется следующими характеристиками:

• фиксированная ориентация;

• индивидуальный детерминированный срок изготовления 4;

• штраф по опережению or, за единицу времени;

• штраф по запаздыванию Д за единицу времени.

Множества заготовок / и листов В являются динамическими и изменяются во времени. Множество листов В может быть разделено на два непересекающихся подмножества: В* с В - множество форматных листов материала', и В* = В \ В * - множество деловых остатков2.

Каждая карта раскроя s имеет индивидуальное время обработки pSk на машине keQ, где psk определяется функцией щ(рагат^3, зависящей от параметров s.

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

уе.а*

следующие условия:

• Условие непересеченш заготовок с границами листа и взаимного непересечения заготовок (С. Chen, 1991; Н. Onodera, 1995).

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

hij= 1, если заготовка /' располагается левее заготовки j, {0,1}; b,j= 1, если заготовка i располагается ниже заготовки j, bye {0,1}; uis=1, если заготовка / назначена листу 5, uise {0,1}.

Пара переменных (х^у,) соответствует координате левого нижнего угла заготовки i, Xj,y, eZ\

Тогда должна выполняться следующая система неравенств:

v/je/, .'</, SE/i; (1)

x^Xj + Lh^L-l,, Vi.jel; (2)

y^yj+Wb^W-w,, gI; (3)

х,<1,-1,+(1-и„)и Vie I, seB; (4)

у, <W1-v/i +(l~ul3)fV, VieI, seB; (5)

JX = 1, V; e /, (6)

1 На практике соответствуют стандартным форматным листам материала и заказываются у производителя материалов.

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

аспила листов от предыдущих заказов.

На практике функция, определяющая время обработки карты раскроя (раскроя листа), мо-

жет зависеть от таких технологических операций как установка материала на режущую ма-

шину, настройка машины, прифуговка, производство реза, поворот и сдвиг материала.

где L = max{Ls} и W = шах{ж,} - максимальная длина и ширина листа соответствен sbB

венно; условие (1) описывает непересечение двух заготовок друг с другом; условия (2) и (3) описывают попарное относительное расположение двух заготовок по горизонтали и вертикали соответственно; условия (4) и (5) описывают непересечение заготовки с вертикальными и горизонтальными границами листа соответственно; условие (6) подразумевает назначение заготовки одному из листов.

• Условие гтьотинности разделения прямоугольных областей листа (Т. М. Сиразетдинов, 2004).

Для любой прямоугольной области pes, seR с размерами (/,w):(/*/,) v(и>* w.), Vie/? (рис.1), выполняется условие разделения на две прямоугольные области p'~(l',w') иp"~(l",w"):

((/'+/"= /) л (w'= w"= w)) v ((/'= Г= I) л (w'+w"= w)), [если iep', mo Hp" [если i^p", mo i£p'

Г I"

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

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

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

а„=\, если обработка карты раскроя ,? предшествует обработке карты раскроя V, а,„е {0,1}; 1, если карта раскроя £ назначена для выполнения на машине к,

4 соответствует моменту начала обработки карты раскроя .

Тогда должна выполняться следующая система неравенств:

¿60; (7) (8)

(9)

(10)

максимально возможное время обработки всех карт

teg

>0, Vie Л;

ksQ

где r = max{rf.}+£max{At} -

раскроя на параллельных машинах; условие (7) описывает попарное непересечение временных интервалов обработки карт раскроя, назначенных одной машине; условие (8) описывает попарное взаимное расположение во времени интервалов обработки карт раскроя; условие (9) ограничивает выход момента начала обработки за границу начального момента времени для каждой из карт раскроя; условие (10) подразумевает назначение карты раскроя одной из режущих машин.

Требуется найти допустимое расписание, минимизирующее сумму взвешенного опережения и запаздывания по всем картам раскроя:

где Gs соответствует множеству заготовок, входящих в карту раскроя s. Et =тах{0Д -с,} является опережением, а 7] =max{o,cs -с/,.} - запаздыванием изготовления заготовки i соответственно. Момент времени с, соответствует моменту окончания обработки карты раскроя s, запланированной на машине k&Q : fsk= 1. Этот момент вычисляется как сумма момента начала обработки карты раскроя ts и времени его выполнения pst на машине к, для которой^=1, т.е. cs = ts + psk. Заготовка / считается выполненной раньше срока, если cs < d, и выполненной позже срока в противном случае.

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

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

j=i ¡е а,

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

Таблица 1. Соотношение между типами используемых интеллектуальных агентов

В-агент (лист материала, карта раскроя) 1-агент (заготовка) М-агент (режущая машина)

Коммуникация взаимодействие с 1-агентами взаимодействие с В-агентами взаимодействие с В-агентами

Назначение формирования карты раскроя присоединение к карте раскроя 1. Расчет времени изготовления карты раскроя. 2. Хранение информации о назначенных картах раскроя.

Конкуренция с др. В-агентами за лучших 1-агентов с др. 1-агентами за лучших В-агешов -

Цель максимальная эффективность карты раскроя минимизация негативного влияния на опережение-запаздывание карты раскроя -

Целевой параметр коэффициент раскроя приращение значения опережения-запаздывания карты раскроя -

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

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

Рисунок 2 - Функциональная модель процесса построения решения

1. Задача выделения критической области производственного расписания.

2 Задача определения множества прямоугольных листов (В-агентов) для размещения заготовок критической области.

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

4. Задача распределения сформированных карт раскроя по параллельным машинам.

5. Задача восстановления допустимости решения.

s = l

к = 1

t, время

лист 1

-у i "

карты раскроя ~~

—¡-агенты — (заготовки)

Г> М-

лист 2

к = 1-к = 2 •

s = 2

к = 2

t, время

Рисунок 3 - Последовательность построения решения агентно-ориентированной системой

Для решения задачи выделения критической области производственного расписания предложено использовать алгоритм разностного пикового группирования (R. Yager и D. Filev, 1984), основанный на функции Гаусса. Применение этого алгоритма позволяет идентифицировать интервалы временной оси с высокой плотностью распределения плановых сроков изготовления заготовок. В конечном счете, соответствующие таким интервалам критические области

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

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

Для решения задачи построения карт раскроя, минимизирующих локальное взвешенное опережение-запаздывание предложен метод, основанный на взаимодействии интеллектуальных агентов системы. B-агенты выполняют процесс формирования карты раскроя, направленный на размещение заготовок согласно эвристическому алгоритму EGBL (улучшенный гильотинный нижний-левый) с целью увеличения коэффициента раскроя листа. I-агенты применяют процесс присоединения к карте раскроя, направленный на поиск такой карты раскроя, присоединение к которой окажет наименьшее негативное влияние на взвешенное опережение и запаздывание входящих в нее заготовок.

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

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

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

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

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

1) Эффективность использования материала: коэффициент раскроя или количество затраченных листов.

2) Значение взвешенного опережения-запаздывания.

3) Уровень делового остатка.

4) Количество заготовок, произведенных точно в срок.

5) Общее количество сформированных карт раскроя.

6) Общее время раскроя,

где 1 и 2 являются основными критериями, а 3-6 - дополнительными.

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

<Рк (tk_ycm Js,Vk •flsJk noe.Jk dos. пов. dos.)»

где tkj,cm. - время установки листа на режущую машину к; /,- общая длина пути реза карты раскроя s; vk- скорость раскроя машиной к\ ns~ количество необходимых поворотов материала при раскрое карты s; tk noe. - время поворота материала на машине к; tkjo«. - время доводки материала до линии реза на машине к.

Первая серия экспериментов проведена на наборе тестовых примеров с неизвестным оптимумом с целью исследования влияния количества режущих машин q на эффективность решения. Сравнительный анализ результатов эксперимента, проведенный на основе значений нижних границ Fekete и Schepers (рис. 4, а), показывает:

• В динамических условиях АО-система имеет низкую эффективность использования материала (О(АОудинам)), как при большом, так и малом количестве режущих машин q. Максимальная эффективность использования материала достигается при q=5.

• В статических условиях изменение числа машин q не влияет на эффективность использования материала (О(АО стат)).

• АО-система имеет высокую эффективность при формировании карт раскроя.

Кроме того, увеличение количества режущих машин q оказывает следующее влияние на различные критерии эффективности:

• понижает значение взвешенного опережения-запаздывания (рис. 4, б);

• увеличивает число заготовок, произведенных точно в срок;

• увеличивает общее количество сформированных карт раскроя;

• увеличивает общее время раскроя.

Вторая серия экспериментов проведена на наборе примеров с известным оптимумом с целью исследования зависимости эффективности использования материала от количества типоразмеров листов. Анализ полученных результатов показывает (рис. 4, в), что увеличение числа используемых типов листов материала оказывает следующее влияние:

• повышает эффективность использования материала (РС(АО_динамj) в динамических условиях;

• понижает эффективность использования материала (РС(АО_стат)) в статических условиях.

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

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

• решение АО-системы высокоэффективно с точки зрения использования материала (рис. 4, г) и уровня делового остатка только при среднем размере критической области (~ 30-120 мин.);

• решение АО-системы высокоэффективно с точки зрения опережения-запаздывания (рис. 4, д) только при среднем размере критической области (~ 40-80 мин.);

• общая продолжительность выполнения раскроя и количество карт раскроя снижается с увеличением размера критической области;

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

Для примеров средней размерности, имитирующих среднюю загрузку режущей машины, установлено следующее:

• решение АО-системы высокоэффективно с точки зрения использования материала только при среднем размере критической области (~ 40-120 мин.);

• значение взвешенного опережения-запаздывания (рис. 4, е) возрастает с увеличением размера критической области (неэффективно при размере более 80 мин.).

Четвертая серия экспериментов проведена на основе данных реального производства. Сравнение результатов решения, полученных АО-системой, с результатами двух эвристических алгоритмов построения плана раскроя («раскрой при поступлении заказа» и «раскрой по востребованию заготовки») позволяет сделать выводы, что при различных комбинациях управляющих параметров АО-система дает следующие преимущества:

• Увеличение эффективности использования материала на -30%;

• Снижение опережения-запаздывания при выполнении плана раскроя на-60%;

• Снижение уровня делового остатка на -25%;

• Сокращение количества карт раскроя на -75%;

• Сокращение продолжительности раскроя на -35%;

• Возможность производства заготовок точно-в-срок.

В конечном итоге в зависимости от комбинации управляющих параметров АО-система способна предоставить:

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

• либо решение с меньшим значением опережения-запаздывания и большим количеством заготовок, произведенных точно-в-срок.

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

4=1 : 4=2 • 4=3 : 4=4

;й01АО_ди*ЭМ); 1,24 :Й0[А0 оэт) I :яг

д=6 : ()=7 : 4=8 :

; ш 1,18

1,18 I 1,19 ; 1,20 : 1,21 • 1,21 :

1,02 : 1,02 : 1,02 ! 1,02 I 1,02 !

• ч=1 | 4=2 : 4=3 | 4=4 4=5 : 4=6 ! 4=7 ; ч=8 4=9 : 4=10 ; 5 \tfET ¡252561 4227,: 2172,: 1573,: 1184, 951,4 ! 707,5 | 540,4 1396,5 : 276,6 !

94,00 :

92,00 ;

90,00 |

88,00 >

Ш

; й=г ; (1=з ; о=а ; ¿=5 ; а=б • d=7 • <*=8 ; ¿=э

йРС(А0_динам1; 75Д8 76,60 РС(АО_сгаг) : 90,17 : 89,00 :

175000

170000 ;

165000 :

160000 ;

155000 :

150000 :

145000 ; 140000

135000 ; 130000

7738 ; 88,71 :

: 78,05 : 88,19

Ж , (1=10 ; 78,39 ] 88,22 '

V»

время (минуты)

время (минуты)

г

25000 20000 ; 15000 : 10000 5000

Зрамя {у.ппуТЬ

д е

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

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

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

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

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

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ОПУБЛИКОВАНЫ В РАБОТАХ

В рецензируемых журналах из списка ВАК

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

2. Агентно-ориентированный подход для решения задач оптимизации рюкзачного типа / С. Ю. Поляковский, Р. М'Халлах // Лекционные материалы по компьютерным наукам: новые тенденции в приложениях искусственного интеллекта. 20-я Междунар. конф. 1ЕА/А1Е, Киото, 2007. Спрингер. Вып. 4570. С. 1098-1107. (Статья на англ. яз.).

3. Агентно-ориентированный подход для решения задачи двумерной гильотинной контейнерной упаковки / С. Ю. Поляковский, Р. М'Халлах // Ев-

ропейский журнал по исследованию операций. 2009. Т. 192. С. 767-781. (Статья на англ. яз.).

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

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

5. Свид. о per. программы для ЭВМ № 2006612022 /С. Ю. Поляковский, А. Ф. Валеева, Д. В. Попов. Программа решения задачи двумерного раскроя на основе метода юго-западного угла. Зарег. РосАПО, 14 июня 2006.

6. Метод юго-западного угла для решения задачи двумерной контейнерной упаковки / С. Ю. Поляковский, Э. А. Мухачева, А. Ф. Валеева // Матер. Междунар. конф. "3rd ESICUP Meeting". Порто, Португалия, 2006. http://paginas.fe.up.pt/~esicup/. (Статья на англ. яз.).

7. Решение задачи гильотинного раскроя методом юго-западного угла в условиях единичного производства / С. Ю. Поляковский // Сб. Уфимск. междунар. зимн. шк.-конф. по математике и физике для студентов, аспирантов и молодых ученых. Уфа: БГУ, 2006. С. 22-24.

8. Мультиагентный метод решения задачи двумерной гильотинной контейнерной упаковки / С. Ю. Поляковский // Компьютерные науки и информационные технологии CSIT' 2006: 8-я междунар. конф. Карлсруэ, Германия, 2006. Т. 2. С. 163-169. (Статья на англ. яз.).

9. Интеллектуальная система для решения динамической задачи гильотинной упаковки в разнородные листы / С. Ю. Поляковский, Р. М'Халлах 11 Материалы междунар. конф. "GOR Operations Research 2007". Саарбрюккен, Германия, 2007. С. 203-208. (Статья на англ. яз.).

10. Агентно-ориентированный подход для решения задачи двумерной гильотинной контейнерной упаковки / С. Ю. Поляковский, А. Ф. Валеева // Математическое программирование и приложения: сб. тезисов XIII Всерос. конф. Екатеринбург: УрО РАН, 2007. С. 183-184.

11. Агентно-ориентированная модель для решения оптимизационных задач рюкзачного типа / С. Ю. Поляковский, Р. М'Халлах // Компьютерные науки и информационные технологии CSIT' 2007: 9-я междунар. конф. Уфа, 2007. Т. 3. С. 45-50. (Статья на англ. яз.).

12. Улучшенная эвристика для решения задачи гильотинной упаковки в разнородные листы / С. Ю. Поляковский, А. Ф. Валеева, Р. М'Халлах // Компьютерные науки и информационные технологии CSIT' 2007 : 9-я междунар. конф. Уфа, 2007. Т. 2. С. 34-37. (Статья на англ. яз.).

13. Интеллектуальная система для решения динамической задачи гильотинной упаковки в разнородные листы / С. Ю. Поляковский, Р. М'Халлах // Матер. Европ. конф. по исслед. операций "EURO ХХШ". Германия, Бонн, 2009. С. 567. (Статья на англ. яз.).

Диссертант

_ С. Ю. Поляковский

ПОЛЯКОВСКИЙ Сергей Юрьевич

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

(В ДЕРЕВООБРАБАТЫВАЮЩЕЙ И МЕБЕЛЬНОЙ ПРОМЫШЛЕННОСТИ)

05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

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

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

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

Оглавление.

Введение.

1. Анализ современных методов минимизации.потерь при управлении раскроем листового материала.^

1.1. Актуальность исследуемой проблемы.р

1.2. Организация, планирование и управление производство*^ под заказ».^

1.3. Содержательная постановка задачи.

1.4. Анализ методов решения задач раскроя листового материала и составления расписания.

Выводы по 1 главе.^

2. Постановка задачи раскроя листового материала с учетом опережения-запаздыванияпроизводства заготовок и методы ее решения.^

2.1. Математическая модель задачи раскроя; листового материала с учетом опережения-запаздывания производствшзаготовок

2.2. Задача многокритериальной^оптимизации-и>методы ее решения

2.3. Агентно-ориентированная концепция решения задачи раскроя листового материалам учетом опережения-запаздывания производства заготовок.^

Выводы по12 главе.У j

3. Агентно-ориентированная;система для решения задачи минимизации потерь при управлении раскроем листового материала

3.1. Процесс построения решения агентно-ориентированной системой1 73 3:2. Принятие решенияшри поступлении срочных заготовок,.;.

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

4. Численные'эксперименты.• ду

4.1. Гёнерацияшабора тестовых примеров.I.;. gg

• 4.2. Анализ результатов численного эксперимента с использованием? ' • набора сгенерированных тестовых примеров:.г

1 (jjL

4.3; Исследование эффективности решения на примере реального ' ; производства.Г

Выводы по 4 главе .|.

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

Актуальность темы исследования

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

Для стабильного положен^3 на рынке производители вынуждены учитывать новые тенденции, применяя новые технологии и специальное программное обеспечение. Это дает возможность значительно повысить эффективность и= гибкость производства, гарантируя производителям высокую прибыль и привлечение новых юги^ктов; •

Сегодня потребность производителей в> технологиях управления; и оптимизацию производства ^есгивно удовлетворяется компаниями-разработчиками, но часто предлаг^-^:м:ые мет°Ды Решения задач являются либо узко специализированными^ либо с^лхишком'общими. В первом случае - узкая специализация мешает их, использа11ию для решения класса задач раскроя при различных производственных: ^граничениях. Во втором случае - общие г методы применяются для нескольких задач, но при этом предлагаемое рeiu^njje может иметь низкое качество. Поэтому возрастает необходимость в разра£><зт:к:е новых методов, поддерживающих внедрение эффективных проблеоч<аю:о-ориентированных алгоритмов и гибкую адаптацию для задач раскроя с учетом различных условий производства.

В диссертационной работе проводятся исследования в этом направл^вснзи:, и решается задача рационального раскроя листового материала с и:«^л1е»ю достижения минимума опережения и запаздывания при производстве заготовок на стадии предварительного распила в деревообрабатывающей и мебелЕ»н:о;й: промышленности. Как известно, задачи раскроя относятся к классу NP-Tpyv£CQZE»rx: задач комбинаторной оптимизации. Это означает, что детерминирова^гвсый: метод полиномиальной сложности для их решения не известен, и оптимал^^а^^^ результат в общем случае может быть получен только за экспоненциальное время. Поскольку на практике задачи раскроя нередко имеют боль-хную размерность, а результат должен быть получен за приемлемое врем^з:^ то актуальной является проблема- разработки эффективных приближе^з^Езгых методов решения.

Цель работы

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

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

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

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

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

5. Исследовать эффективность предложенных методов и алгоритмов с помощью численного эксперимента. Выработать рекомендации по их применению в реальном производстве.

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

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

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

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

2. Методика повышения эффективности управления раскроем листового материала в условиях неопределенности.

3; Агентно-ориентированная концепция решения задачи раскроя листового материала с учетом опережения-запаздывания- производства заготовок, основанная на агентно-ориеытировашюм подходе; 4. Математическое обеспечение для решения динамической задачи раскроя листового материала с учетом опережения-запаздывания производства заготовок на основе предложенной концепции:

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

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

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

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

3. Методы и алгоритмы для решения задачи раскроя листового материала с учетом опережения-запаздывания производства заготовок на основе предложенной концепции. Их новизна ' опреДеляется новизной задачи раскроя, для получения допустимого решения которой требуется решить серию специальных подзадач:

3.1. Задача' выделения критических областей оперативно-календарного плана;

3.2. Задача определения множества прямоугольных листов, необходимого

- для размещениязаготовок критической' о власти;

3.3. Задача построения1 карт раскроя, ^усинимизирующих локальное взвешенное опережение-запаздывание;

3.4. Задача- распределения карт раскроя- по параллельным режущим машинам для их обработки. w

Практическая значимость работы

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

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

Внедрение результатов работы в виде методики повышения эффективности управления раскроем листового материала при производстве заготовок, и рабочего прототипа программного обеспечения для, оптимизации стадии предварительного распила осуществлено в ООО «ДИП» («Двери и пиломатериалы»), г. Ростов-на-Дону.

Апробация работы и публикации

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

1. Седьмой международный симпозиум по информатике и информационным технологиям CSIT' 2005 (Уфа - 2005).

2. Третья международная конференция по раскрою и упаковке 3rd ESICUP Meeting 2006 (Porto, Portugal - 2006)'. .'

3. 20-ая международная конференция по промышленным, инженерным идругим приложениям в области прикладных интеллектуальных систем

1 •

Kyoto, Japan-2007).

4. 22-ая европейская, конференция по исследованию операций EURO ХХП, (Praha, Czech Republic - 2007).

5. Международная конференция Германского общества по исследованию* операций Operations Research 2007 (Saarbrucken, Germany - 2007).

6. Девятый международный симпозиум по информатике и информационным технологиям CSIT' 2007 (Уфа - 2007).

7. Пятая международная конференция по раскрою и упаковке 5th ESICUP Meeting 2008 (L'Aquila, Italy - 2008).

8. 23-ая европейская конференция по исследованию операций EURO XXIII (Bonn, Germany - 2009).

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

Диссертация состоит из введения, 4-х глав, выводов и списка литературы. Работа изложена на 152 страницах машинописного текста, кроме того, содержит 42 рисунка и 2 таблицы. Библиографический список включает 151 наименование и занимает 14 страниц.

Выводы по 4 главе

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

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

• В динамических условиях АО-система имеет низкую эффективность использования? материала; как, при большом, так и малом; количестве режущих машин q. Максимальная: эффективность использования; материала достигается при q=5:

• В статических условиях изменение5 числа машин q не влияет на эффективность использования материала. ,

• АО-система имеет высокую эффективность при формировании карт раскроя.

Кроме того, увеличение количества режущих машин q оказывает следующее влияние на различные критерии эффективности:

• понижает значение взвешенного опережения-запаздывания;

• увеличивает число заготовок, произведенных точно в срок;

• увеличивает общее количество сформированных карт раскроя;

• увеличивает общее время раскроя.

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

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

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

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

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

• решение АО-системы высокоэффективно с точки зрения использования материала и уровня делового остатка только при среднем размере критической области (~ 30-120 мин.);

• решение АО-системы высокоэффективно с точки зрения опережения-запаздывания только при среднем размере критической области 40-80 мин:);

• общая- продолжительность выполнения раскроя- и количество карт раскроя , снижается с увеличением размера критической.области;

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

Для примеров средней размерности, имитирующих среднюю загрузку режущей машины, установлено следующее:

• решение АО-системы высокоэффективно с точки зрения использования материала только при среднем размере критической области 40-120 мин.);

• значение взвешенного опережения-запаздывания возрастает с увеличением размера критической области (неэффективно при размере более ~ 80 мин.).

Четвертая серия экспериментов проведена на основе данных реального производства. Сравнение результатов решения, полученных АО-системой, с результатами двух эвристических алгоритмов построения плана раскроя («раскрой при поступлении заказа» и «раскрой по востребованию заготовки») позволяет сделать выводы, что при различных комбинациях управляющих параметров АО-система дает следующие преимущества:

• Увеличение эффективности использования материала на —30%;

• Снижение опережения-запаздывания при выполнении плана раскроя на -60%;

• • Снижение уровня делового остатка на -25%;

• Сокращение количества карт раскроя на -75%;

• Сокращение продолжительности раскроя на —35%;

• Возможность производства заготовок точно-в-срок.

В конечно итоге в зависимости от комбинации управляющих параметров АО-система способна предоставить:

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

• либо решение с меньшим значением опережения-запаздываншг и большим, количеством заготовок, произведенных точно-в-срок.

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

137

Заключение

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

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

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

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

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

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

139

1. Агенты, многоагентные системы, виртуальные сообщества: стратегическое направление в информатике и искусственном интеллекте / В- Б. Тарасов // Новости искусственного интеллекта. 1998. №2. С. 5-63.

2. Адаптивные поисковые алгоритмы для решения сложных задач многокритериальной оптимизации / А. П. Гуменникова // Дис- канД- техн-наук. Сибирский гос. аэрокосм, ун-тет, Красноярск. Июне» 2,006. 129 с.

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

4. Введение в экономико-математическое моделирование / -А- Лотов // Наука: 1984. С. 378-392.

5. Выбор оптимальных параметров в задачах со многими критериями / И. М. Соболь, Р. Б. Статников // М.: Дрофа. 2006. С. 54-78.

6. Древесно-плитные материалы, http://www.faneraoptom.ru/articles/

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

8. Конструирование мебели. Справочник / П. А. Андрианов // ^зд. «ПрофиКС». 2006. С. 4-17.

9. Логистика/Б. А. Аникин, Т. А. Родкина// Проспект. 2008- С- 102-115.

10. Автоматизация^ мебельного производства — миф шхй . Достижимая реальность? // Мебельное обозрение (отраслевой журнал)- Ноябрь 2009. №60. С. 11-16.

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

12. Методы локального поиска оптимума в задачах ортогонального раскроя и упаковки: аналитический обзор и перспективы развития / Э. А. Мухачева,

13. A. С. Мухачева, А. Ф. Валеева, В. М. Картак // Информационные технологии. М.: Новые технологии, Приложение №5. 2004. С. 1-17.

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

15. Многоагентные системы. Обзор / В. И.Городецкий, М. С. Грушинский, А.

16. B.Хабалов // Новости искусственного интеллекта. №2. 1998. С. 64-116.

17. Многокритериальная оптимизация: теория, вычисления и приложения / Р. Штойер // М.: Радио и связь. 1992. С. 396-405.

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

19. Оптимизация при наличии ограничений / А. Г. Трифонов. http://matlab.exponenta.ru/optimiz/bookl/15.php

20. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика / В. Б. Тарасов. // М.: Эдиториал УРСС. 2002. С. 44-57.

21. Парето-оптимальные решения многокритериальных задач / В. В. Подиновский, В. Д. Ногин // М.: ФИЗМАТЛИТ. 2007. С. 17-26.

22. Планирование на предприятии. Учебное пособие / Е. А Кобец // Таганрог: Изд-во ТРТУ, 2006. С. 15-24.

23. Принятие решений в многокритериальной среде: количественный подход / В. Д. Ногин // М.: ФИЗМАТЛИТ. 2004. С. 34-39.

24. Проблемы малого мебельного предприятия // «Дерево-RU». Деловой журнал по деревообработке. 2007. №4 (43). С. 94-100.

25. Проектирование гильотинного раскроя листового и рулонного материала с использованием послойных алгоритмов / Т. М. Сиразетдинов // // Дис. канд. техн. наук. Уфимский гос. авиац. техн. ун-тет, Уфа. Апрель 2004. 140 с.

26. Расчет рационального раскроя материалов / Л. В. Канторович, В. А. Заллгаллер // Лениздат. 1951. С. 22-31.

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

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

29. Стратегии развития производства мебельной фурнитуры. // Фабрика мебели. 2008. №5. С. 68-72.

30. A branch and bound algorithm for the single machine earliness and tardiness scheduling problem / C. F. Liaw // Computers & Operations Research. 1999. Vol. 26, pp. 679-693.

31. A branch and bound approach for single machine scheduling with earliness and tardiness penalties / P. C. Chang // Computers and Mathematics with Applications. 1999. Vol. 37, pp. 133-144.

32. A column generation based decomposition algorithm for a parallel machine justin-time scheduling problem / Z. L. Chen, W. B. Powell // European Journal of Operational Research. 1999. Vol. 116, pp. 221-233.

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

34. A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights / C. Y. Lee, J. Y. Choi // Computers &

35. Operations Research. 1995. Vol. 22, pp. 857-869:i

36. A heuristic for common due date assignment and job scheduling on parallel machines / Т. С. E. Cheng // Journal of the Operational Reasearch Society. 1989. Vol. 40, pp. 1129-1135.

37. A Linear Programming Approach to the Cutting-stock Problem / P. C drilmore, R. E. Gomory // Operations Research. 1961. Vol. 9, pp. 849-859.

38. A lower bound for the non-oriented two-dimensional bin packing problems / M. Dell'Amico, M. Martello, D. Vigo // Discrete Appl. Math. 2002. VoL 118, pp. 13-24.

39. A new lower bound for the non-oriented two-dimensional bin-packing ^problem / A. Clautiaux Jouglet, J. El Hayek // Operations Research Letters. 200T^ "Vol. 35, pp. 365-373.

40. A new version of on-line variable-sized bin packing / G. Zhang /Л ^Discrete Applied Mathematics. 1997. Vol. 72, pp. 193-197.

41. A practical' solution to a fuzzy two-dimensional cutting stock ргоЫезгзгз- / F. G. Vasko, F. E. Wolf, K. L. Stott // Fuzzy Sets and Systems. 1989. Vol. 29, pp. 259-275.

42. A pseudopolynomial algorithm for sequencing jobs to minimize total ~fcs=*~r~diness / E. L. Lawler // Annals of Discrete Mathematics. 1977. Vol. 1, pp. 331-3^1-2.

43. A stabilized branch-and-price-and-cut algorithm for the multiple lengrtfln cutting stock problem / C. Alves, J. M. Valrio de Carvalho// European Joxirnal of Computers & Operations Research. 2008. Vol. 35, pp. 1315-1328.

44. A time indexed formulation" of non preemptive single machine so^irLecluling problems / J.P. Sousa, L.A. Wolsey // Mathematical Programming. 1Vol. 54, pp. 353-367.

45. Accelerating column generation for variable sized bin-packing pr<z>lz>lems / C. Alves, J. M. Valrio de Carvalho // European Journal of Operational lE^esearch. 2007. Vol. 18, pp. 1333-1352.

46. Agent theories, architectures, and languages: A survey / M. Wooldridge, N. R. Jennings // In: Proceedings of the ECAI-94 Workshop on Agent Theories, Architectures and Languages. Springer-Verlag. 1995. pp. 1-39.

47. Agent-based modeling and mapping of a manufacturing system / S. L. Wang, H. Zia, G. B. Tao, Z. Zhang // Journals of Materials Processing Technology. 2002. Vol. 129, pp. 518-523.

48. Agents in Overalls: Experiences and Issues in the Development and Deployment of Industrial Agent-Based Sytems / H.V.D. Parunak // International Journal of Cooperative Information Systems, 9(3) (2000), 209-228.

49. Algorithms for the variable sized bin packing problem / J. Kang, S. Park // European Journal of Operational Research. 2003. Vol. 14, pp. 365-372.

50. An agent-based approach to knapsack optimization problems / S.J. Polyakovsky R. M'Hallah // In: New Trends in Applied Artificial Intelligence, IEA/AIE 2007, Kyoto, Japan, 2007. Lecture Notes in Computer Science 4570 Springer 2007, pp. 1098-1107.

51. An agent-based approach to the two-dimensional guillotine bin packing problem / S. Polyakovsky, R. M'Hallah // European Journal of Operational Research. 2009. Vol. 192, pp. 767-781.

52. An analytical model for the container loading problem / C. S. Chen, S. M. Lee, Q. S. Shen//Journal of Operational Research. 1995. Vol. 80, pp. 68-76.

53. An empirical study of metaheuristics applied to 2D rectangular bin packing problem / E. Hopper, С. H. Turton // Studia Informatica. 2002. Vol. 2, pp. 77-92.

54. An empirical study of metaheuristics applied to 2D rectangular bin packing problem / E. Hopper, С. H. Turton // Studia Informatica. 2002'. Vol. 2, pp. 77-92.

55. An evolutionary algorithm for multiobjective optimization: the strength Pareto approach / E. Zitzler, L. Thiele // TIK Tech. Report No. 43, Swiss Federal-Institute of Technology (ETH). 1998.

56. An improved typology of cutting and packing problems / G. Wascher, H. Haussner, H. Schumann // European Journal of Operational Research. 2007. Vol. 183, pp. 1109-1130.

57. Approximation algorithms for partitioning small items in unequal bins to minimize the total size / P. Dell'Olmoa, M. G. Speranza // Discrete Applied Mathematics. 1999. 94, pp. 181-191.

58. Approximation algorithms for the oriented two-dimensional bin packing problem / A. Lodi, S. Martello, D. Vigo // European Journal of Operational-Research. 1999. 112, pp. 158-166.

59. Assignment Problems / R. Burkard, M. Dell'Amico, S. Martello. // SIAM. 2009. Pp 120-133.

60. ATOM Die Cutting Nesting Software, http://www.mfgsup.com/ /diecuttingsystems/cncdiecuttingequipment/nestingsoftware.html

61. Automatic Data Collection Systems: Observed Benefits and Problems / R. T. Christoph, S.P. Stevens, O.B. Christoph // International Journal of Operations & Production Management. 1992. Vol. 5, pp. 57-68.

62. Bin packing with divisible item sizes / E.G. Coffrnan, M.R. Garey, D.S. Johnson // Journal of Complexity. 1987. Voh-3, pp. 406-428.

63. Bounds on multiprocessing timing anomalies / R.L. Graham // SIAM: Journal on Applied Mathematics. 1969. Vol. 17, pp. 416-429.

64. Branch-and-bound placement for building block layout / H. Onodera, Y. Taniguchi, K. Tmaru // 28th ACM/IEEE Design Automation Conference. 1991. Vol. 99, pp. 433-439.

65. Comparison of agent-based scheduling to look-ahead heuristics for real-time transportation problems / M. Mes, M. Heijden, A. Harten // European Journal of Operational Research. 2007. Vol. 181, pp. 59-75.

66. Computer and Information Science Papers CiteSeer Publications Research Index, http:// citeseer. ist.psu.edu/

67. Computers and Intractability: A Guide to the Theory of NP-Completeness / M-R-Garey, D.S. Johnson . // W. H. Freeman. 1979. Pp. 201-206.

68. Concept Patterns Software, http://www.conceptpatterns.com/

69. Cutting optimization with variable sized stock and inventory status data / L. bCos, J. Duhovnik // International Journal of Production Research. 2002. Vol. 40, pp. 2289-2301.

70. Dynamic single-machine scheduling under distributed decision making / Г*-Dewan, S. Joshi // International Journal of Production Research. 2000. Vol. 3 8, pp. 3759-3777.

71. Earliness tardiness scheduling problems, II: deviation of completion times about a restrictive common due date / N.G. Hall, W. Kubiak, S.P. Sethi // Operations Research. 1991. Vol: 39, pp. 847-856.

72. Earliness-tardiness scheduling problems, I: weighted deviation of completion, times about a common due date / N.G. Hall, M.E. Posner // Operations Research. 1991. Vol.39, pp. 836-846.

73. Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem / Y. Hendel, F. Sourd // European Journal of Operational Research. 2006. Vol. 173, pp. 108-119.

74. Essentials of Fuzzy Modeling and Control / R. Yager, D: Filev // John Wiley, New York, 1984. Ppi 178-185.

75. Evolutionary Multi-objective Optimization in Uncertain Environments / C. Goh, К. C. Tan // Springer. 2009. Pp. 247-265.

76. Evolutionary Multiobjective Optimization. . Theoretical Advances and Applications / A. Abraham, J.C. Jain, R. Goldberg (Eds.) // Advanced Information and Knowledge Processing. Springer. 2005. Pp. 136-152.

77. Exact solution of the two-dimensional finite bin packing problem / S. Martello, D. Vigo //Management Science. 1998. Vol. 44, pp. 388-399.

78. FIPA Request Interaction Protocol Specification, http://www.fipa.org/specs.

79. Firma HOLZ-HER Reich Spezialmaschinen GmbH, http://www.holzher.de/.

80. General framework for bounds for higher-dimensional orthogonal packing problems / S. Fekete, J. A. Schepers // Mathematical Methods of Operations Research. 2004. Vol. 60, pp. 311-29.

81. Goal programming and extensions / J. P. Ignizio // Lexington Books, Lexington, MA, 1976. Pp. 223-241.

82. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems / A. Lodi, S. Martello, D. Vigo // INFORMS Journal on Computing. 1999. Vol. 11, pp. 345-357.

83. Improved1 heuristics for the early/tardy scheduling problem with no idle time / J. Valente, R. Alves // Computers & Operations Research. 2005: Vol. 32(3), pp. 557-569.

84. Productivity Press; Л 998: Pjp; 102-118: 89. Knapsack Problems: Algorithms and Computer Implementations / S. Martello, P. Toth // John Wiley& Sons, Chichester-New York. 1990. Pp.116-126.

85. Linear Programming Cutting Problems / E.A. Mukhacheva, V.A. Zalgaller // International Journal of Software Engineering and Knowledge Engineering. 1993. Vol. 3 (4), pp. 463-476.

86. Lower Bounds and Reduction procedures for the Bin Packing Problem / S. Martello, P. Toth // Discrete Applied Mathematics. 1990. Vol. 28, pp. 59 70.

87. Make-To-Order Assembly Management / R. Kolisch // Springer Verlag, 2001. pp. 41 59.

88. Make-to-Order vs. Make-to-Stock in a Production-Inventory System with General Production Times / A. Arreola-Risa, G. DeCroix // IIE Transactions. 1998. Vol. 30, pp. 705-713.

89. Management models and industrial applications of linear programming / A. Charnes, W.W. Cooper // Wiley, New York, 1961. Pp. 117 136.

90. Mathematical methods for geometric design / Y.G. Stoyan // in: Advances in CAD/CAM: Proceeding PROLAMAT'82, Leningrad, USSR, 16-18 May 1982. North Holland. 2003. pp. 67-86.

91. MES-системы с точки, зрения организации производства / А. Р. Залыгин // ERPNEWS, 2007, http://erpnews.ru/doc2749.html.

92. MES-системы, как они есть или эволюция систем планирования производства / Е.Б. Фролов, P.P. Загидуллин // «Станочный парк», № 10, 2008, С. 31-37.

93. Metaheuristics in combinatorial optimization: Overview and conceptual comparison / C. Blum, A. Roli // ACM Computing Surveys. September 2003. 35, no. 3, pp. 268-308.

94. Minimizing the average deviation of job completion times about a common due date / J J. Kanet // Naval Research Logistics Quarterly. 1981. Vol. 28, pp. 643651.

95. Minimizing total earliness and tardiness on a single machine using a hybrid heuristic / R. M'Hallah // Computers & Operations Research. 2007. Vol. 34 (10), 3126-3142.

96. Minimizing weighted absolute deviation in single machine scheduling / T.D. Fry, R. Armstrong, J. Blackstone // HE Transactions. 1987. Vol. 19, pp. 445-450.

97. Models and algorithms for three-stage two-dimensional: bin packing / J. Puchinger, G. R. Raidl // European Journal of Operational» Research. 2006; Vol. 183, pp. 1304-1327. .

98. Modern heuristic optimization techniques theory and applications to power systems /K.Y. Lee, M.A. El-Sharkawi (edit) // IEEE Press. 2008. Pp. 59 70.106; Multicriteria optimization / M. Ehrgott// Springer. 2005. Pp.289- 303.

99. Multi-Objective Optimization using Evolutionary Algorithms / K. Deb // Wiley, 2002. Pp. 147 160.

100. Multiobjective Programming and Goal Programming Theoretical Results and Practical Applications / V. Barichard, M. Ehrgott, X. Gandibleux, V. T'Kindt (Eds.) // Lecture Notes in Economics and Mathematical Systems. 2009. Vol. 618. Pp. 30 48.

101. Multiple Criteria Optimization: Theory, Computations, and Application / R.E. Steuer // New York: John Wiley & Sons. 1986. Pp. 49 62. ' , . •

102. Multiple machine scheduling with earliness, tardiness and completion time penalties"/ D. Biskup, Т. С. E. Cheng // Computers & Operations Research; 19991 Vol. 26, pp: 45-57.

103. Multiple objective metaheuristic algorithms for combinatorial optimization / A. Jaszkiewicz // Habilitation thesis, Poznan University of Technology. 2001. Pp. 98-110.

104. Multiple objective optimization with vector evaluated genetic algorithms / J.D. Schaffer // In: Proceedings of the International Conference on Genetic Algorithms and Their Applications, Pittsburgh, IEEE. July 24-26, 1985. Pp. 93100.

105. New classes of lower bounds for bin packing problems / S.P. Fekete, J. Schepers //Math. Programming. 2001. Vol. 91, pp. 11-32.

106. New reduction procedures and lower bounds for the two-dimensional bin-packing problem with fixed orientation / J. Carlier, F. Clautiaux, A. Moukrim // Computers & Operations Research. 2007. 34, pp. 2223-2250.

107. No free lunch theorems for optimization / D.H: Wolpert, W.G. Macready // IEEE Trans Evol Сотр. 1997. Vol. 1, pp. 67-82.

108. On dynamic bin packing: An improved lower bound and resource augmentation analysis / W.T. Chan, P.'W.H. Wong, F.C.C. Yung // Lecture Notes of Computer Science. 2006. Vol. 4112, pp. 309-319.

109. On-packing two-dimensional bins / F. K. R. Chung, M. R. Garey, D. S. Johnson // SLAM: Journal of Algebraic and Discrete Methods. 1982. Vol. 3, pp. 66-76.

110. On the general solution for a class of early/tardy problems / P: De, J. B. Ghosh;, C.E. Wells // Computers& Operations Research. 1993. Vol. 20, pp. 141-149.

111. Operations management / W. J. Stevenson // McGraw-Hill/Irwin: 2007. Pp. 123140.

112. Optimize Now, or There Will Be No Tomorrow / M. BenBassat // Plataine. http://www.plataine.com/mbb0907.

113. Order Assignment and Scheduling in a Supply Chain / Z. L. Chen, G. Pundoor // Operations Research. May-june 2006. Vol. 54, № 3, pp. 555-572.

114. Packing items to feed assembly lines / M. C. de Souza, C. R. V. de Carvalho, W.B. Brizon // European Journal of Operational Research. 2008. Vol. 184, pp. 480-489.

115. Parallel genetic algorithms for the earliness-tardiness job scheduling problem with general penalty weights / C. Y. Lee, S.J . Kim // Computers & Industrial Engineering. 1995. Vol. 28, pp. 231-243.

116. Parallel Machine Earliness and Tardiness Scheduling with Proportional Weights / H. Sun, G. Wang // Computers & Operations Research. 2003. Vol. 30, pp. 801808.

117. Pareto simulated annealing—a metaheuristic technique for multiple-objective combinatorial optimization / P. Czyzak, A. Jaszkiewicz // Journal of Multi-Criteria Decision Analysis. 1998. Vol. 7, pp. 34-47.

118. Plataine White Papers / Plataine // http://www.plataine.com/articles/

119. Production Chain Optimization: Basic Principles / M. BenBassat //'Plataine. http://www.plataine.com/mbb0806.

120. Recent advances on two-dimensional bin packing problems / A. Lodi, S. Martello, D. Vigo // Discrete Applied Mathematics. 2002. Vol. 123, pp. 379396.

121. Resource augmentation for online bounded space bin packing / J. Csirik, G.J. Woeginger / Journal of Algorithms. 2002. Vol. 44, pp. 308-320.

122. Sciencedirect Database, http://www.sciencedirect.com

123. Scopus citation database of research'literature, http://www.scopus.com

124. Sequencing with earliness and' tardiness penalties: a review / K. R. Baker, G. D. Scudder // Operations Research. 1990. Vol. 38, pp. Vol. 22-36;

125. Single machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches / M. Feldmann, D. Biskup // Computers & Industrial Engineering. 2003. Vol. 44, pp. 307-323.

126. Solving the variable size bin packing problem with dicretized formulations / I. Correia, L. Gouveia, F. Saldanha-da-Gama // Computers & Operations Research. 2008. Vol. 35, pp. 2103-2113.

127. Springer Science, http://www.springer.com

128. Technology to the Rescue Then and Now / W. Hefner // Plataine. http://www.plataine.com/hefnerl207.

129. The one machine problem with earliness and tardiness penalties / F. Sourd, S. Kedad-Sidhoum//Journal of Scheduling. 2003. Vol. 6, pp. 533-549.

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

131. The two-dimensional bin packing problem with variable bin sizes and costs / D. Pisinger, M. Sigurd // Discrete Optimization. 2005. Vol. 2, pp. 154-167.

132. The two-dimensional finite bin packing problem. Part I: new lower bounds for the oriented case /М. Boschetti, A; Mingozzi // 40R. 2003. Vol. 1, pp.* 27-42.

133. Toyota Production System: Beyond Large-Scale Production / T. Ohno // Productivity Press, NY, USA. 1988. Pp. 58-67.

134. Trim-loss minimization in a crepe-rubber mill: Optimal solution versus heuristic in the 2(3)-dimensional case / W. Schneider // European Journal of Operational Research.-1998. Vol. 34, ppl 273-281';

135. Two-dimensional finite bin packing algorithms / J. О: Berkey, P: Y. Wang // Journal of the Operational Research Society. 1987. Voh 38, pp. 423-429:

136. Variable-sized bin packing: Tight absolute worst-case performance ratios for four approximation algorithms / C. Chu, R. La // SI AM Journal on Computing. 2001. Vol. 30, pp. 2069-2083

137. Zuschnitprobleme und ihre praktische Losung / J. Terno, R. Lindeman, G. Scheithauer//Leipzig, 1987. Pp. 17-25.