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 --- Optimal Objective --- 24.950000000000003 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:
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 Python. Supply Chain Data Analytics. url: https://www.supplychaindataanalytics.com/flow-shop-scheduling-with-pulp-in-python
Industrial engineer focusing on leveraging optimization methods and artificial intelligence technologies using multiple programming languages to empower a business to achieve its goals!
Leave a Reply