Flow shop scheduling with PuLP in Python

In previous articles, I modeled and solved a single machine scheduling problem. What if we have two resources that operate in a pre-determined sequence (but not in parallel) to process a set of similar jobs? The so-called “flow shop” scheduling models focus on these situations. It can be production scheduling inside a factory. Or it can be service scheduling between facilities and customers inside a supply chain. Accordingly, flow shop scheduling has numerous applications. In this article, I propose a simple model for flow shop scheduling in Python.

Modeling and solving flow shop scheduling problem in Python

Herein, I code the decision problem according to the following assumptions and regarding the elements of the decision making environment:

The machines:

  • Can not conduct more than one task at a time. (No multi-tasking)
  • Have a setup time before starting to conduct any task.
  • May not process one job after another immediately (except the first one).
  • Operate in a predetermined sequence.

The tasks:

  • Have a specific processing time on each machine.
  • Have a specific priority (weight) for their completion.
  • Are equivalent to a single job (i.e., all tasks consist of one job).
  • Follow a predetermined process route.
  • Follow the same sequence (permutation) on all machines.

The time:

  • Starts from zero (for the first machine).

The criterion:

  • Is to minimize the total weighted completion time (TWCT) (for jobs that leave the last machine in the sequence).

Herein, I provide a code that models the decision problem, satisfying the mentioned assumptions:

import pulp as op
import itertools as it

#Developer: @KeivanTafakkori, 14 March 2022

def model(I,J,K,p,s,dispmodel="n",solve="y", dispresult="y"):
    m    = op.LpProblem("FlowShopSchedulingProblem", op.LpMinimize)
    x    = {(i,j): op.LpVariable(f"x{i}{j}", 0,1, op.LpBinary) for i,j in it.product(I, J)}
    c    = {(j,k): op.LpVariable(f"c{j}{k}", 0, None, op.LpContinuous) for j,k in it.product(J, K)}
    maxi = {(j,k): op.LpVariable(f"maxi{j}{k}", 0, None, op.LpContinuous) for j,k in it.product(J, K)}
    objs = {0: sum(w[j]*c[(j,1)] for j in J)}
    cons = {0: {i: (sum(x[(i,j)] for j in J) == 1, f"eq0_{i}") for i in I},
            1: {j: (sum(x[(i,j)] for i in I) == 1, f"eq1_{j}") for j in K},
            2: {j: (c[(j,1)] >= sum(x[(i,j)]*p[1][i] for i in I) + maxi[(j,1)], f"eq2_{j}") for j in J if j!=0},
            3: {0: (c[(0,1)] == s[1] + sum(x[(i,0)]*p[1][i] for i in I) + c[(0,0)], "eq3_")},
            4: {j: (c[(j,0)] >= c[(j-1,0)] + sum(x[(i,j)]*p[0][i] for i in I), f"eq4_{j}") for j in J if j!=0},
            5: {0: (c[(0,0)] == s[0] + sum(x[(i,0)]*p[0][i] for i in I), "eq5_")},
            6: {j: (maxi[(j,1)] >= c[(j-1,1)], f"eq6_{j}") for j in J if j!=0},
            7: {j: (maxi[(j,1)] >= c[(j,0)], f"eq7_{j}") for j in J}}
    m += objs[0]
    for keys1 in cons: 
        for keys2 in cons[keys1]: m += cons[keys1][keys2]
        if dispmodel=="y":
            print("Model --- \n",m)
        if solve == "y":
            result = m.solve(op.PULP_CBC_CMD(timeLimit=None))
            print("Status --- \n", op.LpStatus[result])
            if dispresult == "y" and op.LpStatus[result] =='Optimal':
                print("Objective --- \n", op.value(m.objective))
                print("Decision --- \n", [(variables.name,variables.varValue) for variables in m.variables() if variables.varValue!=0])
    return m, c, x

w = [0.1, 0.4, 0.15, 0.35] #Priority weight of each job
p = [[  7,   3,    9,    4],
     [  7,   3,    9,    4]] #Processing time of each job on each machine
s = [5, 2] #Setup times of the machines
I = range(len(p[0])) #Set of jobs
J = range(len(I)) #Set of positions
K = range(len(p)) #Set of machines

To solve the model, I use the following command:

m, c, x = model(I,J,K,p,s) #Model and solve the problem

Fortunately, there are no errors, the status is reported feasible and optimal, and the following results are obtained:

Status --- 
Objective --- 
Decision --- 
 [('c00', 8.0), ('c01', 13.0), ('c10', 12.0), ('c11', 17.0), ('c20', 19.0), ('c21', 26.0), ('c30', 28.0), ('c31', 37.0), ('maxi01', 8.0), ('maxi11', 13.0), ('maxi21', 19.0), ('maxi31', 28.0), ('x02', 1.0), ('x10', 1.0), ('x23', 1.0), ('x31', 1.0)]

Therefore, the obtained sequence is: 2->4->1->3, which is similar for all machines. Finally, a visualization of the results can be as follows:

Flow shop scheduling in Python

Concluding remarks

In this article, I created a simple and basic model for flow shop scheduling in Python then solved it using pulp, an interface in Python, which by default uses the open-source CBC solver for integer programming models. If you found the description interesting, let us know by commenting below this article!

If this article is going to be used in research or other publishing methods, you can cite it as Tafakkori (2022) (in text) and refer to it as follows: Tafakkori, K. (2022). Flow shop scheduling with PuLP in PythonSupply Chain Data Analytics. url: https://www.supplychaindataanalytics.com/flow-shop-scheduling-with-pulp-in-python

Leave a Reply

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.