Скоординированная Capacitated Лот-Калибровка Проблема с Спрос Динамическая: лагранжевых Эвристический

РЕЗЮМЕ

Скоординированная пополнения проблемы являются общими в производстве и распределении, когда семья из пунктов имеет общую производственную линию, поставщик, или видом транспорта. В таких ситуациях координации общих, зачастую весьма ограниченных, ресурсов по пунктам является экономически привлекательным. Эта статья описывает частично целочисленного программирования и разработки лагранжевых процедуры релаксации для решения одной семьи скоординированных capacitated много-калибровки проблемы с динамическими спроса. Проблема распространяется как мульти-пункт capacitated динамичный рост спроса-много размеров проблемы и uncapacitated скоординированных динамичный рост спроса-много размеров проблемы. Мы предоставляем результаты вычислительных экспериментов по исследованию математических свойств при разработке и исполнении лагранжиана процедур. Полученные результаты свидетельствуют о превосходстве двойного основе эвристического над линейного программирования, подходы к этой проблеме. Качество эвристического решения лагранжевых улучшились в большинстве случаев с увеличением размера задачи. Эвристические решения усредненной 2,52% выше оптимальной. Процедуры были применены к проблеме отрасли тест приносят 22,5% сокращение общего объема расходов.

Предметные области: управление запасами, Лот-Калибровка и математического программирования / Оптимизация.

ВВЕДЕНИЕ

пополнение политики фирмы является основной движущей силой своей оперативной инвестиций и затрат, а способность выполнять свои задачи обслуживания клиентов. Из-за их практическое значение, пополнения много-калибровки проблемы относятся к числу наиболее широко исследуемых областей операций и управления цепочками поставок. Тем не менее, из-за их сложности вычислений, несколько важных классов проблемы остаются нерешенными. Это исследований скоординированной capacitated много размера задачи (CCLSP) с динамическим спроса. Проблема определяет, для одного семейства продуктов, повременных пополнения графика, которая минимизирует пополнения запасов и расходов по backlogging спроса и ограниченной пропускной способностью. Основная часть затрат, понесенных установки каждый раз один или несколько пунктов в семейство продуктов пополняются, и незначительные затраты установки взимается за каждый пункт пополняется. Пункт спрос детерминированных и над горизонтом планирования T-период.

Серебряный (1979) приводит несколько контекстов, в которых скоординированных пополнения важно, например, когда семья пунктов общий поставщик, общий вид транспорта или объекта общего производства. В таких ситуациях, координации общих, зачастую весьма ограниченных, ресурсов по пунктам является экономически привлекательным. Шапиро, Розенфельд и Stecke (2002) изучить возможности ассигнований в связи с производства как основной (семейство продуктов) установок и незначительные (в пределах семьи) установок. Хотя некоторые исследователи обеспечить алгоритмы uncapacitated версия этой проблемы, capacitated проблема не получает надлежащего внимания в литературе.

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

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

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

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

Обзор литературы

Четыре класса задача заложить основу для исследования CCLSP: uncapacitated проблема много размера (ULSP), одного пункта capacitated проблема много размера (Стратегия), многочисленные повестки дня capacitated проблема много размера (MCLSP), а также скоординированных uncapacitated проблема много размера (CULSP). Из-за большого числа публикаций в этой области, полный обзор этой литературы не практично здесь. Вместо этого мы сосредоточимся на окончательные работы и обновление обзоров литературы Бала, Рицман и Gupta (1987) для ULSP, Стратегией и MCLSP и Аксой и Erenguc (1988) для CULSP. Дрексл и Kimms (1997) обеспечивает широкий обзор много определения размеров и сроков литературы.

ULSP оптимизирует пополнения графики для одного элемента, полагая, дискретных динамических спроса и неограниченные поставки продукта в каждом периода пополнения. Система включает затраты на единицу товарно-материальных запасов и затрат постоянных и переменных затрат пополнения. Вагнер и Уайтин (1958) представить динамического программирования алгоритм O (T ^ SUP 2 ^), где Т количество периодов времени, в горизонте планирования. Зангвилл (1966) расширяет модель для разрешения спроса backlogging. Эванс (1985), Federgruen и Цур (1991), Wagelmans, Ван Hoesel и Kolen (1992), и Aggarwal и парк (1993) описывают эффективных процедур осуществления решения ULSP.

Добавление возможности ограничения, основанные на рабочую силу, оборудование, складские помещения и другие ограничивающие факторы расширяет модель рассмотреть вопрос о более практических ситуациях. Флориан, Ленстра и Rinnooy Кан (1980) и Bitran и Yanasse (1982) показывают, что вычислительная сложность Стратегией является NP-жесткий или NP-полна для общей цели функции и предположений относительно изменчивости спроса и возможностей. Таким образом, исследования были направлены на процедуры для разрешения особых случаях Стратегией. В эти исследования потоке Флориан и Клейна (1971), Любовь (1973), Бейкер, Диксон, журнал, и серебро (1978), Ламберт и Ласс (1982), Чжун и Линь (1988), Erenguc и Аксу (1990) , Кырджа (1990), Лотфи и Юн (1994), Чжун, Флинн, и Лин (1994), а Шоу и Wagelmans (1998). Hoesel и Wagelmans (2001) изучить полностью полиномиальной аппроксимации схемы, которые производят решений с относительное отклонение от оптимальности. Хинди (1995a), Sox и Гао (1999), и Гопалакришнан, Динг, Bourjolly и Мохан (2001) обобщить проблемы рассмотреть установки переходящий в соседние периоды времени.

В многочисленных пункта capacitated проблема много размеров, MCLSP, соревнуясь пунктов долю ограниченных ресурсов. Манн (1958) дает приближенное линейного программирования (ЛП) разработку, в которой решение переменных представляют собой возможные последовательности пополнения. Dzielinski и Гомори (1965) и Lasdon и Terjung (1968) уточнить подход Manne, в то время Bitran и Мацуо (1986) обеспечивают погрешность оценки и показать, что граница качества хорошо, когда количество элементов больших по сравнению с числом периодов . Kleindorfer и Ньюсон (1975) применить лагранжевой релаксации ограниченные возможности MCLSP и показать, что решения двойного релаксированных задача эквивалентна решению разработке Manne в.

Другие математические методы программирования для задачи: Биллингтон, Макклейн и Томаса (1983) частично целочисленного программирования (ПМС) формулировку с ограниченной пропускной способностью материала требование планирования (MRP) системы, (1985b) Эванса фиксированного заряда одной товаропроводящей сети модель течения и ветвей и границ (B

В связи с вычислительной трудности для нахождения оптимальных решений, многочисленные эвристические подходы, предлагаемые для MCLSP. Мэйс и ван Wassenhove (1988) дается обзор нескольких эвристик, а также их эффективности. Ньюсон (1975a, 1975b), Ван Nunen и Wessels (1978), и Карни-н-ролла (1982) подойти к решению проблемы, первоначально игнорируя ограничения пропускной способности и создания производственных графиков. Далее, производственные планы корректируются для достижения экономической целесообразности. Eisenhut (1975), Ламбрчт и Vanderveken (1979), Диксон и серебро (1981), и Дограмаджи, Panayiotopoulos, и Адам (1981) предложить жадные эвристики строительства. Pratsini (2000) развивает чистая экономия эвристика для MCLSP со временем установки и обучения.

Гилберт и Мадан (1991) обеспечивает эвристический на основе решения проблемы фиксированного заряда транспорта. Лосано, Larraneta и Onieva (1991) предложить primaldual эвристики. Кырджа и Kokten (1994) использовать итеративный пункта по-пункта для создания стратегии решения задач. Хинди (1996) использует поиск Табу совершенствовать решения жесткой релаксации ЛП проблемы. Ozdamar и Bozyel (2000) применить алгоритм имитации отжига считая сверхурочных и возможности установки времени.

Следующие подходы лагранжевой релаксации тесно связаны с данного исследования. Тизи и Ван Wassenhove (1985), Trigeiro (1987), Trigeiro, Фома и Макклейн (1989), и Диаби, Баль, Karwan и Zionts (1992a) ослабить ограничения пропускной способности и решить одного пункта ULSP подзадач. Решение любой проблемы транспортировки или смены эвристический потенциал восстановления экономической целесообразности. Предполагая, сверхурочные затраты для установки и настройки времени, Диаби, Баль, Karwan и Zionts (1992b) сравнить релаксации потенциала в сравнении с ограничениями спроса выяснилось, что лучшее исполнение связана с расслабляющими ограниченной пропускной способностью. Кэмпбелл и Mabert (1991) продлить этот подход к рассмотрению MCLSPs с циклический график. Ким, Mabert и Пинто (1993) исследования циклических расписаний с последовательностью зависимых расходов установки. В одной из немногих моделей, которая рассматривает backlogging спроса, Миллар и Ян (1994) описывают лагранжевой релаксации переменной верхняя ограничений. Миллар и Янг (1993) представляют лагранжевы техника разложения, что приводит к вспомогательной транспорта и N независимых ULSPs.

Согласно стандартным, скоординированных много размеров проблемы предположить семьи пунктов акций общей стоимостью установки. Аркин, Joneja и Раунди (1989) и Joneja (1990) показывают, что скоординированные uncapacitated много размеров проблема WP-полной. Традиционные подходы к решению CULSP разработки динамических алгоритмов программирования (см. Зангвилл, 1966б; Veinott, 1969; Као, 1979, и серебро, 1979), в котором время вычислений растет экспоненциально с проблемой размера. Haseborg (1982) исследует оптимальности совместного заказа политики по смягчению неблагоприятного воздействия большого количества элементов.

Erenguc (1988) предлагает комбинированные B

Erenguc и Мерджан (1990) являются единственным вычислительных исследование скоординированной, capacitated много-калибровки проблемами мы столкнулись в литературе. Они считают, нескольких семейств продуктов, которые разделяют с ограниченными ресурсами. Семья время установки производятся каждый раз, когда семейство продуктов производится. Кроме того, время установки и запуска единицу времени применяются для каждого единицу выпускаемой продукции. Установка расходы не входят в целевую функцию, так как затраты на рабочую силу, как предполагается, будут невозвратные издержки. Backorders не допускается. Они используют специализированные B

Ряд исследователей изучить структуру многогранных альтернативные формулировки MIP динамического много-калибровки проблемы в попытке обнаружить жесткий линейных релаксаций программирования. Барани, Van Roy, а Вулси (1984a), представляет описание выпуклая оболочка ULSP набором линейных неравенств. Они также обеспечивают эквивалентную простой формулировке расположение растений и характеризуют его выпуклой оболочки. Барани, Van Roy, а Вулси (1984b) обеспечивают сильные формулировки MCLSP. Leung, Magnanti и Vachani (1989) изучить структуру многогранных Стратегией и использование их результатов для разработки действительный неравенства, которые определяют аспекты основных многогранника целочисленного программирования. Мартин (1987) и Eppen и Мартин (1987) ввести понятия переменной пересмотра в качестве метода для разработки более жестких формулировках MIP capacitated много-калибровки проблем. Эти уточненные формулировки более эффективно решать общие цели MIP программного обеспечения по сравнению с традиционными формулировок и послужить основой для разработки специализированных алгоритмов. Тизи (1991) оценивает пять различных лагранжевых разложения MCLSP с многогранного анализа прогнозировать их значения и вычислительной сложности.

Denizel, Erenguc и Шерали (1996) развивать выпуклых underestimators для некоторых интерактивных вогнутой фиксированного заряда задач минимизации и покажем, что выпуклая оболочка релаксации приводит к релаксации Л. сильного IP / MIP формулировки этих проблем. Они применяют свои результаты 4 классов, включая проблемы общей постановке нескольких CCLSP семьи, которая учитывает как стоимость установки и настройки времени. Они не предлагают алгоритмического подхода для ее решения.

Таким образом, в литературе имеются самые разнообразные эвристические и точное решение подходит для MCLSP и CULSP. Тем не менее, очень мало усилий, направленных на более общие и часто встречающихся CCLSP. Таким образом, исследования изучение альтернативных формулировок и математических свойств CCLSP и развития эвристических процедур является оправданным. Работы, наиболее тесно связанных с нашим является Erenguc и Мерджан (1990). Однако, проблема изучается в данном исследовании, его математическая формулировка и алгоритмические подходы различны. Мы предполагаем, одного семейства продуктов, создание потребляется семьи установок и пункт время работы, и backorders допускается. Кроме того, мы предлагаем общие структуры расходов, которые рассматривают основные расходы установки для координации деятельности, незначительные затраты установки для отдельных типов элементов, а также backlogging расходов. Хотя это может быть продлена Erenguc и алгоритмический подход Мерджан "переносить backorders и наши более общие структуры затрат, эти дополнительные функции задача уничтожить многие благоприятные математических свойств эксплуатации со стороны их B

ПОСТАНОВКА ЗАДАЧИ

политики минимальной стоимости пополнения должны быть определены в течение периода планирования T горизонты для одной семьи пунктов K. Спрос D ^ ^ к югу кт для каждого элемента А = 1, 2,. . . , K во времени периодом Т = 1, 2,. . . , T является детерминированным, меняется со временем, и должны быть удовлетворены за счет текущего производства или инвентаризации или backlogging. Пополнение много расщепления является допустимым.

Мы ориентируемся на структуру расходов, обычно наблюдается в промышленности и изучены в более ранних исследований. Пополнение в семействе продуктов во времени я требует больших расходов установки, S ^ югу я ^ я = 1, 2,. . . , Т. несовершеннолетнего стоимость установки S ^ ^ ик югу произведены для включения пункта А в семье пополнение в период I. Стоимость за единицу пополнения пункта А в это время я с ^ ^ ик к югу. Для этого, ч ^ ^ к югу ИКТ является стоимость за единицу backlogging связанных с обслуживанием спрос пункта А в период т с пополнением от времени I. Всего на единицу стоимости на поставку спрос на пункт А за время Т от пополнения в период я это C ^ югу ИКТ ^ = с ^ к югу ик ^ H ^ ^ к югу ИКТ.

Общее количество пополнения, возникающие в период времени я подлежат одного ограничение ресурсов мощностью P югу ^ ^ я. Возможные ограничения включают время производства, размер процесса бак, масса / куб, или других ограничивающих факторов. Основные установки для пополнения семейства продуктов времени я потребляет е ^ ^ к югу я единицы мощности в результате чего чистый потенциал P югу ^ я ^ - е ^ ^ я к югу. За потребление единицы ресурса пункта А в период времени я это Ь к югу ик ^. Решение переменной Z ^ ^ я к югу равна 1, если семья пополняется времени я, и 0 в противном случае. Y ^ ^ ик югу представляет пополнение пункта А в период я, где Y ^ ^ к югу ик = 1, если к включен, и 0 в противном случае. X ^ ^ к югу ИКТ, является непрерывной переменной решение, связанное с долей спроса пункта А в период времени т, что подается с пополнением времени I.

Лагранжевой ПРОЦЕДУРЫ релаксации ПРОБЛЕМА P

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

Проблема LR ([лямбда], [му]) экспонатов целостность имущества, определенного в Geoffrion (1974). То есть, оптимальным решением задачи LR ([лямбда], [му]) с целочисленности ограничения в ограничениях (6) и (7) расслабленной гарантируется доходность целочисленных значений для Z ^ югу я ^ и Y ^ ^ к югу ик . Таким образом, наилучшим связанных предоставляемый Z ^ югу LR ^ ([лямбда], [му])

Из главных проблем в получении точной оценки с лагранжевой релаксации в том, как определить значения [лямбда] ^ ^ кт к югу и [му] ^ ^ я к югу, которые обеспечивают плотные нижняя граница Проблема П. Это, решая проблемы LR, лагранжевой двойственной задачи.

Проблема LR

Z ^ югу LR = тах к югу [лямбда], [му] ^ (Z ^ югу LR ^ ([лямбда], [му])),

где [му] ^ югу я ^> или = 0 для всех я и [лямбда] ^ ^ кт югу неограниченный для всех К и Т.

На практике, хорошо, но не всегда оптимальны, мультипликатор набор можно найти, используя субградиентного оптимизации. Краткое обсуждение в общем порядке и разработок частности, нашей заявки представлены в данном разделе, а более подробные сведения приведены в приложении. LR Процедура начинается с [му] югу ^ я = 0 для всех я и [лямбда] ^ ^ кт югу равно второй наименьшее значение C югу ^ ^ ИКТ для всех К и т. На основании этих значений множителя, решение задачи LR ([лямбда], [му]) предусматривает, что нижняя граница может быть невозможным для задачи P в связи с нарушением ограничений (2) и (3). Технико-экономическое Процедура изменяет лагранжевых снизу решение восстановить возможность в случае необходимости. Далее, новый множитель значения создаются в соответствии со стандартными конвенций субградиентного оптимизации в попытке устранить любые нарушения ограничений в следующей итерации. Процедура итерации, обновление значения множителя до дальнейшего улучшения маловероятно. См. проведены Вулф и Краудер (1974) и Фишера (1981) для вычислительной производительности и теоретические свойства этой субградиентный метод.

Еще одним усовершенствованием устраняет избыточные решения в B

Перед окончательным закреплением установки переменной закрыты, B

Численное исследование

Мы провели расчетные исследования для оценки математических свойств постановки задачи, качество нижняя граница предоставляемый релаксации Л.П., а также эффективность оптимизации Подпрограмма IBM Библиотеку (OSL) и лагранжиан основе процедур, чтобы найти хорошие эвристические и оптимальные решения в CCLSP. OSL является коммерчески доступных частично целочисленного программирования, использующий LP-основанные B

Описание тестовых задач

Проблема размеры колеблются от 36 до 492 целое решение переменные, как определяется число элементов K [эпсилон] (2, 4, 6, 10, 20, 30, 40), а длина горизонт планирования, который установлен на уровне 12 периодов времени для всех тестовых задач.

Основные расходы установки S ^ ^ я к югу, взяты из набора (190, 310, 360, 620, 1120, 1520 и 1920), масштабирование с большим числом элементов. Erenguc (1988) показывает, что в число продуктов увеличение общей стоимости решения проблемы становится менее крупные-установки стоимостью доминирующей и относительно легко решить. Таким образом, расширение основных расходов установки позволяет сделать более точную оценку выполнения алгоритма с увеличением K. Предварительные вычислительные эксперименты показали, что незначительные стоимость установки потенциально могут воздействие качеству решения и вычислительные потребности. Следовательно, мы включили в незначительных расходов установки в качестве экспериментального фактора. Мы ставим незначительные затраты установки с ^ ^ к югу ик на двух уровнях, $ 100 или $ 300. На $ 300, незначительные затраты установки стала важной движущей затрат и зачастую перевешивают стоимость основных установки в определении пополнения графики.

Для каждого сочетания параметров задачи, мы создали 10 случаях проблема случайно генерации различных моделей спроса. Для каждого г ^ ^ к югу тыс. т, данные случайно обращается с равномерным распределением (50 150). Любое требование значение меньше или равно 60 единиц устанавливается равным нулю. Таким образом, для каждого элемента, 90%, спрос сроки больше нуля. Для всех я, К, Т, Н ^ к югу ИКТ = $ 1 (т - я) при *> или = я и Л ^ к югу ИКТ = $ 3 (я - т) для т

Математические свойства задачи

Математические свойства задачи P и возможность найти хорошую эвристического и оптимальные решения с общего назначения, частично целочисленного программирования оценивали по OSL математического программирования IBM, программное обеспечение. Математические свойства изучены включать качества нижняя граница предоставляемый релаксации ЛП и часть решения ЛП, которые являются оптимальными для задачи П. Экспериментальные результаты приведены в таблицах 1, 2 и 3, в соответствии с уровнем использования потенциала. Каждая запись в таблице дает средние показатели для 10 случаев проблема.

Качество отдыха Л. указывается процент отклонения от нижней границы (LB) от оптимальности, которая определяется как LB / Опт. Разрыв в таблицах. Как и ожидалось, в связи с тенденцией к единственному требованию источника (например, X ^ югу ИКТ = 0 или 1) на низкой загрузки мощностей и использовать много расщепления (т.е. дробных X ^ ^ к югу ИКТ) при высоких уровнях использования, Л. П. релаксации сжатые для относительно проблемы низкого использования производственных мощностей. Средний LB / Опт. Разрыв 0,04%, 1,27% и 9,9% для 5%, 45% и 85% уровня использования производственных мощностей, соответственно. OSL не смог получить оптимальные решения задачи для всех проблемных случаях на 45% и 85% уровня использования производственных мощностей. Таким образом, результаты представляют лишь проблема случаях, для которых оптимальным решением было получено. Существует причина полагать, что разница может быть еще хуже, чем было указано на проблемы, которые OSL не удалось решить в оптимальности. Тем не менее, результаты явно указывают на ухудшение качества релаксации Л.П. по мере увеличения загрузки производственных мощностей. Кроме того, на 5% и 45% проблемы использования производственных мощностей, LB / Опт. Пробелы стали тесными для $ 100 несовершеннолетних стоимость установки по сравнению с $ 300 незначительных проблем, стоимость установки. Получены аналогичные результаты для небольших 85% проблемы использования, но не являются окончательными для больших размеров с проблемой оптимального решения не могут быть найдены во всех случаях ..

Процент оптимальных решений проблемы найдено релаксации Л. на корневой узел (узел 0) из B

LP-основе эвристических и B

Линейное программирование и оптимальное решение раза увеличилось с проблемой размера. Кроме того, $ 300 незначительных проблем, стоимость установки последовательно требуется больше ресурсов процессора, чем $ 100 незначительных проблем, стоимость установки. Хотя OSL смог найти оптимальные решения для всех 140 от 5% проблемы использования производственных мощностей, он может проверить оптимальные решения только для 135 из 140 случаев проблемы на уровне 45% использования и 47 140 случаев проблемы при 85% мощности использования уровне.

OSL предусматривает эвристических решений путем округления до целого дробных значений переменных в решении LP. Хотя это не является сложной процедурой, она обеспечивает создание возможности верхняя решения, которые, в сочетании с объективным значением функции релаксации Л.П., обеспечить наихудший оценка эвристического решения. LB / Гэп УБ и UB / Опт. Разрыв в таблицы позволяет оценить эффективность эвристического OSL. В целом, эффективность эвристического OSL разочаровывает, особенно проблемы множеств с $ 300 несовершеннолетних стоимость установки. Эти результаты являются веским обоснованием для разработки более эффективных эвристических подходов.

Вычислительная производительность лагранжиана релаксационных процедур

Результаты расчетов для лагранжиана процедуры релаксации приведены в таблицах 4, 5 и 6. В целом, производительность лагранжиана процедур для нахождения оптимальных решений не столь эффективно, как OSL. Тем не менее, процедуры проверить оптимального решения для всех 5% мощностей задач и 68 из 140 случаев проблемы на 45% уровень использования. Ни один из 85% производственных мощностей проблемы были решены к оптимальности. Как и в случае с LP-основанные B

Превосходство OSL в поиске оптимальных решений, связанных с ужесточением LB Решение, предлагаемое релаксации LP. Лагранжиан (OSL) LB / Опт. Пробелы для тестовых задач 0,07% (0,04%), 2,8% (1,27%) и 14,21% (9,9%), соответственно, на 5%, 45% и 85% проблемы использования производственных мощностей. Как и ожидалось, LB предоставляемый лагранжевых процедуры не столь жесткой, как релаксация Л. из-за целостность имущества в разработке, и общая трудность нахождения оптимального значения множителя. Тем не менее, МО разумно жесткой для 5% и 45% его вместимости проблемы использования уровне.

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

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

Наконец, несколько точек остановки возможны LR эвристики. В вычислительных экспериментов, мы предоставляем результаты на узле 0 в B

Сравнение эффективности ЛР и LP-основанные эвристик в таблицах 1-6 показывает средний процент LB / UB пробелов в LR (OSL) эвристический являются 0,49 (3,6), 6,4 (18,48), а 14,51 (19,2) для 5%, 45% и 85% проблемы использования производственных мощностей, соответственно. Соответствующие UB / Опт. пробелы 0,44 (4,68), 3,91 (23,36), и 4,72 (15,61). Эти результаты иллюстрируют преимущества лагранжева подхода и поддержки сделанные ранее выводы о том, что проблема сложность возрастает с более высоким уровнем использования производственных мощностей. Рассмотрение таблицы показывает также, что большую UB / Опт. пробелы, связанные с более высоким уровнем незначительные затраты установки.

Цифры 1 и 2 наглядно сравнить производительность LR и OSL эвристические подходы для 45% своих возможностей уровнем использования ресурсов и $ 100 и $ 300 незначительные затраты установки. Аналогичные результаты справедливы для 5% и 85% проблемы использования производственных мощностей. LB / Опт. пробелы как эвристики уменьшается количество элементов возрастает. Манн (1958) получили аналогичные результаты для нескольких пункта capacitated проблемы много размеров, где он отметил, что количество элементов увеличивается, целевая функция частично целочисленного подходов к программированию, что проблема релаксации LP. Эти результаты подтверждают целесообразность LP-низкое качество ограничивающей подходы к разработке проблемы CCLSP, особенно для крупных проблем. Таким образом, выбор расслабленной ограничений в предлагаемом LR является оправданным.

Повышение эффективности LR над эвристический OSL свидетельствует сопоставление LB / УБ и UB / Опт. пробелов в данных и таблиц. Во всех случаях качество LB / пробелы UB для LR эвристический улучшилось количество элементов увеличилось. OSL свидетельствует о неустойчивой работы. Эвристический LR также стремится обеспечить жесткий UB / Опт. пробелов, а количество элементов возрастает. Эти результаты являются перспективными с эвристические подходы, более вероятно, должны применяться в этих крупных проблем условиях.

Тестовое приложение лагранжиана ПРОЦЕДУРЫ

Для иллюстрации потенциальных управленческих преимущества модели и решения процедур, мы применили их к тестовой задачи, предоставляемых производителем и дистрибьютором смазочных материалов описано выше. Проблема считает конце 10 пунктов, которые имеют общий химический состав, миксер, и упаковочной линии. Смеситель узкое работы с суточной мощностью 8500 фунтов. Смеситель, выделяемых на продуктовую линейку до 3 дней в неделю, но обычно используется только 50% рабочих дней после ее получения. установка смесителя операции включают в себя материал постановки, рецепт калибровки, контроля качества и очистки для установки стоимостью $ 100. Миксер отделен от упаковочной линии на промежуточных резервуаров для хранения продуктов, которые питаются на упаковочную линию. Таким образом, продукт переход на упаковочной линии не влияет на смеситель операций или потенциала. Незначительные затраты на установку переходе упаковочной линии составляет $ 10, который охватывает прямую труда об изменении упаковки контейнеров, этикетки продуктов и чернил для печати струй номера партии продукции.

Прогнозируемого спроса еженедельно приведены в таблице 7 для 12-недельного горизонта планирования. В таблице, каждый элемент представляет собой уникальную упаковки и этикетки конфигурации для 16-унции жира трубки стоимостью $ 1 за тюбик ". В связи с относительно высоким спросом разница, инвентарь чулок фирмы цель заключается в сохранении поставить 12 недель каждой трубки в системе. Производство взимается товарно-материальных запасов затрат для всех запасов более 12 недель поставок и backlogging затраты при инвентаризации провалов ниже целевого показателя. Ежегодные расходы товарно-материальных запасов на 37% стоимость пункта, или $ 0,01923 за тюбик в неделю. Всего за единицу товарно-материальных запасов на поставку спрос на пункт А в момент т с производства в период I, H ^ ^ к югу ИКТ, составляет $ 0,01923 (т - 2) для т> i. Backlogging расходы наказывать управления производством для погружения в безопасности материально-производственных запасов, а доступ к более быстрыми темпами в зависимости от длины отставание спроса. Стоимость за единицу backlogging на поставку спрос на пункт А по времени т с производства в период I, H ^ ^ к югу ИКТ, составляет $ 0,01923 [бета] ^ ^ к югу он (я - т) для т

производственный план мастер планировщика для тестовой задачи, приведены в таблице 8. Планировщик попытки выделить выход на целый день на одного пункта, с тем чтобы свести к минимуму издержки перехода, а также использует много расщепления, чтобы избежать длительных backorders. Он первым проектов недель поставки каждого элемента, а затем планирует элементов в порядке возрастания их недель поставок. В случае ничьей, наибольший объем продавца планируется в первую очередь. В таблице 8, в колонке W1 указывают неделю производства 1 Расписание, где L1, L2, L3 и представляют собой три 8500-фунтовые много-размеров, по одному для пункта C1, A1, и С2. Каждый серийное производство потребляет мощность одного дня, в результате чего 100% использования имеющихся возможностей в неделю 1. В неделю два, один серийное производство делится между пунктами B1 и C3. Смеситель не были использованы другие два дня она была доступна. Общая стоимость системы на 12-неделе горизонта $ 3751 с использованием активов 47,2% (т.е. 17 дней производство из имеющихся 36 дней производства).

Лагранжево-процедуры, основанные на рекомендовать производственного графика представлены в таблице 9. Этот график предусматривает производство 15 партий (41,7% использования) с каждой партии раскола среди нескольких элементов. Общая стоимость системы оптимизированного графика составляет $ 2907 или 22,5% ниже, чем текущий график. Всего установке оборудования и затрат на переход оптимизирована графика составляет $ 1990 (15 основных установок плюс 49 пункта переналадки) по сравнению с $ 1930 (17 основных установок плюс 23 пункта переналадки) для текущего плана компании. Инвентаризация расходов снизился 49,6% с $ 1821 до $ 917.

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

ВЫВОДЫ И ПОСЛЕДСТВИЯ

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

Мы предложили разработке MIP для одного семейства продуктов скоординированной capacitated много размеров проблемы и лагранжевы процедура нахождения эвристических и оптимальных решений. Математическая модель основана на жесткой древовидный фиксированной сети заряда представления предложенной Робинсон и Гао (1996) для uncapacitated проблемы. Преимущество этой модели по сравнению с традиционными динамических моделей программирования заключается в иерархической связи решения переменных с помощью переменной верхняя ограничений. Для uncapacitated проблемы, эти ограничения приблизились выпуклая оболочка области допустимых приносит очень жесткие Л. снизу. Как показано в исследовании, эта формулировка также предоставляет привлекательную платформу и нижней ограничивающей схемы capacitated проблем. На основании этих наблюдений, мы расслабились назначения и ограничения пропускной способности, уступая эффективно решить лагранжевых подзадач. Такой подход позволяет избежать NP-полных подзадач, которые будут получены только путем ослабления потенциала ограничения, традиционно предлагается capacitated динамичный рост спроса много размеров проблемы.

Лагранжевой эвристический оказались способны находить у LP-качество снизу решения, и требует меньше вычислительных ресурсов на масштабные проблемы, чем решить релаксации LP. Кроме того, лагранжиан снизу решение является хорошей отправной точкой и экономического руководства для построения высококачественных верхняя решений. Вычислительные эксперименты проверили превосходства лагранжиана эвристический над LP-основанные эвристики. Кроме того, качество LR-эвристического решения улучшились в большинстве случаев, как проблема размер увеличен. Это еще больше документов LR-эвристического Благоприятные особенности, а также потенциальную ценность в качестве инструмента поддержки принятия решений. Все, на узле 0 в B

Capacitated, скоординированных много размеров проблемы создает благоприятную почву для дальнейших исследований. Потенциальные расширения включают рассматривает сверхурочную производственных мощностей, несколько фиксированного заряда функции затрат (Липман, 1969), несколько семейств продуктов (Denizel и др.., 1996), ограничения пропускной способности на отдельных пункта уровне, а также несколько ресурсных ограничений. Обе разработки и испытания альтернативных решений проблемы и решения подходы имеют смысл. Это может быть либо оптимизации и эвристических основе. Van Roy (1983, 1986) успешно применяется кросс-разбиения методов capacitated задачи размещения объекта. Учитывая сходство дискретных месте и динамические проблемы инвентаризации спроса математические структуры, такой подход является многообещающим для оптимизации основе научных исследований. Дополнительные эвристического развития также вполне оправдано с лагранжианом основе, вперед пройти, и общие процедуры обеспечения строительства логических подходов. [В редакцию: апрель 2002. Принято редколлегией: октябрь 2003.]

Ссылки

Aggarwal А.,

Armentano, В. А., Франка, П. М.,

Аркин Е., Jonja Д.,

Аксой Ю.,

Бал, H. C., Рицман, Л. П.,

Бейкер, К. Р., Диксон П., журнал, М. J.,

Барани И., Van Roy, Т. J.,

Барани И., Van Roy, Т. J.,

Биллингтон, П. J., Макклейн, J. О.,

Bitran, Г. Р.,

Bitran, Г. Р.,

Кэмпбелл, Г. М.,

Чунг, C.,

Чунг, C., Флинн, J.,

Чунг, C., Hum, S.,

Чунг, C., Hum С.,

Диаби, М., Баль, H. C., Karwan, М. Х.,

Диаби, М., Баль, H. C., Karwan, М. Х.,

Denizel, М., Erenguc, С. С.,

Диксон, П. С.,

Дограмаджи А., Panayiotopoulos, J. C.,

Дрексл А.,

Dzielinski, Б. П.,

Eisenhut, P. S. (1975). Динамического много алгоритм расчета размера с ограниченной пропускной способностью. AIIE Сделки, 7 (2), 170-176.

Eppen, Г. Д.,

Erenguc, С. С. (1988). Multi-продукт динамического много-калибровки модели с согласованными пополнений. Naval Research Логистика, 35, 1-22.

Erenguc, С. С.,

Erenguc, С. С.,

Erlenkotter, D. (1978). Двойной основе процедуры uncapacitated расположение объекта. Исследование операций, 26 (6), 992-1009.

Эванс, J. R. (1985). Эффективного осуществления Вагнер-Уайтин алгоритм динамического много-размеров. Журнал операционного менеджмента, 5 (2), 229-235.

Эванс, J. Р. (1985b). Сетевые алгоритмы оптимизации для многих capacitated пункта много размеров проблемы. Компьютеры и организации промышленного производства, 9 (3), 297-305.

Federgruen А.,

Фишер, М. Л. (1981). Лагранжиана релаксационный метод для решения задач целочисленного программирования. Управление науки, 27 (1), 1-18.

Флориан, М.,

Флориан, М., Ленстра, J. К.,

Geoffrion, А. М. (1974). Лагранжевой релаксации для целочисленного программирования. Математическое программирование Исследование 2. Нью-Йорк: North-Holland Издательское дело, 82-114.

Гилберт, К. Д.,

Гопалакришнан, М., Дин К. Bourjolly, J.,

Haseborg, Ф. (1982). Об оптимальности совместной политики в заказе нескольких продуктов динамической модели размера партии индивидуальных и совместных стартовые расходы. Европейский журнал исследования операций, 9, 47-55.

Хелд, М., Вольф П.,

Хинди, К. С. (1995a). Решение одного пункта, capacitated динамического много-калибровки проблемы с запуском и бронирование затраты на поиск Табу. Компьютеры и организации промышленного производства, 28 (4), 701-707.

Хинди, К. С. (1995b). Алгоритмы capacitated, мульти-пункт-много размеров без установленных окон. Журнал Оперативного общества исследований, 46, 465-472.

Хинди, К. С. (1995c). Вычислительном эффективного решения многих пункта capacitated много-размеров проблемы. Компьютеры и организации промышленного производства, 28 (4), 709-719.

Хинди, К. С. (1996). Решение Стратегией поисковой Табу эвристики. Журнал Оперативного общества исследований, 47, 151-161.

Hoesel, К. П. М.,

Joneja, D. (1990). Совместные проблемы пополнения: New эвристики и худшие оценки случае производительность. Исследование операций, 38 (4), 711-723.

Као, Э. П. C. (1979). Мульти-продукт динамической модели много размеров индивидуальных и совместных расходов установки. Исследование операций, 27 (2), 279-289.

Карни, Р.,

Ким Д., Mabert, В. А.,

Кырджа, О. (1990). Эффективный алгоритм для capacitated один элемент динамической задачи размер лота. Европейский журнал исследования операций, 45, 15-24.

Кырджа, О. (1995). Прямой-двойственной алгоритм динамического много-калибровки проблемы совместными расходов установки. Naval Research Логистика, 42, 791-806.

Кырджа О.,

Kleindorfer, П. Р.,

Ламберт, А.,

Ламбрехт, М. Р.,

Lasdon, Л. С.,

Leung, J., Magnanti, Т. Л.,

Липпман, С. А. (1969). Оптимальное инвентаризации политики с несколькими стартовые расходы. Управление науки, 16 (1), 118-138.

Лотфи В.,

Любовь, С. F. (1973). Ограниченные производства и хранения моделей с кусочно вогнутой расходов. Управление науки, 20 (3), 313-318.

Лозано, S., Larraneta, J.,

Мэйс, J.,

Манн, А. С. (1958). Программирование экономической много-размеров. Управление науки, 4 (2), 115-135.

Мартин, Р. К. (1987). Создание альтернативных программ частично целочисленного-модели с помощью переменной пересмотра. Исследование операций, 35 (6), 820-831.

Миллар, Х. Х.,

Миллар, Х. Х.,

Ньюсон, Е. F. P. (1975a). Multi-пункт планирования размер лота по эвристический часть I: С фиксированной ресурсов. Управление науки, 21 (10), 1186-1193.

Ньюсон, Е. F. P. (1975b). Multi-пункт планирования размер лота по эвристический часть II: С переменной ресурсов. Управление науки, 21 (10), 1194-1203.

Pratsini, Е. (2000). Capacitated динамической задачи размер участка с переменной технологии. Компьютеры и организации промышленного производства, 38, 493-504.

Ozdamar, L.,

Робинсон, Э. П.,

Шапиро, Р., Розенфельд, Д.,

Шоу, Д. X.,

Серебро, Е. А. (1979). Скоординированная пополнение запасов, при изменяющихся во времени спрос: динамическое программирование формулировки. Логистика Naval Research Quarterly, 26 (1), 141-151.

Sox, К. Р.,

Тизи, J. М. (1991). Анализ лагранжевых разложение для многих пункта capacitated много-размеров проблемы. INFOR, 29 (4), 271-283.

Тизи, J. М.,

Trigeiro, В. В. (1987). Двойной цене эвристика для capacitated много размеров проблемы. ИМО Сделки, 67-72.

Trigeiro, В. В. Томас, Л. J.,

Ван Nunen, J. А. Е. Е.,

Van Roy, Т. J. (1983). Креста разложения для смешанного целочисленного программирования. Математическое программирование, 25, 46-63.

Van Roy, Т. J. (1986). Перекрестного алгоритма разложения capacitated расположение объекта. Исследование операций, 34 (1), 145-163.

Veinott, А. Ф., Jr (1969). Минимальная стоимость вогнутой решение Леонтьева замены моделей многоцелевых систем учета. Исследование операций, 17, 262-291.

Wagelmans А., Ван Hoesel, S.,

Вагнер, Х. М.,

Зангвилл, В. I. (1966). Детерминированных производства нескольких период планирования модели с backlogging. Управление науки, 13 (1), 105-119.

Зангвилл, В. I. (1966б). Детерминированных многопродуктовыми, multifacility производства и хранения системы. Исследование операций, 14, 846-508.

Е. Пауэлл Робинсон, Jr [кинжал]

Техас

77843-4217, адрес электронной почты: <a href="mailto:probinson@cgsb.tamu.edu"> probinson@cgsb.tamu.edu </ A>

F. Барри Лоренс

Техас

77843-3367, адрес электронной почты: <a href="mailto:Lawrence@entc.tamu.edu"> Lawrence@entc.tamu.edu </ A>

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

Е. Пауэлл Робинсон является адъюнкт-профессором по управлению цепочками поставок на Мейс бизнес-школы, штат Техас

Д-р Ф. Барри Лоренс является директором Лаборатории Сеть Поставка систем и адъюнкт-профессор Техасского