在python中使用GEKKO求解器求解Johnson规则

Question

我试图在GEKKO中使用Johnson规则来解决一个问题，但不幸的是没有成功。它可以很容易地在excel中解决，但我正在尝试在python中解决。

问题：

有两台机器(机器T和机器K(依次工作另一个。产品必须先通过机器T，然后再通过通过机器K，两台机器可以同时工作，但每台机器机器一次不能处理一个以上的产品。工厂需要以最大限度地缩短所有给定产品的生产时间(即。最小化机器的空闲时间k(

每台机器的产品时间：

T.   K.
1.  10   20
2.  20   30
3.  15   10
4.  40   25
5.   8   18

解决步骤：

from Gekko import GEKKO
m = GEKK()
T = { 1: 10, 2: 20, 3: 15, 4: 40, 5: 8 }
K = { 1: 20, 2: 30, 3: 10, 4: 25, 5: 18 }
x = [m.Var(lb=1,ub=5,integer=True) for i in range(5)]

现在，一些变量需要依赖于以前的变量，比如：

idle1 = T[x[0]]
idle2 = T[x[1]] - K[x[0]]
idle3 = T[x[2]] - idle2 + m.if2(idle2<0, idle2, 0)
...
...

这造成了一个问题，因为python试图对T[x[0]进行散列，但x[0]不是一个数字，而是一个Gekko变量。如何绕过此问题？

有什么想法吗？

Answer 1

为x使用具有25个总决策(5x5矩阵(的二进制变量。每个决定都是关于是否在特定工具上处理该产品。方程式是，每台机器一次只能处理一个产品(总和(行(==1(，每个产品只能处理一次(总和(列(==1。延迟和松弛变量(无延迟时为正(最小化。第一个时间步长的延迟为零，因为机器K上没有任何处理。如果随后的K时间大于T时间，则延迟为正。

from gekko import GEKKO
m = GEKKO(remote=False)
T = { 1: 10, 2: 20, 3: 15, 4: 40, 5: 8 }
K = { 1: 20, 2: 30, 3: 10, 4: 25, 5: 18 }
x = m.Array(m.Var,(5,5),value=0,lb=0,ub=1,integer=True)
for i in range(5):
# 5 time slots, 5 order options
m.Equation(m.sum([x[i,j] for j in range(5)])==1)
m.Equation(m.sum([x[j,i] for j in range(5)])==1)
# time to process
tT = m.Array(m.Var,5)
tK = m.Array(m.Var,5)
for i in range(5):
# time to process on T
m.Equation(tT[i] == m.sum([x[i,j]*T[j+1] for j in range(5)]))
# time to process on K
m.Equation(tK[i] == m.sum([x[i,j]*K[j+1] for j in range(5)]))
# added delay time
delay = m.Array(m.Var,5,lb=0)
slk   = m.Array(m.Var,5,lb=0)
m.Equation(delay[0]==tT[0])
m.Equation(slk[0]==0)
for i in range(1,5):
m.Equation(delay[i]>=tK[i-1]-tT[i]+slk[i])
m.Minimize(m.sum(delay))
m.Minimize(1e-3*m.sum(slk))
m.options.SOLVER=1
m.solve()

求解器找到解决方案后，通过打印变量查看解决方案。

print('Order of processing, rows=order, columns=product')
print(x)
print('time on machine T')
print(tT)
print('time on machine K')
print(tK)
print('delay')
print(delay)

最优解的延迟为3。正确的顺序是5、3、1、2、4。

Order of processing, rows=order, columns=product
[[[0.0] [0.0] [0.0] [0.0] [1.0]]
[[0.0] [0.0] [1.0] [0.0] [0.0]]
[[1.0] [0.0] [0.0] [0.0] [0.0]]
[[0.0] [1.0] [0.0] [0.0] [0.0]]
[[0.0] [0.0] [0.0] [1.0] [0.0]]]
time on machine T
[[8.0] [15.0] [10.0] [20.0] [40.0]]
time on machine K
[[18.0] [10.0] [20.0] [30.0] [25.0]]
delay
[[8.0] [3.0] [0.0] [0.0] [0.0]]

有趣的问题。我希望这能帮助你了解如何将调度问题重新表述为优化形式。APMonitor文档中有关于松弛变量和整数变量的其他信息。