0

这是我的问题。比方说，我有 10 种产品要打包。所有 10 种产品的包装都在同一条生产线/机器上完成。

不同产品之间有不同的设置时间。例如，从产品 1 到产品 2 的设置时间（您必须调整高度，并进行小清理）为 30 分钟。从产品 2 到产品 1（只需调整高度，无需清理），设置时间为 15 分钟。从产品 1 到产品 3，需要 5 分钟，以此类推。

我正在尝试最小化设置时间。

我该如何解决这个问题？我的实际问题有 100 种不同的产品（所以是 100 x 100 矩阵）

它与旅行推销员问题非常相似。不同之处在于，您不必绝对离开产品 1（或 TSP 中的城市 A），也无需在最后返回产品 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];

 };
4

1 回答 1

0

如果我很好地理解了您的问题，您可以通过创建“产品 0”将其减少到 TSP，从产品 0 到产品 i 的成本为 0，从产品 i 到产品 0 的成本为 0。

那么你的包装问题就变成了一个以“产品 0”开始并以它结束的 TSP。

于 2016-08-30T15:49:08.773 回答