## Scheduling Optimization

## Main.ScheduleOptimization History

Hide minor edits - Show changes to output

Added lines 4-11:

Manufacturing facilities employ expert schedulers and tools to help visualize and plan for production cycles, scheduled downtime, transitions, etc. This example is a comparison of three methods for scheduling problems:

* Exhaustive search

* Heuristic

* Integer Programming

The example demonstrates Gekko for solving scheduling problems and compares to exhaustive search and heuristic method.

Changed lines 92-93 from:

The order is ''P4'', ''P0'', ''P1'', ''P3'', ''P2'' with total delay of 26 on machine Z and total makespan time of 121 to complete all processing.

to:

The order is ''P4'', ''P0'', ''P1'', ''P3'', ''P2'' with total delay of 26 on machine Z and total makespan time of 121 to complete all processing. This is the same as the first row in the sorted exhaustive search list.

Changed line 276 from:

The order of the sequence is different than Johnson's rule but the total makespan time (121) is the same. The optimizer found ~~an~~ equally optimal solution.

to:

The order of the sequence is different than Johnson's rule but the total makespan time (121) is the same. The optimizer found the equally optimal solution as the second row in the sorted exhaustive search list.

Added lines 32-83:

'''Exhaustive Search'''

There are ''n!'' permutations for a production list of ''n'' length. For this specific problem with 5 products, there are ''5!=120'' combinations. An exhaustive search calculates the makespan (total time) for all possible combinations.

(:source lang=python:)

from itertools import permutations

import pandas as pd

Y = {0: 10, 1: 20, 2: 15, 3: 40, 4: 8}

Z = {0: 20, 1: 30, 2: 10, 3: 25, 4: 18}

products = Y.keys()

np = len(products)

pm = [] # list of permutations

tm = [] # list of makespan time

for order in permutations(products):

# append permutation to the pm list

pm.append(order)

# lookup time for each step

ty = [0]*(np+1); tz = [0]*(np+1)

for i in range(np):

ty[i] = Y[order[i]]

tz[i+1] = Z[order[i]]

# calculate makespan time

t = 0

for i in range(np+1):

t += max(ty[i],tz[i])

tm.append(t)

# convert to Pandas DataFrame for sorting

r = pd.DataFrame(pm,columns=['T0','T1','T2','T3','T4'])

r['makespan'] = tm

r.sort_values('makespan',inplace=True)

print(r.head(10))

(:sourceend:)

The top 10 best schedules show that there are two best candidate schedules each with a makespan of 121.

T0 T1 T2 T3 T4 makespan

4 0 1 3 2 121

4 2 0 1 3 121

0 1 3 2 4 123

0 1 3 4 2 123

4 1 3 0 2 123

4 1 3 2 0 123

0 2 4 1 3 125

0 4 1 3 2 125

2 4 0 1 3 128

2 0 1 3 4 128

While an exhaustive search is fast for this problem, it becomes impractical to calculate all combinations for more complex schedules. Heuristic or optimization methods are used when exhaustive search is too computationally demanding.

Changed lines 120-122 from:

Y = {~~ 1~~: 10, ~~2~~: 20, ~~3~~: 15, ~~4~~: 40, ~~5~~: 8~~ ~~}

Z = {~~ 1~~: 20, ~~2~~: 30, ~~3~~: 10, ~~4~~: 25, ~~5~~: 18~~ ~~}

Z = {

to:

Y = {0: 10, 1: 20, 2: 15, 3: 40, 4: 8}

Z = {0: 20, 1: 30, 2: 10, 3: 25, 4: 18}

Z = {0: 20, 1: 30, 2: 10, 3: 25, 4: 18}

Changed line 134 from:

m.Equation(ty[i] == m.sum([x[i,j]*Y[j~~+1~~] for j in range(5)]))

to:

m.Equation(ty[i] == m.sum([x[i,j]*Y[j] for j in range(5)]))

Changed line 136 from:

m.Equation(tz[i] == m.sum([x[i,j]*Z[j~~+1~~] for j in range(5)]))

to:

m.Equation(tz[i] == m.sum([x[i,j]*Z[j] for j in range(5)]))

Changed line 141 from:

m.Equation(d[0]==~~tz~~[0])

to:

m.Equation(d[0]==ty[0])

Changed lines 161-162 from:

The problem is solved with the APOPT solver in 0.1 sec with a minimized objective (time delay) of 11. ~~The order is ''P4''~~, ~~''P2'', ''P0'', ''P1'', ''P3'' with total delay of 11 on machine Z and~~ total makespan time of 121 to complete all processing.

to:

The problem is solved with the APOPT solver in 0.1 sec with a minimized objective (time delay) of 11.

(:source lang=python:)

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 Y

[[8.0] [15.0] [10.0] [20.0] [40.0]]

time on machine Z

[[18.0] [10.0] [20.0] [30.0] [25.0]]

delay

[[8.0] [3.0] [0.0] [0.0] [0.0]]

(:sourceend:)

The order is ''P4'', ''P2'', ''P0'', ''P1'', ''P3'' with total makespan time of 121 to complete all processing.

(:source lang=python:)

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 Y

[[8.0] [15.0] [10.0] [20.0] [40.0]]

time on machine Z

[[18.0] [10.0] [20.0] [30.0] [25.0]]

delay

[[8.0] [3.0] [0.0] [0.0] [0.0]]

(:sourceend:)

The order is ''P4'', ''P2'', ''P0'', ''P1'', ''P3'' with total makespan time of 121 to complete all processing.

Changed line 213 from:

<td><b>Time (~~131~~):</b></td>

to:

<td><b>Time (121):</b></td>

Added line 216:

<td align="center" bgcolor="#f0f0f0">10</td>

Deleted line 217:

Changed lines 224-237 from:

Order

[[[0.0] [0.0] [0.0] [0.0] [1.0]]

[[0.0] [0.0] [1.0] [0.0] [0

[[1.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 Y

[[8.0] [15.0] [10.0] [20.0] [40.0]]

time on machine Z

[[18.0] [10.0] [20.0] [30.0] [25.0]]

delay

[[8.0] [3.0] [0.0] [0.0] [0.0]]

(:sourceend:)

to:

The order of the sequence is different than Johnson's rule but the total makespan time (121) is the same. The optimizer found an equally optimal solution.

Changed line 196 from:

<td><b>Time (~~121~~):</b></td>

to:

<td><b>Time (131):</b></td>

Changed lines 161-162 from:

to:

The problem is solved with the APOPT solver in 0.1 sec with a minimized objective (time delay) of 11. The order is ''P4'', ''P2'', ''P0'', ''P1'', ''P3'' with total delay of 11 on machine Z and total makespan time of 121 to complete all processing.

(:html:)

<table border=0 align="center">

<tr>

<td><b>Sequence</b></td><td><b>T0</b></td><td><b>T1</b></td><td><b>T2</b></td><td><b>T3</b></td><td><b>T4</b></td><td><b>T5</b></td>

</tr>

<tr>

<td><b>Machine Y:</b></td>

<td align="center" bgcolor="#aad8e6">8</td>

<td align="center" bgcolor="#fb946d">15</td>

<td align="center" bgcolor="#bafb6d">10</td>

<td align="center" bgcolor="#fbf96d">20</td>

<td align="center" bgcolor="#fbc76d">40</td>

<td align="center"></td>

</tr>

<tr>

<td><b>Machine Z:</b></td>

<td align="center"></td>

<td align="center" bgcolor="#aad8e6">18</td>

<td align="center" bgcolor="#fb946d">10</td>

<td align="center" bgcolor="#bafb6d">20</td>

<td align="center" bgcolor="#fbf96d">30</td>

<td align="center" bgcolor="#fbc76d">25</td>

</tr>

<tr>

<td><b>Delay (11):</b></td>

<td align="center" bgcolor="#f0f0f0">8</td>

<td align="center" bgcolor="#f0f0f0">3</td>

<td align="center" bgcolor="#f0f0f0">0</td>

<td align="center" bgcolor="#f0f0f0">0</td>

<td align="center" bgcolor="#f0f0f0">0</td>

<td align="center" bgcolor="#f0f0f0">0</td>

</tr>

<tr>

<td><b>Time (121):</b></td>

<td align="center" bgcolor="#f0f0f0">8</td>

<td align="center" bgcolor="#f0f0f0">18</td>

<td align="center" bgcolor="#f0f0f0">20</td>

<td align="center" bgcolor="#f0f0f0">20</td>

<td align="center" bgcolor="#f0f0f0">40</td>

<td align="center" bgcolor="#f0f0f0">25</td>

</tr>

</table>

(:htmlend:)

(:html:)

<table border=0 align="center">

<tr>

<td><b>Sequence</b></td><td><b>T0</b></td><td><b>T1</b></td><td><b>T2</b></td><td><b>T3</b></td><td><b>T4</b></td><td><b>T5</b></td>

</tr>

<tr>

<td><b>Machine Y:</b></td>

<td align="center" bgcolor="#aad8e6">8</td>

<td align="center" bgcolor="#fb946d">15</td>

<td align="center" bgcolor="#bafb6d">10</td>

<td align="center" bgcolor="#fbf96d">20</td>

<td align="center" bgcolor="#fbc76d">40</td>

<td align="center"></td>

</tr>

<tr>

<td><b>Machine Z:</b></td>

<td align="center"></td>

<td align="center" bgcolor="#aad8e6">18</td>

<td align="center" bgcolor="#fb946d">10</td>

<td align="center" bgcolor="#bafb6d">20</td>

<td align="center" bgcolor="#fbf96d">30</td>

<td align="center" bgcolor="#fbc76d">25</td>

</tr>

<tr>

<td><b>Delay (11):</b></td>

<td align="center" bgcolor="#f0f0f0">8</td>

<td align="center" bgcolor="#f0f0f0">3</td>

<td align="center" bgcolor="#f0f0f0">0</td>

<td align="center" bgcolor="#f0f0f0">0</td>

<td align="center" bgcolor="#f0f0f0">0</td>

<td align="center" bgcolor="#f0f0f0">0</td>

</tr>

<tr>

<td><b>Time (121):</b></td>

<td align="center" bgcolor="#f0f0f0">8</td>

<td align="center" bgcolor="#f0f0f0">18</td>

<td align="center" bgcolor="#f0f0f0">20</td>

<td align="center" bgcolor="#f0f0f0">20</td>

<td align="center" bgcolor="#f0f0f0">40</td>

<td align="center" bgcolor="#f0f0f0">25</td>

</tr>

</table>

(:htmlend:)

Deleted lines 207-212:

Solver : APOPT (v1.0)

Solution time : 0.1003 sec

Objective : 20.

Successful solution

---------------------------------------------------

Changed lines 209-210 from:

[[[0.0] [0.0] [~~1.~~0] [0.0] [0~~.0~~]]

[[0.0] [0.0] [0~~.0~~] [0.0] [~~1~~.0]]

[[0.0] [0.0] [0

to:

[[[0.0] [0.0] [0.0] [0.0] [1.0]]

[[0.0] [0.0] [1.0] [0.0] [0.0]]

[[0.0] [0.0] [1.0] [0.0] [0.0]]

Changed line 215 from:

[[~~15~~.0] [~~8~~.0] [10.0] [20.0] [40.0]]

to:

[[8.0] [15.0] [10.0] [20.0] [40.0]]

Changed line 217 from:

[[~~10~~.0] [~~18~~.0] [20.0] [30.0] [25.0]]

to:

[[18.0] [10.0] [20.0] [30.0] [25.0]]

Changed line 219 from:

[[~~10~~.0] [~~2~~.0] [~~8~~.0] [0.0] [0.0]]

to:

[[8.0] [3.0] [0.0] [0.0] [0.0]]

Changed lines 40-41 from:

The order is ''P4'', ''P0'', ''P1'', ''P3'', ''P2'' with total delay of 26 on machine Z and total time of 121 ~~for~~ all processing.

to:

The order is ''P4'', ''P0'', ''P1'', ''P3'', ''P2'' with total delay of 26 on machine Z and total makespan time of 121 to complete all processing.

Changed line 75 from:

<td><b>~~Makespan~~ (121):</b></td>

to:

<td><b>Time (121):</b></td>

Changed line 75 from:

<td><b>~~Time~~ (121):</b></td>

to:

<td><b>Makespan (121):</b></td>

Changed line 40 from:

The order is ''P4'', ''P0'', ''P1'', ''P3'', ''P2''~~.~~

to:

The order is ''P4'', ''P0'', ''P1'', ''P3'', ''P2'' with total delay of 26 on machine Z and total time of 121 for all processing.

Changed line 66 from:

<td><b>Delay:</b></td>

to:

<td><b>Delay (26):</b></td>

Added lines 73-81:

</tr>

<tr>

<td><b>Time (121):</b></td>

<td align="center" bgcolor="#f0f0f0">8</td>

<td align="center" bgcolor="#f0f0f0">18</td>

<td align="center" bgcolor="#f0f0f0">20</td>

<td align="center" bgcolor="#f0f0f0">40</td>

<td align="center" bgcolor="#f0f0f0">25</td>

<td align="center" bgcolor="#f0f0f0">10</td>

<tr>

<td><b>Time (121):</b></td>

<td align="center" bgcolor="#f0f0f0">8</td>

<td align="center" bgcolor="#f0f0f0">18</td>

<td align="center" bgcolor="#f0f0f0">20</td>

<td align="center" bgcolor="#f0f0f0">40</td>

<td align="center" bgcolor="#f0f0f0">25</td>

<td align="center" bgcolor="#f0f0f0">10</td>

Added lines 64-72:

</tr>

<tr>

<td><b>Delay:</b></td>

<td align="center" bgcolor="#f0f0f0">8</td>

<td align="center" bgcolor="#f0f0f0">8</td>

<td align="center" bgcolor="#f0f0f0">0</td>

<td align="center" bgcolor="#f0f0f0">0</td>

<td align="center" bgcolor="#f0f0f0">10</td>

<td align="center" bgcolor="#f0f0f0">0</td>

<tr>

<td><b>Delay:</b></td>

<td align="center" bgcolor="#f0f0f0">8</td>

<td align="center" bgcolor="#f0f0f0">8</td>

<td align="center" bgcolor="#f0f0f0">0</td>

<td align="center" bgcolor="#f0f0f0">0</td>

<td align="center" bgcolor="#f0f0f0">10</td>

<td align="center" bgcolor="#f0f0f0">0</td>

Added lines 41-66:

(:html:)

<table border=0 align="center">

<tr>

<td><b>Sequence</b></td><td><b>T0</b></td><td><b>T1</b></td><td><b>T2</b></td><td><b>T3</b></td><td><b>T4</b></td><td><b>T5</b></td>

</tr>

<tr>

<td><b>Machine Y:</b></td>

<td align="center" bgcolor="#aad8e6">8</td>

<td align="center" bgcolor="#bafb6d">10</td>

<td align="center" bgcolor="#fbf96d">20</td>

<td align="center" bgcolor="#fbc76d">40</td>

<td align="center" bgcolor="#fb946d">15</td>

<td align="center"></td>

</tr>

<tr>

<td><b>Machine Z:</b></td>

<td align="center"></td>

<td align="center" bgcolor="#aad8e6">18</td>

<td align="center" bgcolor="#bafb6d">20</td>

<td align="center" bgcolor="#fbf96d">30</td>

<td align="center" bgcolor="#fbc76d">25</td>

<td align="center" bgcolor="#fb946d">10</td>

</tr>

</table>

(:htmlend:)

Changed line 109 from:

print('time on machine ~~T~~')

to:

print('time on machine Y')

Changed line 111 from:

print('time on machine ~~K~~')

to:

print('time on machine Z')

Changed lines 119-136 from:

to:

(:source lang=python:)

---------------------------------------------------

Solver : APOPT (v1.0)

Solution time : 0.1003 sec

Objective : 20.

Successful solution

---------------------------------------------------

Order of processing, rows=order, columns=product

[[[0.0] [0.0] [1.0] [0.0] [0.0]]

[[0.0] [0.0] [0.0] [0.0] [1.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 Y

[[15.0] [8.0] [10.0] [20.0] [40.0]]

time on machine Z

[[10.0] [18.0] [20.0] [30.0] [25.0]]

delay

[[10.0] [2.0] [8.0] [0.0] [0.0]]

(:sourceend:)

---------------------------------------------------

Solver : APOPT (v1.0)

Solution time : 0.1003 sec

Objective : 20.

Successful solution

---------------------------------------------------

Order of processing, rows=order, columns=product

[[[0.0] [0.0] [1.0] [0.0] [0.0]]

[[0.0] [0.0] [0.0] [0.0] [1.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 Y

[[15.0] [8.0] [10.0] [20.0] [40.0]]

time on machine Z

[[10.0] [18.0] [20.0] [30.0] [25.0]]

delay

[[10.0] [2.0] [8.0] [0.0] [0.0]]

(:sourceend:)

Changed lines 48-49 from:

Solve the problem with an integer programming solver ([[https://apopt.com|APOPT]]) by setting up each decision as a binary variable (0 or 1). A zero (0) is a decision to not place the item in the schedule while a one (1) is a decision to include it. There are {`5`} products with processing times {~~`y~~_~~1~~, \ldots, ~~y~~_~~5`~~} and {~~`z~~_~~1~~, \ldots, ~~z~~_~~5`~~}. The decision variables are a matrix of 25 values that can be 0 or 1:

to:

Solve the problem with an integer programming solver ([[https://apopt.com|APOPT]]) by setting up each decision as a binary variable (0 or 1). A zero (0) is a decision to not place the item in the schedule while a one (1) is a decision to include it. There are {`5`} products with processing times {`ty_0, \ldots, ty_4`} and {`tz_0, \ldots, tz_4`}. The decision variables are a matrix of 25 values that can be 0 or 1:

Changed lines 60-61 from:

The time ~~{`(t)`} ~~to process on ~~machines~~ Y {`(ty)`} and Z {`(tz)`} ~~are~~:

to:

The time to process on machine Y {`(ty)`} and machine Z {`(tz)`} is:

Deleted line 118:

Changed lines 125-139 from:

Order of processing, rows=order, columns=product

[[[0.0] [0.0] [1.0] [0.0] [0.0]]

[[0.0] [0.0] [0.0] [0.0] [1.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

[[15.0] [8.0] [10.0] [20.0] [40.0]]

time on machine K

[[10.0] [18.0] [20.0] [30.0] [25.0]]

delay

[[10.0] [2.0] [8.0] [0.0] [0.0]]

(:sourceend:)

to:

Order of processing, rows=order, columns=product

[[[0.0] [0.0] [1.0] [0.0] [0.0]]

[[0.0] [0.0] [0.0] [0.0] [1.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

[[15.0] [8.0] [10.0] [20.0] [40.0]]

time on machine K

[[10.0] [18.0] [20.0] [30.0] [25.0]]

delay

[[10.0] [2.0] [8.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]]

[[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

[[15.0] [8.0] [10.0] [20.0] [40.0]]

time on machine K

[[10.0] [18.0] [20.0] [30.0] [25.0]]

delay

[[10.0] [2.0] [8.0] [0.0] [0.0]]

Changed lines 37-40 from:

* The lowest time is ''~~P5~~'' and it is assigned to be first because the lowest time is for machine Y.

* Then next lowest is ''~~P3~~'' and it is assigned to be last because the lowest time is for machine Z.

The order is ''~~P5~~'', ''~~P1~~'', ''~~P2~~'', ''~~P4~~'', ''~~P3~~''.

* Then next lowest is ''

The order is ''

to:

* The lowest time is ''P4'' and it is assigned to be first because the lowest time is for machine Y.

* Then next lowest is ''P2'' and it is assigned to be last because the lowest time is for machine Z.

The order is ''P4'', ''P0'', ''P1'', ''P3'', ''P2''.

* Then next lowest is ''P2'' and it is assigned to be last because the lowest time is for machine Z.

The order is ''P4'', ''P0'', ''P1'', ''P3'', ''P2''.

Changed lines 10-11 from:

to:

<table border=0 align="center">

Changed line 20 from:

<td align="center" bgcolor="#~~abc76d~~">8</td>

to:

<td align="center" bgcolor="#aad8e6">8</td>

Changed line 28 from:

<td align="center" bgcolor="#~~abc76d~~">18</td>

to:

<td align="center" bgcolor="#aad8e6">18</td>

Deleted lines 31-32:

----

Changed line 11 from:

<table border=0 align="~~center~~">

to:

<table border=0 align="left">

Deleted lines 10-12:

<td><img src="/me575/uploads/Main/scheduling.png"></td>

<td>

Deleted line 31:

Changed line 16 from:

to:

<td><b>Product</b></td><td><b>P0</b></td><td><b>P1</b></td><td><b>P2</b></td><td><b>P3</b></td><td><b>P4</b></td>

Changed line 19 from:

<td><b>Machine Y</b></td>

to:

<td><b>Machine Y:</b></td>

Changed line 27 from:

<td><b>Machine Z</b></td>

to:

<td><b>Machine Z:</b></td>

Changed line 122 from:

The problem is solved with the APOPT solver in 0.1 sec with a minimized objective (time delay) of 20. The selected order is ~~3~~, ~~5~~, ~~1~~, ~~2~~, ~~4~~.

to:

The problem is solved with the APOPT solver in 0.1 sec with a minimized objective (time delay) of 20. The selected order is P3, P5, P1, P2, P4.

Added lines 1-145:

(:title Scheduling Optimization:)

(:keywords Optimization, Selection, Schedule, Plan, Machine, Time, Decision, Maximize, Minimize, Benchmark:)

(:description The objective of the scheduling optimization problem is to minimize the delay where products are produced in two successive steps with different processing times. This scheduling problem is solved with mixed-integer programming in Python Gekko.:)

'''Objective:''' Minimize the delay for the production of 5 products on 2 machines. Each product requires a different amount of time to process for each step.

There are 5 products that require 2 processing steps on separate machines. The two machines (machine Y and machine Z) work one after the other. A product must go through machine Y first and after that through machine Z. Both machines can work simultaneously, but each machine cannot work on more than 1 product at a time. The factory needs to minimize the time of production of all given products. This is equivalent to minimizing the idle time of machine Z.

(:html:)

<table><tr>

<td><img src="/me575/uploads/Main/scheduling.png"></td>

<td>

<table border=0 align="center">

<tr>

<td></td><td><b>Product</b></td><td><b>P0</b></td><td><b>P1</b></td><td><b>P2</b></td><td><b>P3</b></td><td><b>P4</b></td>

</tr>

<tr>

<td><b>Machine Y</b></td>

<td align="center" bgcolor="#bafb6d">10</td>

<td align="center" bgcolor="#fbf96d">20</td>

<td align="center" bgcolor="#fb946d">15</td>

<td align="center" bgcolor="#fbc76d">40</td>

<td align="center" bgcolor="#abc76d">8</td>

</tr>

<tr>

<td><b>Machine Z</b></td>

<td align="center" bgcolor="#bafb6d">20</td>

<td align="center" bgcolor="#fbf96d">30</td>

<td align="center" bgcolor="#fb946d">10</td>

<td align="center" bgcolor="#fbc76d">25</td>

<td align="center" bgcolor="#abc76d">18</td>

</tr>

</table>

</td></tr></table>

(:htmlend:)

'''Heuristic Solution: Johnson's Rule'''

Similar to the [[Main/KnapsackOptimization|Knapsack Optimization]], there is a heuristic solution that is problem-specific and achieves optimal results under certain restrictive assumptions. [[https://en.wikipedia.org/wiki/Johnson%27s_rule|Johnson's Rule]] is a method for scheduling the jobs in two work centers with constant job time. Job times are not affected by the sequence and products are processed on the first machine before moving to the second machine. Johnson's rule selects the product with the shortest activity time and assigns it to be processed first if the shortest time is for machine Y. If the shortest time is for machine Z, it assigns the product to the end of the list. The next shortest time is selected and assigned as the second or second to last product if those were selected previously. The process is repeated until all products are ordered.

* The lowest time is ''P5'' and it is assigned to be first because the lowest time is for machine Y.

* Then next lowest is ''P3'' and it is assigned to be last because the lowest time is for machine Z.

The order is ''P5'', ''P1'', ''P2'', ''P4'', ''P3''.

'''Optimization Solution: Integer Programming'''

The same heuristics do not work if there are any changes in the assumptions that would invalidate Johnson's rule. This may happen if the problem changes or there is a priority for finishing one product over another. There may also be additional constraints a third processing step could be introduced. A more flexible approach is to solve the problem with [[https://apmonitor.com/wiki/index.php/Main/IntegerProgramming|Integer Linear Programming (ILP)]]. Variables, equations, and an objective are created to fit into a standard form that an optimizer can solve.

{$ \begin{align} & \text{maximize} && \mathbf{c}^\mathrm{T} \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \le \mathbf{b} \\ & && \mathbf{x} \ge \mathbf{0} \\ &&& \mathbf{x} \in \mathbb{Z}^n \end{align} $}

Solve the problem with an integer programming solver ([[https://apopt.com|APOPT]]) by setting up each decision as a binary variable (0 or 1). A zero (0) is a decision to not place the item in the schedule while a one (1) is a decision to include it. There are {`5`} products with processing times {`y_1, \ldots, y_5`} and {`z_1, \ldots, z_5`}. The decision variables are a matrix of 25 values that can be 0 or 1:

{$x = \left [ \begin{matrix} x_{0,0} & x_{0,1} & x_{0,2} & x_{0,3} & x_{0,4} \\ x_{1,0} & x_{1,1} & x_{1,2} & x_{1,3} & x_{1,4}\\x_{2,0} & x_{2,1} & x_{2,2} & x_{2,3} & x_{2,4} \\ x_{3,0} & x_{3,1} & x_{3,2} & x_{3,3} & x_{3,4} \\ x_{4,0} & x_{4,1} & x_{4,2} & x_{4,3} & x_{4,4}\\ \end{matrix} \right ]$}

Each row represents a new processing step (5 total) and each column is the product (5 total). Only one product is selected to be processed first, second, third, and so on. This is mathematically expressed with the sum of each row equal to 1.

{$\sum_{j=0}^4 x_{i,j} = 1 \quad \forall \; i=0\ldots4$}

A product is only processed once with the sum of each row equal to 1.

{$\sum_{i=0}^4 x_{i,j} = 1 \quad \forall \; j=0\ldots4$}

The time {`(t)`} to process on machines Y {`(ty)`} and Z {`(tz)`} are:

{$ty_i = \sum_{j=0}^4 Y_j x_{i,j} = 1 \quad \forall \; i=0\ldots4$}

{$tz_i = \sum_{j=0}^4 Z_j x_{i,j} = 1 \quad \forall \; i=0\ldots4$}

The delay {`d\ge0`} is calculated with help of a slack variable {`s\ge0`} that is non-zero only if the delay would be negative. This clips the calculated delay at a lower bound of 0 if the processing time for Z is less than the next processing time for Y.

{$d_i \ge tz_{i-1} - ty_i + s_i$}

The delay and slack variables are minimized to find the optimal solution.

(:div id=gekko:)

(:source lang=python:)

from gekko import GEKKO

m = GEKKO(remote=False)

Y = { 1: 10, 2: 20, 3: 15, 4: 40, 5: 8 }

Z = { 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 for machine Y and Z

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 on Y and Z

ty = m.Array(m.Var,5)

tz = m.Array(m.Var,5)

for i in range(5):

# time to process on Y

m.Equation(ty[i] == m.sum([x[i,j]*Y[j+1] for j in range(5)]))

# time to process on Z

m.Equation(tz[i] == m.sum([x[i,j]*Z[j+1] for j in range(5)]))

# delay time on Z

d = m.Array(m.Var,5,lb=0)

s = m.Array(m.Var,5,lb=0)

m.Equation(d[0]==tz[0])

m.Equation(s[0]==0)

for i in range(1,5):

m.Equation(d[i]>=tz[i-1]-ty[i]+s[i])

m.Minimize(m.sum(d))

m.Minimize(1e-3*m.sum(s))

m.options.SOLVER=1

m.solve()

print('Order of processing, rows=order, columns=product')

print(x)

print('time on machine T')

print(ty)

print('time on machine K')

print(tz)

print('delay')

print(d)

(:sourceend:)

The problem is solved with the APOPT solver in 0.1 sec with a minimized objective (time delay) of 20. The selected order is 3, 5, 1, 2, 4.

(:source lang=python:)

---------------------------------------------------

Solver : APOPT (v1.0)

Solution time : 0.1003 sec

Objective : 20.

Successful solution

---------------------------------------------------

Order of processing, rows=order, columns=product

[[[0.0] [0.0] [1.0] [0.0] [0.0]]

[[0.0] [0.0] [0.0] [0.0] [1.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

[[15.0] [8.0] [10.0] [20.0] [40.0]]

time on machine K

[[10.0] [18.0] [20.0] [30.0] [25.0]]

delay

[[10.0] [2.0] [8.0] [0.0] [0.0]]

(:sourceend:)

(:keywords Optimization, Selection, Schedule, Plan, Machine, Time, Decision, Maximize, Minimize, Benchmark:)

(:description The objective of the scheduling optimization problem is to minimize the delay where products are produced in two successive steps with different processing times. This scheduling problem is solved with mixed-integer programming in Python Gekko.:)

'''Objective:''' Minimize the delay for the production of 5 products on 2 machines. Each product requires a different amount of time to process for each step.

There are 5 products that require 2 processing steps on separate machines. The two machines (machine Y and machine Z) work one after the other. A product must go through machine Y first and after that through machine Z. Both machines can work simultaneously, but each machine cannot work on more than 1 product at a time. The factory needs to minimize the time of production of all given products. This is equivalent to minimizing the idle time of machine Z.

(:html:)

<table><tr>

<td><img src="/me575/uploads/Main/scheduling.png"></td>

<td>

<table border=0 align="center">

<tr>

<td></td><td><b>Product</b></td><td><b>P0</b></td><td><b>P1</b></td><td><b>P2</b></td><td><b>P3</b></td><td><b>P4</b></td>

</tr>

<tr>

<td><b>Machine Y</b></td>

<td align="center" bgcolor="#bafb6d">10</td>

<td align="center" bgcolor="#fbf96d">20</td>

<td align="center" bgcolor="#fb946d">15</td>

<td align="center" bgcolor="#fbc76d">40</td>

<td align="center" bgcolor="#abc76d">8</td>

</tr>

<tr>

<td><b>Machine Z</b></td>

<td align="center" bgcolor="#bafb6d">20</td>

<td align="center" bgcolor="#fbf96d">30</td>

<td align="center" bgcolor="#fb946d">10</td>

<td align="center" bgcolor="#fbc76d">25</td>

<td align="center" bgcolor="#abc76d">18</td>

</tr>

</table>

</td></tr></table>

(:htmlend:)

'''Heuristic Solution: Johnson's Rule'''

Similar to the [[Main/KnapsackOptimization|Knapsack Optimization]], there is a heuristic solution that is problem-specific and achieves optimal results under certain restrictive assumptions. [[https://en.wikipedia.org/wiki/Johnson%27s_rule|Johnson's Rule]] is a method for scheduling the jobs in two work centers with constant job time. Job times are not affected by the sequence and products are processed on the first machine before moving to the second machine. Johnson's rule selects the product with the shortest activity time and assigns it to be processed first if the shortest time is for machine Y. If the shortest time is for machine Z, it assigns the product to the end of the list. The next shortest time is selected and assigned as the second or second to last product if those were selected previously. The process is repeated until all products are ordered.

* The lowest time is ''P5'' and it is assigned to be first because the lowest time is for machine Y.

* Then next lowest is ''P3'' and it is assigned to be last because the lowest time is for machine Z.

The order is ''P5'', ''P1'', ''P2'', ''P4'', ''P3''.

'''Optimization Solution: Integer Programming'''

The same heuristics do not work if there are any changes in the assumptions that would invalidate Johnson's rule. This may happen if the problem changes or there is a priority for finishing one product over another. There may also be additional constraints a third processing step could be introduced. A more flexible approach is to solve the problem with [[https://apmonitor.com/wiki/index.php/Main/IntegerProgramming|Integer Linear Programming (ILP)]]. Variables, equations, and an objective are created to fit into a standard form that an optimizer can solve.

{$ \begin{align} & \text{maximize} && \mathbf{c}^\mathrm{T} \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \le \mathbf{b} \\ & && \mathbf{x} \ge \mathbf{0} \\ &&& \mathbf{x} \in \mathbb{Z}^n \end{align} $}

Solve the problem with an integer programming solver ([[https://apopt.com|APOPT]]) by setting up each decision as a binary variable (0 or 1). A zero (0) is a decision to not place the item in the schedule while a one (1) is a decision to include it. There are {`5`} products with processing times {`y_1, \ldots, y_5`} and {`z_1, \ldots, z_5`}. The decision variables are a matrix of 25 values that can be 0 or 1:

{$x = \left [ \begin{matrix} x_{0,0} & x_{0,1} & x_{0,2} & x_{0,3} & x_{0,4} \\ x_{1,0} & x_{1,1} & x_{1,2} & x_{1,3} & x_{1,4}\\x_{2,0} & x_{2,1} & x_{2,2} & x_{2,3} & x_{2,4} \\ x_{3,0} & x_{3,1} & x_{3,2} & x_{3,3} & x_{3,4} \\ x_{4,0} & x_{4,1} & x_{4,2} & x_{4,3} & x_{4,4}\\ \end{matrix} \right ]$}

Each row represents a new processing step (5 total) and each column is the product (5 total). Only one product is selected to be processed first, second, third, and so on. This is mathematically expressed with the sum of each row equal to 1.

{$\sum_{j=0}^4 x_{i,j} = 1 \quad \forall \; i=0\ldots4$}

A product is only processed once with the sum of each row equal to 1.

{$\sum_{i=0}^4 x_{i,j} = 1 \quad \forall \; j=0\ldots4$}

The time {`(t)`} to process on machines Y {`(ty)`} and Z {`(tz)`} are:

{$ty_i = \sum_{j=0}^4 Y_j x_{i,j} = 1 \quad \forall \; i=0\ldots4$}

{$tz_i = \sum_{j=0}^4 Z_j x_{i,j} = 1 \quad \forall \; i=0\ldots4$}

The delay {`d\ge0`} is calculated with help of a slack variable {`s\ge0`} that is non-zero only if the delay would be negative. This clips the calculated delay at a lower bound of 0 if the processing time for Z is less than the next processing time for Y.

{$d_i \ge tz_{i-1} - ty_i + s_i$}

The delay and slack variables are minimized to find the optimal solution.

(:div id=gekko:)

(:source lang=python:)

from gekko import GEKKO

m = GEKKO(remote=False)

Y = { 1: 10, 2: 20, 3: 15, 4: 40, 5: 8 }

Z = { 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 for machine Y and Z

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 on Y and Z

ty = m.Array(m.Var,5)

tz = m.Array(m.Var,5)

for i in range(5):

# time to process on Y

m.Equation(ty[i] == m.sum([x[i,j]*Y[j+1] for j in range(5)]))

# time to process on Z

m.Equation(tz[i] == m.sum([x[i,j]*Z[j+1] for j in range(5)]))

# delay time on Z

d = m.Array(m.Var,5,lb=0)

s = m.Array(m.Var,5,lb=0)

m.Equation(d[0]==tz[0])

m.Equation(s[0]==0)

for i in range(1,5):

m.Equation(d[i]>=tz[i-1]-ty[i]+s[i])

m.Minimize(m.sum(d))

m.Minimize(1e-3*m.sum(s))

m.options.SOLVER=1

m.solve()

print('Order of processing, rows=order, columns=product')

print(x)

print('time on machine T')

print(ty)

print('time on machine K')

print(tz)

print('delay')

print(d)

(:sourceend:)

The problem is solved with the APOPT solver in 0.1 sec with a minimized objective (time delay) of 20. The selected order is 3, 5, 1, 2, 4.

(:source lang=python:)

---------------------------------------------------

Solver : APOPT (v1.0)

Solution time : 0.1003 sec

Objective : 20.

Successful solution

---------------------------------------------------

Order of processing, rows=order, columns=product

[[[0.0] [0.0] [1.0] [0.0] [0.0]]

[[0.0] [0.0] [0.0] [0.0] [1.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

[[15.0] [8.0] [10.0] [20.0] [40.0]]

time on machine K

[[10.0] [18.0] [20.0] [30.0] [25.0]]

delay

[[10.0] [2.0] [8.0] [0.0] [0.0]]

(:sourceend:)