Планирование процессов производства с временем установки

Question

Обзор

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

Проблема формулировки

Проблема состоит из

.
• Последовательность последовательных временных интервалов $ t \ in \ {1, \ dots, n_t \} $ , каждый с началом и заканчивается $ (s_t, e_t) $ и длина $ l_t= e_t-s_t $ . Подряд означает $ E_ {t}= s_ {t + 1} $ Для всех $ t \ in \ {1, \ DOTS, N_T-1 \} $ .
• Список типов товаров, которые производится: $ j \ in \ {1, ..., n_j \} $
• Требование каждого типа хорошего типа в течение промежутка времени $ d_ {j, t} $ .
• Список производственных линий $ I \ in {1, \ dots, n_i} $
• Наличие производственных линий в течение интервала времени $ a_ {i, t} $ . $ a_ {i, t} $ - это двоичный - будь то доступна или нет.
• Производственная скорость на производственную линию на тип товаров $ v_ {i, j} $ .
• Время установки из одного типа товаров на другой $ u_ {j, j '} $ .
• Цена на использование производственной линии (лизинговая), подсчитывается в минуту $ c_ {i} $

Цель состоит в том, чтобы спланировать производственные линии, чтобы спрос накрыл, а цена на лизинг минимальна.

Примечания:

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

Пример

Есть две производственные линии, т. Е. $ n_i= 2 $ и есть два типа товаров, то есть $ n_j= 2 $ .

У нас есть два интервала, то есть. $ n_t= 2 $ , у каждого есть leght 1 час. Скажи, что начинается в 13:00, второй в 2 часа дня.

Спрос:

.
• $ d_ {1,1}= 1,1 $
• $ d_ {1,2}= 1 $
• $ d_ {2,1}= 1 $
• $ d_ {2,2}= 0,5 $

Запуск производственных линий:

.
• $ c_ {1}= c_ {2}= 1 $ usd / minky

Все возможные времена настройки 30 минут, то есть.:

.
• $ u_ {j, j '}= 0,5 $ Для всех $ J, J' $ где $ j \ neq j '$ .

Скорость:

.
• $ v_ {1,1}= 1,1 $
• $ v_ {1,2}= 1,5 $
• $ v_ {2,1}= 1 $
• $ v_ {2,2}= 1 $

Очевидно, что спрос выполнен, если первая строка производит первый тип товара с промежутками интервалов, и и вторая строка производит второй тип. Стоимость 204,55. Смотрите решение здесь:

Однако может быть заманчиво включить их. Линия 1 гораздо более эффективна для второго типа товаров (1.5). Если не будет времени установки, у нас будет стоимость 180 долларов США. Однако это невозможно.

Вопрос

Что такое алгоритм, чтобы запланировать этот процесс производства оптимально?

Ответ Добро пожаловать, даже если он будет наметить путь и подход (MOLP, SAT, CSP, ...).

Идеи FO FOL

.
• Если длина интервалов будет исправлена, скажем, 1 час и время установки будет определено в терминах этих единиц, скажем, 2 часа. Тогда это может быть разрешимо по SAT / CSP.
• Идея состоит в том, чтобы использовать эволюционный алгоритм, который будет состоять из последовательности действий с мутациями (добавить активность, удалить активность, продлению активности) и кроссовером (смешать два плана случайным образом).

Answer 1

Мы используем индекс $ K $ для такого времени, что $ k \ in [s_1, e_ {n_t}] $

Введем следующие переменные:

$ \ ell ^ {i, k} $ - line $ i $ арендует на линии $ k $

$ \ alpha ^ {i, k} _ {j, j '} $ - двоичный индикатор для линии $ i $ переключается с $ j $ на $ j '$ во время $ k $ .

$ p ^ {i, k} _j $ - двоичный индикатор для линии $ i $ Производство хорошего $ j $ во время $ K $ .

$ h ^ {i, j} _j $ - двоичный индикатор, что строка $ i $ Ожидание, чтобы создать хороший $ j $ во время $ K $

$ g ^ {i, k} _j $ - Сгенерированная сумма для линии $ i $ для Хороший $ j $ во время $ K $ (либо $ v_ {i, j} $ или $ 0 $ )

Тогда цель - минимизировать $ \ sum_ {i, k} c_i \ ell ^ {i, k} $ С учетом ограничений:

Ограничения для каждого $ I, K $ :

.
• может переключаться только на 1 хорошее за раз: $ \ textrm {AT-1} \ alpha ^ {i, k} _ {j, j '} $ < / span>
• может сделать только 1 хорошее за раз: $ \ textrm {AT-1} p ^ {i, k} _j $
• может держать только 1 хорошее за раз: $ \ textrm {AT-SIGHT-1} h ^ {i, k} _j $
• При производстве, не переключение: $ \ bigvee_j p ^ {i, k} _j \ priverarrow \ neg \ bigweged_ {j, j '} \ alpha ^ {i, k} _ {j, j '} $
• Лизинг IFF Производство или переключение: $ \ ell ^ {i, k} \ leftretarrow \ bigvee_ {j, j '} \ alpha ^ {i, k} _ {j, J '} \ vee \ bigvee_j p ^ {i, k} _j $
• не лизинг подразумевает холдинг для некоторого хорошего: $ \ neg \ el ^ {i, k} \ prightarrow \ bigvee_j h ^ {i, k} _j $ < / li>

Оговорки для каждого $ i, k, j $ :

.
• Генерация только при производительности: $$ p ^ {i, k} _j \ prightarrow g ^ {i, k} _j= v_ {i, j} $$ $$ \ neg p ^ {i, k} _j \ priverarrow g ^ {i, k} _j= 0 $$
• При остановке производства он должен немедленно удерживать для того же хорошего или переключиться на другой хороший (для $ k ): $ P ^ {i, k} _j \ quild \ neg p ^ {i, k + 1} _j \ priverarrow h ^ {i, k + 1} _j \ vee \ bigvee_ { J '} \ alpha ^ {i, k + 1} _ {j, j'} $
• При выработке или удержании на $ K + 1 $ Должно быть, удерживая, удерживание или переключение на $ K < e_ {n_t} $ : $ p ^ {i, k + 1} _j \ vee h ^ {i, k + 1} _j \ prightarrow p ^ {i, k} _j \ vee h ^ {i, k} _j \ vee \ bigvee_ {j '} \ alpha ^ {i, k} _ {j', j} $

Ограничения для каждого $ i, k :

.
• При переключении он должен переключаться достаточно долго: $ (p ^ {i, k} _j \ vee h ^ {i, k} _j) \ quild \ alpha ^ {i, k + 1} _ {j, j '} \ Priverarrow \ bigwege_ {k '= k + 2} ^ {\ min (k + u_ {j, j'}, e_ {n, t})} \ alpha ^ {i, k '} _ {j, j' } $

Ограничения для каждого $ d_ {j, t} $ :

.
• $ \ sum_ {k= s_t} ^ {e_t} \ sum_i g ^ {i, k} _j \ geq d_ {j, t} $