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

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

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

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

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

Это очень похоже на задачу коммивояжера. Разница в том, что вам не обязательно выходить из продукта 1 (или города А в 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];

 };