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

Question

我正在尝试使用 GEKKO 中的约翰逊规则解决问题，但不幸的是没有运气。它可以在 excel 中轻松解决，但我正在尝试在 python 中解决。

问题：

there are two machines (Machine T and Machine K) that work one after the other. A product must go through machine T first and after that through Machine K. both machines can work simultaneously, but each machine cant work on more than 1 product at a time. the factory needs to minimize the time of production of all given products (i.e. minimize the idle time of machine k)

Products time for each machine:
    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 矩阵）的二元变量。每个决定都是是否在特定工具上处理该产品。等式是每台机器一次只能处理一个产品 (sum(row)==1)，每个产品只能处理一次 (sum(column)==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 文档中有additional information on slack variables and integer variables。

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

Solving Johnson rule using GEKKO solver in python

python

gekko