Порядке задачи раскроя фонда,

РЕЗЮМЕ

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

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

ВВЕДЕНИЕ

Задачи раскроя фонда (CSP) является одним из старейших и наиболее полно изученных проблем в области комбинаторной оптимизации. Большая часть интерес к этой проблеме связано с большим количеством производственных проблем которым относится CSP (Суини

1-мерный CSP является NP-полной задачи, которая возникает при стандартных размеров пунктов фонда должны быть физически разрезать на куски с разнообразием размеров в одном измерении (например, длину или ширину). Типичный подход предполагает решение пытается определить набор резки модели, которые будет производить необходимый набор элементов с минимальным количеством отходов. Это может быть смоделирована как целое линейного программирования (ЦЛП) задачи, в которой каждый столбец матрицы ограничений представляет собой конкретное резки картины. Значительное количество исследований было сосредоточено на решении одномерного CSP путем создания соответствующего набора кандидатов резки модели в контексте ILP (Гилмор

Из-за своей сложности, решения одномерных CSP часто создан с помощью таких методов, как ветвь, и по срокам (Валерио де Карвальо, 1998) и имитации отжига (Chen, Харт,

Независимо от того, общий подход к решению, что будет принят, то решение CSP, как правило, определить набор резки модели и количество просмотров каждой из этих моделей должны применяться. Для реализации этого решения на производственных площадей, образцы должны быть последовательность и запланировано. Это последовательность важна, по крайней мере три возможных причин: (1) нож / лезвие изменения настроек, необходимых для перехода с одной резкой картины на следующий (часто смягчается автоматизированного оборудования), (2) согласованность качества продукции для одному клиенту, что легче добиться, если такие изменения настроек можно избежать, и (3) частично хранения готовых продуктов и unready-for-packaging/assembly стеков (Hinterding

За последние два десятилетия, производственных организаций понимают, что значительные финансовые, оперативные, снабженческие и стратегические выгоды возникают от производства продукции на точно в срок (JIT) основе. В последнее время массовой кастомизации стала организация деловых принцип двадцать первого века. Массовой кастомизации представляет собой сочетание "массового производства" и "заказ". Это может быть определено как производство и поставка процесс, посредством которого серийных товаров и услуг для удовлетворения индивидуальных очень специфические потребности клиента при доступной цене. Потому что правильно реализации или JIT и массовых настройки требует значительного снижения уровня запасов и деятельности обработки материалов, классические CSP не может обеспечить соответствующую модель для оптимизации таких процессов.

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

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

ORDERED CSP

Приказал CSP может быть описан следующим образом. Производитель M рабочих мест, которые могут быть обработаны в любом порядке. Каждая работа у [элемент] (1,. . . , M) требует п ^ к югу J ^ частей сократится с фиксированной длиной части запасов материалов (например, лес, металл, ПВХ трубы, листовое стекло, и так далее). П ^ к югу J ^ частей, необходимых для каждого задания можно вырезать в любом порядке, однако, всех п ^ к югу J ^ части требования / должны быть срезаны до резки любых частей для следующей работы. Когда последняя часть для работы J режется, все оставшиеся длины заготовки используется для резки деталей для следующего задания, если остаток является надлежащей длины, в противном случае остаток отбрасывается в качестве лома. Производитель хотелось бы вырезать части для всех рабочих мест M при генерации наименьшее количество металлолома. Рисунок 1 дает пример приказал CSP, где каждая работа состоит из 5 частей (т. е. п ^ к югу J = 5 для всех /).

Эта проблема является вариантом 1-мерной резки проблемы складе, где мы определить количество и размещение прямых разрезов на каждой единице запасов. Ряд замечаний, касающихся этой проблемы в порядке. Во-первых, потому что Есть M! различных перестановок заказов рабочих мест и до тонны югу ф ^! перестановок частей в той или иной работы J, пространство решений задачи (т. е. число режущих модели), имеет размер M! [Pi] ^ SUP M ^ ^ к югу / = 1 ^ (п ^ к югу J ^! ) и быстро вырастает до огромных размеров, даже при малых значениях M и суб п ^ J ^. В результате, эвристический метод решения, необходимые для оптимизации задача такой сложности.

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

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

ПРИМЕНЕНИЕ

Приказал CSP была доведена до нашего сведения американская компания производитель деревянных окон и дверей. По данным последней переписи населения американской экономики в 1997 году древесных производителей окон и дверей производства и отгруженной продукции на сумму более 8,7 млрд. долл. США. Данный производитель частная компания с годовым объемом продаж в диапазоне от $ 1 миллиард.

Компания позволяет клиентам заказывать заказ окон в размерах от 12 до 84 дюймов в ширину и длину и в четверть дюйма шагом. Деревянные части ленты и рам для окон разрезаются до требуемой длины пользовательских от стандартной длины части сырья материалов. Эти части складе сырья закупается у поставщика, который устраняет недостатки в древесине и пальцев соединяет все воедино для создания бездефектных фонда для окна производителя. Компания управляет 10 производственными линиями, каждая из которых производит 50 окон часа, 8 часов в день, чтобы производить около 4000 окон в сутки. Ни один день производства все тот же.

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

РЕШЕНИЕ МЕТОДОЛОГИЯ

Как отмечалось ранее, решение пространства приказал задача CSP имеет размер M! [Pi] ^ SUP M ^ ^ к югу / = 1 ^ (п ^ к югу J ^!) И быстро становится слишком большим для перечисления, даже небольшие проблемы. В случае работы производства окне, если в час производства на 1 линии производит 50 окон и каждое окно требует 8 частей, а затем приказал связанных CSP бы 50! (8!) 50 [асимптотически =] 5.74E 294 возможных решений . Если упорядочение рабочих мест проводится постоянная и только заказ деталей в течение каждого рабочего места могут изменяться, до сих пор подавляющее (8!) 50 [асимптотически =] 1.89E 230 возможных решений. Учитывая сложность этой проблемы и для основе (перестановки) характер, генетические алгоритмы (ГА) является естественным методологии решения.

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

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

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

Генетические алгоритмы и ORDERED CSP

Для решения задачи оптимизации использования Г.А., мы должны прежде всего определить хромосом для представления возможных путей решения этой проблемы. В случае приказал CSP, хромосома может быть вектор длины M [Sigma] ^ SUP M ^ ^ к югу / = 1 ^ п ^ ^ J югу. Первые элементы M хромосомы содержат значения вектора д представляющих перестановки идентификаторы М работу. Остальные элементы хромосомы состоят из векторов M PJ, каждый из которых представляет перестановки югу п ^ J ^ часть идентификаторов связанных с работой j. Фитнес-функция затем развита подсчитать, сколько лом, связанные с каждым решением, как показано в (1) - (5).

Такого рода проблемы могут быть реализованы в таблицу и решить с коммерческим программным обеспечением А. пакет (Палисейд Corporation, 2001). Потому что хромосома состоит из M 1 различных подвектора каждая из которых представлена перестановки последовательных целых чисел, легко для пакета ГА для получения исходной популяции возможных решений, а также сохранить возможность в новых решений, которые создаются в процессе эволюции. Однако, поскольку хромосомы не записывает или отражать расположение части остатка запасов, типичный кроссовер и мутация предназначен для операторов, основанное на заказах (перестановки) хромосом не может использовать эту информацию в создании улучшение хромосом. В сущности, потому что кроссовера и мутации операторы не могут "видеть", где потенциально используемых кусков остаток осени они слепо (или случайно) порядок работы и запчасти в рамках рабочих мест таким образом, что часто пропускает очевидные улучшения решения. Чтобы преодолеть этот недостаток, мы разработали пользовательский эвристический этой проблемы называется PARTCUT, что улучшает или "ремонт" в ГА случайным решений, когда явные улучшения в части упорядочения возможны.

Эвристический PARTCUT ремонт проводится на каждом новом хромосом, выявленных этими программами Evolver (Палисейд Corporation, 2001) и начинается с помощью сканирования хромосомы, чтобы определить длину каждого элемента остаток (или лом), обозначим через R ^ к югу = L ^ ^ к югу - X ^ ^ к югу для штучных фонда К. Для каждой такой остаток, PARTCUT последовательно просматривает первую работу на складе части к 1 (т. е. задание д (J * ^ к югу ^ 1) на части длиной меньше или равна R ^ ^ к югу. (Заметим, что первая часть в настоящее время планируется сократить на складе части к 1, по определению, больше, чем R ^ ^ А к югу, в противном случае было бы сократить на складе К. шт) Если такая часть найдена, она переносится на первая позиция на складе части к 1, в которой, в сущности, движется части на последнее место на складе кусок А (потому что часть находится сейчас в состоянии быть вырезаны из остатков R ^ к югу ^). Диаграмма 2 иллюстрирует этот процесс. После перехода части, различные индексы обновляются, чтобы отразить эти изменения, и процесс повторяется, начиная со склада А кусок, пока все части К акции были оценены, и, где это возможно, восстановлены.

МЕТОДОЛОГИЯ

Рассмотрим теперь возможности и преимущества решения приказал CSP с использованием данных из окна производителя упоминал ранее. Данных состоит из фактического размера части для 400 окон производятся на одной производственной линии в течение обычного 8-часового рабочего дня (там, где линия производит 50 окон в час). Каждая из этих окон было арочные окна, который требует девять частей, которые варьируются в размерах от 15,563 до 42,125 дюйма, которые вырезались из фонда частей 16 футов в длину. На рисунке 3 показана диаграмма частот части размеров представлены в этих 400 окон.

Для вычислительных целей тестирования, мы случайно отобранных 40 комплектов 50 окон для представления 1 неделю (40 часов) производства по этой линии. Для каждого набора 50 окон, мы рассчитали общую из отходов при обработке заданий и частей в каждой работе на основе FIFO. Это по существу ту же процедуру в настоящее время используется в окно производителя, и будет служить один критерия для оценки решений приказал CSP. Жадные бен-упаковки (BP) эвристический могут также применяться легко к этой проблеме и входит в наши результаты вычислений для сравнительных целей. Эвристический BP процессов частей в каждое рабочее место в порядке длинная часть, которая может быть отрезано от остальной остаток запасов.

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

1. FIFO: Работа и деталей в течение каждого задания обрабатываются в порядке очередности.

2. BP: Работа обрабатываются в порядке FIFO и частей, в каждой работе, обрабатываются в том порядке, в длинной части, которая может быть отрезано от остальной остаток запасов.

3. Исправлена д: Работа обрабатываются в порядке FIFO и часть заказа в течение каждого рабочего места определяется генетический алгоритм.

4. Исправлена д PARTCUT: Работа обрабатываются в порядке FIFO, часть заказа в течение каждого рабочего места определяется генетический алгоритм, и эвристический PARTCUT ремонт работает.

5. Переменная д PARTCUT: Оба заказ на производство продукции и часть заказа в течение каждого задания определяется генетический алгоритм, и эвристический PARTCUT ремонт работает.

Модель приказал CSP был создан в Microsoft Excel. А. оптимизации этой модели проводились с помощью Evolver 4,0 Промышленные Edition (Палисейд, 2001). BP и PARTCUT эвристики были запрограммированы в Visual Basic для приложений (VBA) в Excel. Каждый оптимизации А. использоваться в Evolver, настройки по умолчанию и операторов с 2 минуты работы и использовать решения определены по методике, BP, как первоначальное решение А. в.

Результаты расчетов

Таблица 1 содержит краткую информацию от суммы из отходов в час с использованием каждого из методов решения. Использование существующего подхода планирования окно производителя (обозначается как FIFO), в среднем, 1120 дюйма лома генерируется каждый час в течение 40 часов производства рассматриваются. Используя простой эвристический BP, средняя лома сократился почти на 18% до 923,2 дюймов в час. Если производитель решил приказал CSP с фиксированным заказов работу (д), с использованием только присущие возможности Evolver, лома среднем сократится на 25,3% до 836,8 дюймов в час. Повышение Evolver способностей за счет включения в PARTCUT эвристический приводит к дальнейшему улучшению процент брака, уменьшив ее на 36% по сравнению с техникой FIFO и 22,4% по сравнению с техникой ВР. Хотя не ясно показано в таблице 1, использование эвристического PARTCUT всегда производил решение, которое, по крайней мере так хорошо, как получить решение без него.

Последняя колонка в таблице 1 приведены результаты, полученные, позволяя Evolver оптимизировать порядок заданий (д) в дополнение к приказу частей в каждом задании. Интересно, что возможности для оптимизации порядка работы не приводит к статистически достоверное улучшение по сравнению с предыдущим (с фиксированным PARTCUT д) результат. Это связано с тем, что, как правило, многочисленные альтернативные модели резки, которые генерируют такое же количество металлолома. В результате, когда д фиксируется, часто можно найти решение, которое так же хорошо, как найти лучшее решение, когда Q не является фиксированной. Действительно, в этом исследовании, позволяя ^ для изменяться в результате улучшения решения в 4 из 40 наборов тестовых задач и фактически привели в худшем решение для 3 тестовых наборов (в связи с эвристический характер генетических алгоритмов). Потому что часто Есть оперативные преимущества обработки заданий в установленном порядке (например, для синхронизации производства часть материалов по различным направлениям), этот производитель, вероятно, будет интересно узнать, что нет статистически значимых выгод в той или иной порядок работы.

Напомним, что в этом исследовании мы позволили Evolver баллотироваться на 2 минуты на каждого из наших 40 тестовых наборов и для каждого из методов приведены в таблице 1. В последней строке таблицы 1 показывает среднее время (в секундах) в течение этих двух минут окно, когда наилучшее решение было найдено каждого способа. Например, лучшее решение найти, используя метод фиксированных д произошло, в среднем 12,27 секунды на две минуты запустить. Добавление PARTCUT эвристический причин этого среднем к увеличению слегка 13,12 секунды, но это также приводит к улучшению решение не было найдено. Эти результаты позволяют предположить, что хорошего решения проблемы приказал CSP можно найти в очень разумных количествах времени с помощью GA-методик.

Таблица 2 суммирует результаты нашего тестирования с точки зрения среднего числа складе кусков в час путем различных методов решения. Здесь важно отметить, что решения получены с помощью эвристического PARTCUT позволяют производителем точно так же окно части этой линии с помощью производства около 2 меньше складе штук в час. Это составляет приблизительно 3% сокращение сырьевых материальных потребностей. Если этот производитель использует меньше 2 части запасов в час по каждой из 10 производственных линий операционной 8 часов в день, 5 дней в неделю, 52 недель в год, годовой экономии, связанной с такой подход становится весьма значительным (около 41 600 кусков на складе в год).

Дальнейшие испытания

Чтобы получить дальнейшее понимание о приказал CSP, мы случайным дополнительных проблем 360 испытаний и решить каждый из них с помощью методов, определенных пять назад. В данном тестировании мы варьировали количество деталей для каждой должности, круг части размеров и распределения части размеров. Факторный анализ был проведен с использованием экспериментальных уровней приведены в таблице 3. Для коэффициент, представляющий собой распределение части размеров, неоднородной уровни фактора являются главным (симметричных), правый перекос, и оставил перекос треугольной распределений. Во всех испытаний, GA-методик использовали решение ВР в качестве первоначального отправной точкой и было разрешено запускать раз в 2, 3 и 5 минут на работу с 8, 12 и 16 частей, соответственно.

Первоначально 10 репликаций, полученные по каждому обращению в 1 фут в 7 футов спектр факторов размер части. В Таблице 4 приведены результаты тестирования по этим проблемам. В ходе такого испытания техники FIFO включает в себя обработку части для каждого задания в чисто случайном порядке. В результате, это не удивительно, что другие методы, результаты, которые значительно лучше, чем FIFO. Что может быть удивительного в том, что, по существу, нет разницы между производительность техники BP и GA-методик. Вероятной причиной такого результата является то, что, когда части размеров для любой работы охватывают широкий диапазон (например, 1 фут до 7 футов) относительно легко найти части, которые помещаются на складе остатки шт. В результате, эвристический BP очень хорошо работает на такого рода проблемы, и GA-методик, основанных не в состоянии обеспечить столь дальнейшего совершенствования.

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

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

В таблице 5, мы еще раз заметить, что все эвристики выполнить значительно лучше, чем FIFO-в результате сокращения на 50% до 60% в среднем количество металлолома производится. Сравнение производительности от BP эвристический на GA-методик, мы снова находим, что д фиксированной техники дает результаты идентичны ВР. Тем не менее, GA-методик, которые включают PARTCUT эвристический теперь приводит к результатам, статистически значимо различных (но лишь незначительно лучше), чем в среднем эвристический ВР. Отметим также, что среднее количество лома, порожденная всеми эвристические методы больше в таблице 5, чем в таблице 4. Это может быть связано с тем, что минимальный размер участие в таблице 5 (т. е. 2 фута) больше, чем представлено в таблице 4 (т. е. 1 фут), которая в свою очередь, снижает вероятность того, чтобы найти части, которые помещаются на имеющихся остатков часть запасов.

Таблица 6 обобщаются результаты тестирования по части проблем с размерами в диапазоне от 3 футов до 5 футов (опять-таки создан масштабирование тестовых задач с табл. 4). И вновь мы наблюдаем, что все эвристики выполнить значительно лучше, чем FIFO-в результате сокращения на 38% до 48% в среднем количество металлолома производится. Сравнение производительности от BP эвристический на GA-методик, мы снова находим, что д фиксированной техники дает результаты практически идентичны ВР. Тем не менее, GA-методик, которые включают PARTCUT ремонт эвристического приводит к результатам, статистически значительно отличаются (и значительно лучше), чем в среднем эвристический ВР.

ОБСУЖДЕНИЕ

Ряд замечаний вытекают из наших вычислительных тестирования. Во-первых, интересно отметить, что результаты расчетов, приведенные в таблице 1 на основе данных фактических окна производства включены части, размеры которых варьировались от 15,563 дюймов до 42,125 дюйма (или диапазона около 2 метров). Тем не менее, результаты в таблице 1 показано GA-методик, основанных выставке большое преимущество над BP эвристический, чем отражено в таблице 6 (по части размеров различной за такой же спектр 2 фута). Это, вероятно, связано с тем, что реальные данные стремится проявлять больше структуру, чем случайно сгенерированных данных. Например, симметричные длине и ширине размеры, обычно встречающиеся в Windows требует соответствия части размеров для вертикальной и горизонтальной части деталей. Это уменьшает количество отдельных части размеров, связанный с любым работу, которая, в свою очередь, делает его более трудно найти детали, которые будут соответствовать имеющихся остатков часть запасов. В таком случае, GA-методик поиска, вероятно, будет более эффективным, чем простой эвристический жадный, такие как метод ВР.

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

В таблицах 4, 5 и 6, фиксированной д техники следует также (в теории) быть в состоянии найти какой-либо из лучших решений, найденных методов, которые используют PARTCUT эвристики. Как уже упоминалось ранее, потому что кроссовер Evolver и мутации операторы не могут "видеть", где возможно использовать кусочки остатки упадут, они слепо (или случайно) порядок частей в работу таким образом, что часто упускают из очевидного улучшения решения определенных PARTCUT эвристики. Несообщаемого экспериментов изменения по умолчанию кроссовер Evolver и мутаций по фиксированной д техники не улучшить производительность Evoiver здесь. Мы не рассматриваем это как недостаток, но Evolver наглядный урок для аналитиков в стоимости выявления и использования индивидуальных эвристики ремонт в течение газ (что Evolver вмещает красиво).

Наконец, интересно отметить, что во всех наших вычислительных тестирования переменной д PARTCUT техника никогда не выступала статистически достоверно лучше, чем фиксированной техники PARTCUT д. Хотя переменной д PARTCUT методика должна (в теории) позволяют определить решения, которые, по крайней мере так хорошо, как те нашли с фиксированной д PARTCUT техники, напомним, что решение пространства, ассоциированного с переменной д техники PARTCUT больше, чем Исправлена д техники PARTCUT на коэффициент M! В результате, это может занять переменной д PARTCUT техники значительно больше времени, чтобы найти сопоставимый или усовершенствованных решений. В экспериментах с использованием незарегистрированных наборов данных из таблицы 6, мы позволили переменной д PARTCUT метод для запуска 4 раза больше, чем фиксированной д PARTCUT техники и наблюдали номера металлолом за два методы начинают сходиться, как ожидалось. Однако, как отмечалось ранее, хотя различные порядок работы может привести к улучшению решения (при достаточно во время выполнения), мы подозреваем, что большинство производителей будут заинтересованы в сохранении для обработки заданий постоянной для облегчения синхронизации часть материалов по множественного рождения линии (или просто сохранить все рабочие места, что вместе составляют в определенном порядке на одной производственной линии).

ВЫВОДЫ

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

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

Использование Evolver и Microsoft Excel, он взял очень мало времени для создания решений, отвечающих стоит целой недели производства для компании по производству пример. Мы смогли продемонстрировать существенные улучшения по сравнению с существующими подход FIFO принятые в компании, с точки зрения как количества отходов производства и количества штук складе использованного материала. Расширенное тестирование показали, что эти сокращения отходов уровни могут быть достигнуты последовательно через самые разные формулировки проблемы. Такие сокращения могут обеспечить значительные оперативные и конкурентные преимущества путем ведет к уменьшению хранения, обработки и стоимости сырья. [В редакцию: декабрь 2002. Принято редколлегией: Август 2003.]

Ссылки

Бергей, П. К.,

Breedam, А. В. (2000). Сравнение происхождения эвристик и metaheuristics для маршрутизации автотранспорта проблемы. Компьютеры и исследование операций, 28 (4), 289-315.

Chen, C., Харт, S.,

Dyckhoff, H. (1981). Новый линейного программирования подход к режущим задача фонда. Исследование операций, 29 (6), 1092-1104.

Dyckhoff, H. (1990). Типология резки и упаковки проблем. Европейский журнал по исследованию операций, 1 (44), 145-159.

Falkenauer Е.,

Ферстер, H.,

Гилмор, П. C.,

Hinterding Р.,

Голландия, J. H. (1992). Генетические алгоритмы. Scientific American, 267 (1), 66-72.

Лян, К., яо, X., Ньютон, C.,

Палисейд Corporation. (2001). Evolver 4,0 (<a target="_blank" href="http://www.palisade.com" rel="nofollow"> http://www.palisade.com </ A>). Ньюфилд, NY: Корпорация Палисейд

Ривз, К. Р. (1997). Генетические алгоритмы для исследователя операций. Сообщает журнал по вычислительной, 9 (3), 231-265.

Рено, J., Boctor, F.,

Сантос, А.,

Scheithauer Г. Терно, J.,

Shiromaru И., Inuiguchi, М.,

Суини, П. Е.,

Валерио де Карвальо, J. M. (1998). Точное решение одномерной резки материала по проблемам поколения столбца и ветвей и границ. Международные сделки в области оперативного анализа, 5 (1), 35-44.

Валерио де Карвальо, J. M. (2002). Л. моделей для упаковки в контейнеры и резки складе проблем. Европейский журнал исследования операций, 141 (1), 253-273.

Ван Буэр, М., Вудрафф, Д.,

Вагнер, Б. J. (1999). Генетического алгоритма решения для одномерных комплекте складе резки. Европейский журнал исследования операций, 117 (2), 368-381.

Клифф Т. Рагсдейл [кинжал]

Департамент предпринимательства информационные технологии, Памплин бизнес-колледжа, штат Вирджиния политехнического института и государственного университета Блэксбург, В. А. 24061, адрес электронной почты: <a href="mailto:crags@vt.edu"> crags@vt.edu </ A>

Christopher W. Цобель

[Кинжал] корреспондент автора.

Клифф Т. Рагсдейл является "Бэнк оф Америка профессор делового информационных технологий в Технологическом университете Вирджинии. Он получил докторскую степень в области науки управления и информационных технологий из Университета штата Джорджия. Он также имеет степень магистра делового администрирования в области финансов и степень бакалавра в области психологии из Университета Центральной Флориды. Его главным направлением научно-исследовательский центр интересов по вопросам интеграции компьютеров, математики и искусственного интеллекта для решения бизнес-проблем. Он является членом Института Decision Sciences, Ассоциации по информационным системам и Институтом исследования операций и наук управления. Он опубликовал в различных журналах, в том числе Decision Sciences, систем поддержки принятия решений, Naval Research Логистика и OMEGA. Он также является автором учебника таблицы Моделирование и Decision Analysis (Юго-Западный, 2004).

Christopher W. Цобель, доцент Бизнес информационных технологий в Технологическом университете Вирджинии. Он получил докторскую степень в области инженерных систем из Университета Вирджинии, магистра математики в Университете Северной Каролины в Чапел-Хилл, и степень бакалавра по математике в Colgate University. Его основные исследовательские интересы лежат в области интеллектуальных систем поддержки принятия решений, знание техники, крупномасштабные стохастические решения проблем, эвристические решения проблем, и компьютерные симуляции. Он опубликовал статьи в решении наук, Международный журнал научных исследований, производство, компьютеры и операционные исследования Компьютеры и организации промышленного производства, а также IEEE Transactions по системам, человеку и кибернетики, среди других. Он является членом Ассоциации по информационным системам, Институт исследования операций и наук управления, Институт Decision Sciences.

НАУКА - статьи, новости, рефераты, переводы

Порядке задачи раскроя фонда,