Эвристический алгоритм capacitated несколько инвентаризации поставщиком группировки проблемы

РЕЗЮМЕ

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

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

ВВЕДЕНИЕ

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

Наличие конфликтов, влияющих на решения, касающиеся уровня запасов широко признается. Например, хорошо известными экономическими заказа (ЕОК) формула (Vollmann, Берри,

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

В настоящей работе мы сформулируем несколько инвентаризации поставщиком группировки проблема, как смешанная модель целочисленного программирования. Эта формулировка является мотивированным работы Рассела и Краевский (1992a, 1992b), которые обращаются uncapacitated инвентаризации группировки проблемы. Они сформулировать одной проблемы поставщиков, 0-1 целое модель программирования (1992a) и представить эвристический, основанный на интеллектуальных округления непрерывного отдыха модели. Они показывают, что эвристический очень эффективен на наборе тестовых задач. Во втором исследовании, Рассел и Краевский (1992b) продлить ими ранее модели включают несколькими поставщиками. Они сообщают, весьма ограниченные вычислительные опыт многочисленных случае поставщик (6 пунктов в инвентаре, все от того же поставщика).

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

Наше исследование в данной работе продолжается работа Рассела и Краевски (1992b), в двух важных направлениях. Во-первых, мы включать ограничения на емкость для каждого поставщика, который добавляет еще один уровень сложности модели. Во-вторых, мы позволяем спрос на пункт должен быть разбит между поставщиками и общего потока на любой дуги, должны быть разделены между циклами. Модели Рассела и Краевский (1992b) ограничивает элемент одного поставщика, через один интервал порядка (время цикла), а единая ставка фрахта. Поток пункта считается либо нулевой, либо требовать. Хотя их эвристических работает очень хорошо (в одном случае поставщик). На тестовых задач, нет никакой гарантии, что эвристические в конечном итоге сходятся к точке близка к оптимальной. Субградиентного процедуры, используемые в наш алгоритм может быть доказано, сходятся к решению, что близко к оптимальной (Allen, Хельгасон, Кеннингтон,

ИСТОРИЯ

Инвентаризация Группировка

Исследования в области инвентаризации Группировка (Goyal, 1973;

Входящий Консолидация инвентаризации

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

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

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

Грузовые сетей и консолидация

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

Бенджамин (1989) считает, единственный сырьевой товар сетевой модели с несколькими пунктами отправления и назначения. Его модель минимизирует общую стоимость логистики и представляет собой сочетание экономического размера партии, транспорт и экономические проблемы, объем заказов. Бенджамин делает различия между отдельными размер груз для дня и общего годового потока для этого элемента, и подчеркивает необходимость для одновременной оптимизации транспортных потоков и перевозок. Он представляет собой транспортные расходы произведению скорости грузовых и количество отгружаемых и обеспечивает последовательную процедуру, основанную на решении проблемы минимальной стоимости сетевых потоков.

Делко, электроника разделение General Motors, судов товаров из заводов в городе Милуоки, Кокомо, а Матаморос (Мексика) с центрального склада в Кокомо, где товары объединены для отправки на ГМ-растений по всей территории Соединенных Штатов. Блюменфельд и др.. (1986) осуществлять детерминированной модели для сети Делко. Модели сводит к минимуму затраты товарно-материальных запасов (понесенные в начале координат, на складе, а также направления), транзитные издержки и транспортные расходы. Предполагается, что ставки на ссылку полной скорости грузовик нагрузки (фиксированная сумма) и другие номера, пропорциональны этой ставке. Разложения процедуры используются для оптимизации сети. Установлено, что размер груза и принятия решения о маршрутизации тесно взаимосвязаны и не должны быть сделаны самостоятельно.

МОДЕЛЬ РАЗРАБОТКИ Мотивация для модели

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

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

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

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

Компоненты затраты на логистику

Расходы включены товарно-материальных запасов, заказ, транспорт и покупательной способности. Все расходы, рассматриваются в годовом исчислении и понес в пункт назначения. Товарно-материальных запасов ставок устанавливаются пропорции пункта ценностей. Предполагается, что запасы истощаются по единой ставке с момента его получения до момента его использовали. Транспортные расходы моделируются захватить фактических фрахтовых ставок цитирует автоперевозчики и чрезмерное заявил поставок. Over-заявил результате поставки в расширенном фрахтовых ставок графиков, пример которой приводится в Рассел и Краевский (1992a). Для данного поставщика и для цикла, либо ставка фрахта или стоимости перевозки, но не так, применить. Это следует из того факта, что в весовой диапазон, в котором больше объявленных грузов преобладают, общая стоимость доставки остается неизменной. Заказ расходов, понесенных при размещении заказа и поставки товара поставщиком. Заказ расходы включают в себя фиксированную плату за каждый заказ для поставщика. Цены пунктов может варьироваться от поставщика к поставщику.

Предположения и математические модели

Численное исследование И РЕЗУЛЬТАТЫ

В этом разделе представлены наши обширные эксперименты с Лагранжа алгоритма, а также по сравнению с современное состояние математической системы программирования. Наш алгоритм кодируется в FORTRAN 77 и далее именуемый СОФТ (одновременной оптимизации потоков и перевозок). Выполнение софт по сравнению с OSL (IBM, 1992), которая является чрезвычайно эффективный код для решения линейных и целочисленных задач программирования. OSL был разработан IBM и часто используется для крупномасштабного оптимизации с участием тысяч переменных. Оба OSL и СОФТ будут работать на IBM 3090-600E компьютере, с использованием OSL по умолчанию параметров, предусмотренных настоящим Кодексом.

Опытно-конструкторское

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

I. Число поставщиков трех уровнях: низком (1 поставщик), средние (5 поставщиков) и высокой (10 поставщиков);

2. Количество объявлений-трех уровнях: низком (10 единиц), средней (20 пунктов), а также высокой (50 предметов);

3. Количество циклов двух уровнях: низком (5 циклов) и высокой (9 циклов);

4. Количество грузовых категории: 2 уровнях: низком (7 категорий) и высокой (15 категорий).

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

Результаты вычислительных

Этот раздел содержит сравнение OSL и СОФТ с помощью двух показатели деятельности: компьютерное время и качество решения (отклонение от оптимальности). Все вычислительные пояс сообщили в секундах процессора и не включают время, необходимое для ввода и вывода. В таблице 2, "Средняя" представляет собой среднее время центрального процессора, "Стандартное отклонение" представляет собой стандартное отклонение раз процессора, "Максимум" представляет собой максимальное процессорное время, и "минимальная" представляет собой минимум процессорного времени для выборки из 10 проблемами в в каждом наборе. Аналогичные статистические данные образцов приведены в таблице 3 для решения качества, которая определяется как процентное разрыв между оптимальное решение и СОФТ решения.

OSL допускается максимум 15000 секунд процессора (4 часа и 10 минут), чтобы решать любые задачи. Ряд критериев, которые используются для прекращения SOFT. Алгоритм имеет значение для остановки, если разрыв между верхней и нижней границ меньше или равна 1%, или после 2000 итераций, что наступит первым. Мы включили два дополнительных правилах остановки в наш алгоритм для того, чтобы программа не запускается, наконец ради несущественного выигрыша в конвергенции. Эти правила являются следующие: (I) для остановки, если не будет улучшения в верхней и нижней границы после 40 итераций. Причиной этого является экспериментальный факт, что проблемы, которые показывают не улучшилось после примерно 40 итераций, нет, за очень немногими исключениями, даже после улучшения дальнейшего тысяч итераций (II), если остановить повышение верхней границы составляет менее 1%, и улучшение нижняя граница составляет менее 1%, примерно через 300 итераций. Это объясняется тем, также экспериментальные наблюдения, проблемы, которые не обладают по меньшей мере 1% больше, либо связаны после 300 итераций, показывают весьма незначительную или не улучшается даже после дальнейшего тысяч итераций.

Как и в любой субградиентного основе процедуры, дополнительные правила остановки (я) и (II), которые необходимы для гарантии того, что алгоритм не остановится вблизи оптимального решения. Хотя СОФТ содержит эти различные правила, которые помогают сближению, мы не осведомлены о какой-либо механизм OSL включения дополнительных правилах остановки. Мягкий действительно лучший способ для решения многочисленных инвентаризации поставщиком группировки проблемой, чем OSL или это просто, как представляется, лучше из-за различных правил остановки? Чтобы ответить на этот вопрос, мы решили Л. релаксации всех 36 наборов тестовых задач в таблице 1, используя OSL. OSL взял почти в два раза больше времени, чтобы решить релаксации Л.П., чем время, затрачиваемое СОФТ получить оптимальное или близкое к оптимальному решений в натуральных числах. Разрыв между релаксации ЛП и оптимальные решения целого в среднем около 5%. После отдыха Л. занимает гораздо больше времени, чем Софт целое решение, мы утверждаем, что OSL действительно медленнее код, независимо от того или нет дополнительные правила остановки включены в OSL. Следует заметить, что тот же набор значений параметров используется на протяжении всего тестирования. Недорогие рейсы СОФТ позволяют пользователю экспериментировать с различными значениями параметров и выбрать те, которые наилучшим образом соответствуют его или ее применения ..

Результаты расчетов приведены в таблицах 2 и 3 показывают, что СОФТ является чрезвычайно эффективный код для решения многочисленных инвентаризации поставщиком группировки проблемы. Он заканчивается либо оптимальное решение или решение, которое очень близко к оптимальной на каждом из 36 наборов проблемы, требуя мало машинного времени. СОФТ оказывается примерно в 500 раз быстрее, чем OSL, а также выполнение OSL ухудшается с увеличением размера задачи. Например, OSL не в состоянии обеспечить оптимальное решение для нескольких крупных проблем, даже с 15000 секунд машинного времени на проблему. Отрицательная разница в процентах Таблица 3 показывает, что цель значение, полученное СОФТ лучше, чем это предусмотрено в OSL прекращения. OSL имеет то преимущество, встроенный препроцессор, который помогает ему быстро вникнуть в узлах ветвей и границ. Этот препроцессор, как известно, ускорить OSL значительно, но OSL рухнул на многих крупных проблем. СОФТ производит целые потоки, естественно, в то время как OSL требует целостность потоков в качестве дополнительных ограничений. Если целое число ограничений приводится в исполнение, OSL затрудняется решить даже мелкие проблемы. СОФТ занимает больше вычислительных время, когда количество элементов и количество поставщиков увеличилось, но продолжает сохранять преимущество над OSL (см. Таблицу 3, проблема множества 1, 3, 17 и 29, например).

Выполнение СОФТ особенно впечатляет по проблеме наборы с 32 по 36. СОФТ решает самая большая проблема в этой группе, 70200 целочисленных переменных (68850 целого потока переменных и 1350 бинарные переменные) и 3340 трудностей, примерно в 40 секунд процессора. Памяти требование OSL для этой конфигурации настолько велика, что мы не в состоянии решить даже релаксации П. ..

РЕЗЮМЕ

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

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

Возможные ограничения этой работы, связанные с выбором параметров пользователя в мягких и предположения, лежащие в основе модели развития. К счастью, пользователь может экспериментировать с различными значениями параметров и выбрать тех, которые наилучшим образом соответствуют его или ее применения. Такие эксперименты с практической СОФТ является эффективным с точки зрения памяти и требований машинного времени. Предположение о неизменности спроса может исключать применение модели в определенных условиях производства. Тем не менее, наш подход может быть необходимой основой для разработки стратегий группировки, когда спрос не является постоянной. Мы отмечаем, что наши целочисленного программирования модель может быть пересмотрен с целью включения стохастического спроса и время выполнения узоров. Решение в результате стохастического программирования Проблема, однако, является трудноразрешимой задачей и по-прежнему плодотворной областью исследований в области математического программирования. [В редакцию: 13 сентября 1994. Принято редколлегией: Апрель 15,1996.]

Ссылки

Аллен Е., Хельгасон Р., Кеннингтон, J.,

Бенджамин, J. (1989). Анализ инвентаризации и транспортные расходы в стесненном сети. Транспорт наук, 23 (3), 177-183. Блюменфельд, DE, Бернс, LD., Дагансо, CF, Фрик, MC, DC зал, RW (1986). Сокращение расходов на логистику в General Motors. В General Motors Research Report-5334. Уоррен, MI: General Motors.

Буффа, ПС.,

оптимальную стоимость логистики. Решение наук, 21 (1), 14-34. Чакраварти, A.K. (1981). Multi-инвентарный объект объединения в группы. Журнал оперативной общества исследований, 2, 19-26.

Чакраварти, A.K., Орлин, J.B.,

с добавкой цели с применением оптимальных групп инвентаря для совместного пополнения. Исследование операций, 30 (5), 820-834. Фишер, М.Л. (1985). Приложений, ориентированных руководство Лагранжа релаксации. Интерфейсы, IS, 10-21.

Goyal, S.K. (1973). Определение экономической частоты упаковки предметов совместно пополняются. Управление науки, 20 (2), 232-235. Зал, R.W. (1991). Выбор маршрута по грузовым сетей вес и объем ограничений. Транспорт исследований, 25B (4), 175-189. Хелд, М., Вольф П.,

Математическое программирование, 6, 66-68.

IBM Corporation. (1992). OSL-оптимизации библиотеки подпрограмм-Guide и ссылки

релиз 2. Армонк, NY: IBM.

Klincewicz, J. (1990). Решение проблемы грузовых перевозок с использованием методов размещения предприятий. Исследование операций, 38 (1), 99-109.

Малви, J., Розенбаум, Д.,

Nemhauser, G.L.,

Поляк, Б. (167). Общий метод решения экстремальных задач. Советской математики

Доклады, 593-597.

Рассел, Морская пехота Великобритании,

поставщика. Решение наук, 23 (3), 610-632.

Рассел, Морская пехота Великобритании,

Шу, F.T. (1971). Экономический заказа частоты для двух пунктов совместно пополняются. Управление науки, 17 (6), 406-410.

Tersine, Р. J. (1987). Принципы инвентаризации и управления материальными потоками (4 изд.). Нью-Джерси: Prentice Hall, 90-176.

Vollmann, TE, Берри, WL, постоянного Whybark, DC (1984). Планирование производства и системы управления. Boston, MA: Ирвин, 635-640.

Сиддхартха Syam является доцент кафедры менеджмента в Marquette University в штате Висконсин. Он получил диплом MBA в Университете Миссури и докторскую степень из Техаса

Бала Шетти является адъюнкт-профессор бизнес-анализа в Техасе