Solving Johnson rule using GEKKO solver in python

Question

I'm trying to solve a problem using Johnson's rule in GEKKO but unfortunately with no luck. It can easily be solved in excel, but I am trying to do it in python.

The problem:

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

Steps to solve:

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)]

Now some variables needs to be dependent on previous variables like so:

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

This creates an issue because python is trying to hash T[x[0]] but x[0] is not a number rather a Gekko variable. How can I bypass this issue?

any ideas?

Here is a more complete explanation of Johnson's rule compared to an optimization approach for this problem: apmonitor.com/me575/index.php/Main/ScheduleOptimization — John Hedengren

John Hedengren John Hedengren · Accepted Answer · 2021-05-23T02:55:05

Use binary variables with 25 total decisions (5x5 matrix) for x. Each decision is whether to process that product on the specific tool. The equations are that each machine can only process one product at a time (sum(row)==1) and each product can only process once (sum(column)==1). The delay and slack variable (positive when there is no delay) are minimized. The delay is zero for the first time step because there is nothing processing on machine K. The delay is positive if the subsequent K time is more the T time.

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()

After the solver finds a solution, view the solution by printing the variables.

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)

The optimal solution has a delay of 3. The correct order is 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]]

Interesting problem. I hope this helps you see how to reformulate a scheduling problem into an optimization form. There is additional information on slack variables and integer variables in the APMonitor documentation.

Solving Johnson rule using GEKKO solver in python

1 Answers