какая эвристика должна использоваться для комплексного планирования производства и транспортировки MIP?

Пытаюсь решить довольно распространенный MIP. Вот характеристики проблемы.

  1. Мультипродукция, Мультиплощадка (площадки одновременно служат местами хранения производства, спроса и запасов). еженедельные периоды времени
  2. продукты (единица: ящики) могут производиться только отдельными партиями с использованием ограниченного количества смен / партий на каждом объекте в течение каждой недели.
  3. Транспорт разрешен между сайтами для удовлетворения спроса на любом сайте
  4. Кроме того, в каждом месте должен быть соблюден минимальный уровень запасов на конец недели.

Текущее решение от решателя (gurobi) никогда не достигает зазора MIP лучше 15% от наилучшего предела.

Если у этой проблемы нет фиксированных размеров партии (можно произвести любое количество за смену), это просто. Но если нет, может ли кто-нибудь предложить простые эвристические методы для решения такого рода MIP?


gurobi mathematical-optimization linear-programming integer-programming
person VM1    schedule 05.04.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

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

Таким образом, вместо того, чтобы иметь p(t), который объявляет, сколько производить за период t (на одном участке), вы должны смоделировать его p(t,u), где u - это элемент спроса. Обычно это дает гораздо лучшую производительность при соответствующих условиях Big-M, хотя и не решает вашу проблему дискретной партии. Но я бы предположил, что, если партии спроса также имеют дискретные размеры, у вас хорошие шансы получить решение с дискретными размерами партии.

Если это не так, вы можете снова попробовать использовать дискретные переменные для p(t,u), общая производительность в любом случае должна быть намного лучше.

person Sebastian Werk    schedule 08.04.2015

arrow_upward
0
arrow_downward

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

person pbc1303    schedule 09.05.2015