There are many use cases of operations research (OR) where the decision problem is finding an optimal sequence over time. For instance, we may be interested in allocating a resource (e.g., a machine, a human, a facility, a plane, a cloud computer) overtime to conduct a set of tasks (e.g., manufacturing, project, order picking, flight, online learning). Therefore, many practitioners involved in airport management, project management, manufacturing, etc., are interested in creating high-quality schedules. In this article, I describe how one can code such a decision problem using Python programming language and PuLP as an optimization interface. In other words, the readers will learn scheduling in Python.

1. Modeling and solving the scheduling problem in Python

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

The machine:

• Can not conduct more than one task at a time. (No multi-tasking)
• Has a setup time before starting to conduct any task.
• Processes one job after another immediately.

The tasks:

• Have a specific processing time.
• Have a specific priority (weight).
• Are equivalent to a single job (i.e., all tasks consist of one job).

The time:

• Starts from zero.

The criterion:

• Is to minimize the total weighted completion time (TWCT).

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

import pulp as op
import itertools as it

#Developer: @KeivanTafakkori, 8 March 2022

def model(I,J,p,s,dispmodel="y",solve="y", dispresult="y"):
    m = op.LpProblem("SingleMachineSchedulingProblem", 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: op.LpVariable(f"c{j}", 0, None, op.LpContinuous) for j in J}
    objs = {0: sum(w[j]*c[j] for j in J)} 
    cons = {0: {i: (sum(x[(i,j)] for j in J) == 1, f"eq1_{i}") for i in I},
            1: {j: (sum(x[(i,j)] for i in I) == 1, f"eq2_{j}") for j in J},
            2: {j: (c[j] >= c[j-1] + sum(x[(i,j)]*p[i] for i in I), f"eq3_{j}") for j in J if j!=0},
            3: {0: (c[0] == s + sum(x[(i,0)]*p[i] for i in I), "eq4_")}}
    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] #Processing time of each job
s = 5 #Setup time of the machine
I = range(len(p)) #Set of jobs
J = range(len(I)) #Set of positions

Still, I need to solve the model, so I add the following piece of code:

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

Finally, the results after the implementation are as follows:

Status --- 
 Optimal
Objective --- 
 18.25
Decision --- 
 [('c0', 8.0), ('c1', 12.0), ('c2', 19.0), ('c3', 28.0), ('x02', 1.0), ('x10', 1.0), ('x23', 1.0), ('x31', 1.0)]
[2, 4, 1, 3]

2. Visualization of the results

Even if the above piece of code has yielded the necessary results, understandable by an expert, it does not suffice the needs of a business. The results are usually hard to understand in this form. Accordingly, visualization of the obtained results matters. I add the following piece of code to make it easier to understand the results:

seq = []
for j in J:
    for i in I:
        if x[(i,j)].varValue==1:
            seq.append(i+1)
print(seq)

The above code creates a list representing the sequence suggested by the optimization model. What if we could have a Gantt chart to ease reviewing the results? As we all know, a figure is always worth more than a text. So I add the following code:

import matplotlib.pyplot as plt
import numpy as np

fig, gnt = plt.subplots()
gnt.set_xlabel('Minutes since start')
gnt.set_ylabel('Machine')
gnt.set_xlim(0, c[len(J)-1].varValue)
gnt.set_ylim(0, 50)
gnt.set_yticks([15, 25, 35])
gnt.set_yticklabels(['', '1', ''])
gnt.grid(True,color='k',linestyle='-.', alpha=0.2)

process = [(c[j-1].varValue,c[j].varValue) for j in J if j!=0] 
process.insert(0, (0,s))
process.insert(1, (s,c[0].varValue))

np.random.seed(3)
l = []
for j in J:
    l.append(tuple(np.random.choice(range(0, 2), size=3)))
     
gnt.broken_barh(process, (20, 9),color=l)
for j in J:
    if j!=0:
        for i in I:
            if x[(i,j-1)].varValue==1:
                gnt.annotate(f"J{i+1}", (process[j][0],15))
    else:
        gnt.annotate("Setup", (0,15))

for i in I:
    if x[(i,len(J)-1)].varValue==1:
        gnt.annotate(f"J{i+1}", (process[len(J)][0],15))
        
gnt.annotate(["TWCT",sum(w[j]*c[j].varValue for j in J)], ((c[len(J)-1].varValue-s)/2,10))
plt.savefig("gantt1.png")

The code creates a Gantt chart, assigns random colors to each part, and annotates them. Accordingly, the following figure is made:

Concluding remarks

In this article, I introduced how a single machine scheduling problem is solved via PuLP, an interface for optimization, in the Python programming language. The interested readers can visit previous articles on interfaces and solvers to learn more about them. Finally, if you are interested in the content we publish, 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). Single machine scheduling with PuLP in Python. Supply Chain Data Analytics. url: https://www.supplychaindataanalytics.com/single-machine-scheduling-with-pulp-in-python

Keivan Tafakkori M.Sc.

Industrial engineer focusing on leveraging optimization methods and artificial intelligence technologies using multiple programming languages to empower a business to achieve its goals!