Оптимизация CPLEX - планирование последовательности продуктов на одной машине

Question

Вот моя проблема. У меня, скажем, 10 продуктов для упаковки. Упаковка для всех 10 продуктов производится на одной линии/машине.

Существуют разные времена установки между различными продуктами. Например, время установки от Продукта 1 к Продукту 2 (вы должны отрегулировать высоту и сделать небольшую очистку) составляет 30 минут. Из продукта 2 в продукт 1 (вам нужно только отрегулировать высоту, не очистить), время настройки составляет 15 минут. От продукта 1 до продукта 3 требуется 5 минут и т. Д.

Я пытаюсь свести к минимуму время установки.

Как я могу это решить? Моя фактическая проблема имеет 100 различных продуктов (поэтому матрица 100 на 100)

Это действительно похоже на проблему с продавцом. Разница в том, что вам совершенно не нужно уходить из продукта 1 (или города A в TSP), и вам не нужно возвращаться к продукту 1 в конце.

Вот код TSP, который я использовал в прошлом. Могу ли я изменить его, чтобы решить мою проблему? Или я могу это сделать другим способом?

Спасибо!

// *********************** 
// Parameters 
// *********************** 

int  N  = ...; 

range V = 1..N; 

// arcs 

tuple  arc  {int v_dep; int v_arr;} 
setof(arc) A  = {<i,j> | i,j in V: i != j}; 

// Matrix Setup Time 

float   D[V][V] = ...; 

// *********************** 
// Decision variable 
// *********************** 


// x [<i,j>]= 1 if node j follows i 

dvar boolean x[A]; 

// flow conversion 

dvar float+ y[A]; 


// *********************** 
// Objective 
// *********************** 

// Minimize setup times 

minimize sum (<i,j> in A) D[i][j]*x[<i,j>]; 




subject to { 


forall (v in V) 

    sum (a in A: a.v_arr == v) x[a] == 1; 


forall (v in V) 

    sum (a in A: a.v_dep == v) x[a] == 1; 



forall (v in V:v != 1) 

sum (a in A: a.v_arr == v) y[a]-sum (a in A: a.v_dep == v) y[a] == 1; 


    sum (a in A: a.v_arr == 1) y[a]-sum (a in A: a.v_dep == 1) y[a] == -(N-1); 

forall (a in A) 

y[a] <= N*x[a]; 

}; 

Answer 1

Если я хорошо понимаю вашу проблему, вы можете уменьшить его TSP путем создания «Продукт 0», со стоимостью 0 от продукта 0 к продукту я, а стоимость 0 от продукта к продукту I 0.

Тогда ваша проблема с упаковкой становится TSP, которая начинается с «Product 0» и заканчивается им.