Job shop with minimization of total schedule duration (makespan) - solution using the CP Optimizer solver
The production scheduling problem in a job shop environment, also known as process layout, is one of the most famous problems in production management. It involves scheduling a set of jobs (batches or tasks), where each job consists of a sequence of operations that need to be processed on specific resources (machines) in a particular sequence [1] . The complexity of the problem arises from the need to optimize the allocation of resources to minimize some operation service level indicators, such as the total schedule duration (makespan), the average waiting time, or other performance criteria.
Job shop scheduling, due to its computational complexity, is widely acknowledged as an NP-hard problem. This classification implies that finding the optimal solution becomes increasingly challenging as the number of jobs and machines escalates.
Various approaches are used to address the complexity of the job shop problem, including exact methods, such as integer linear and constraint programming algorithms, and heuristic and meta-heuristic methods, such as dispatching rules and genetic algorithms.
This tutorial solves the job shop problem using constraint programming models with the CP Optimizer solver. This approach is particularly effective for dealing with the complexity and numerous constraints characteristic of this type of problem. Constraint programming makes it possible to model the precedence constraints of operations, the availability of machines, and other characteristics of the job shop production environment in a direct and natural form.
The CP Optimizer, in particular, can efficiently explore the space of possible solutions through constraint propagation techniques. This results in a ability to find competitive solutions reasonably, making it a powerful and practical tool for effective production scheduling in industrial environments.
Importing the required libraries
One recommendation is to install the Anaconda package for the Python language [2] , which has most of the libraries needed for modeling. In addition, it is necessary to install the IBM ILOG Optimization Studio [3] software, which has the CP Optimizer solver, necessary for solving the CP models developed. When installing the solver, you will be asked to install the Python libraries cplex and docplex, which will be used in this tutorial.
- Anaconda Python package download link: https://www.anaconda.com/download/success (free and open source)
- CP Optimizer resolver download link: https://academic.ibm.com/ (free for academic purposes - register your academic email > access the Data Science tab > download IBM ILOG CPLEX Optimization Studio)
from docplex.cp.model import CpoModel # Importing the model builder
import docplex.cp.utils_visu as visu # Importing functions to create gantt charts
import numpy as np # Importing the numpy library for array manipulations
Problem parameters
The problem consists of scheduling production in a job shop environment, where each job (or batch) has a processing time on each machine and each job has a specific processing sequence on the machines.
-
Example instance: scheduling 6 jobs ($n=6$) on 6 machines ($m=6$). Each job has a specific operation route. The objective is to minimize the total schedule duration (makespan).
-
Processing times:
| $$p_{ij}$$ | $$J_1$$ | $$J_2$$ | $$J_3$$ | $$J_4$$ | $$J_5$$ | $$J_6$$ |
|---|---|---|---|---|---|---|
| $$M_1$$ | 3 | 8 | 5 | 5 | 3 | 1 |
| $$M_2$$ | 7 | 10 | 9 | 9 | 3 | 3 |
| $$M_3$$ | 6 | 10 | 4 | 5 | 5 | 4 |
| $$M_4$$ | 1 | 5 | 1 | 3 | 4 | 3 |
| $$M_5$$ | 6 | 10 | 8 | 5 | 1 | 9 |
| $$M_6$$ | 3 | 4 | 7 | 8 | 9 | 10 |
- Sequence of machines for each job (operations sequence):**
| $$MAC_{jk}$$ | $$O_1$$ | $$O_2$$ | $$O_3$$ | $$O_4$$ | $$O_5$$ | $$O_6$$ |
|---|---|---|---|---|---|---|
| $$J_1$$ | $$M_3$$ | $$M_1$$ | $$M_2$$ | $$M_4$$ | $$M_6$$ | $$M_5$$ |
| $$J_2$$ | $$M_2$$ | $$M_3$$ | $$M_5$$ | $$M_6$$ | $$M_1$$ | $$M_4$$ |
| $$J_3$$ | $$M_3$$ | $$M_4$$ | $$M_6$$ | $$M_1$$ | $$M_2$$ | $$M_5$$ |
| $$J_4$$ | $$M_2$$ | $$M_1$$ | $$M_3$$ | $$M_4$$ | $$M_5$$ | $$M_6$$ |
| $$J_5$$ | $$M_3$$ | $$M_2$$ | $$M_5$$ | $$M_6$$ | $$M_1$$ | $$M_4$$ |
| $$J_6$$ | $$M_2$$ | $$M_4$$ | $$M_6$$ | $$M_1$$ | $$M_5$$ | $$M_3$$ |
Definition of the problem parameters in arrays from the numpy library in python:
m = 6 # Number of macjhines
n = 6 # Number of jobs
p = np.array(
[[ 3, 8, 5, 5, 3, 1],
[ 7, 10, 9, 9, 3, 3],
[ 6, 10, 4, 5, 5, 4],
[ 1, 5, 1, 3, 4, 3],
[ 6, 10, 8, 5, 1, 9],
[ 3, 4, 7, 8, 9, 10]]) # Processing times
MAC = np.array(
[[2, 0, 1, 3, 5, 4],
[1, 2, 4, 5, 0, 3],
[2, 3, 5, 0, 1, 4],
[1, 0, 2, 3, 4, 5],
[2, 1, 4, 5, 0, 3],
[1, 3, 5, 0, 4, 2]]) # Sequence of machines for each job
Problem statement
- Each machine only processes one job at a time.
- Each job has a specific machine sequence.
- Objective: to minimize the total schedule duration.
Classic job shop with makespan minimization - CP Optimizer model
CP model with CP Optimizer notation:
$$ \begin{align}
\text{min} & \nonumber \\
& \underset{\forall j}{\max} \texttt{ endOf}(x_{[MAC_{jm},j]}) \label{fo_cp_ex_job} \\
\text{st} \nonumber&\\
& \texttt{noOverlap}(\Gamma_i), & \forall i\label{c1_ex_job}\\
& \texttt{endBeforeStart}(x_{[MAC_{jk-1}, j]}, x_{[MAC_{jk}, j]}), & \forall j, k>1 \label{c2_ex_job}\\
& \texttt{interval}\texttt{ } x_{ij},\texttt{ }\texttt{ } \texttt{size}=p_{ij}, &\forall i, j\label{c3_ex_job}\\
& \texttt{sequence}\texttt{ } \Gamma_i,\texttt{ }\texttt{ } \texttt{on} \left [ x_{ij}\right ]_{j \in {1, 2, …, 6}}, & \forall i\label{c4_ex_job}
\end{align}$$
Model construction with docplex package:
mdl = CpoModel()
Interval variable representing the operation of jobs on machines:
$\texttt{interval}\texttt{ } x_{ij},\texttt{ }\texttt{ } \texttt{size}=p_{ij}, \quad \forall i, j$
x = [[mdl.interval_var(size=p[i, j], name=f'M{i}-J{j}') for j in range(n)] for i in range(m)]
Sequence variable representing the order of the jobs processed on each machine:
$\texttt{sequence}\texttt{ } \Gamma_i,\texttt{ }\texttt{ } \texttt{on} \left [ x_{ij}\right ]_{j \in {1, 2, …, 6}}, \quad \forall i$
Gamma = [mdl.sequence_var([x[i][j] for j in range(n)], name=f'M{i}') for i in range(m)]
Minimizing the total schedule duration (makespan):
$\text{min} \texttt{ } \underset{\forall j}{\max} \texttt{ } \texttt{endOf}(x_{[MAC_{jm},j]})$
mdl.add(
mdl.minimize( mdl.max( mdl.end_of(x[MAC[j, m-1]][j]) for j in range(n) ) )
)
Each machine only processes one job at a time:
$\texttt{noOverlap}(\Gamma_i), \quad \forall i$
mdl.add(
mdl.no_overlap( Gamma[i] ) for i in range(m)
)
Each job has a specific machine sequence:
$\texttt{endBeforeStart}(x_{[MAC_{jk-1}, j]}, x_{[MAC_{jk}, j]}), \quad \forall j, k>1$
mdl.add(
mdl.end_before_start(x[MAC[j, k-1]][j], x[MAC[j, k]][j]) for j in range(n) for k in range(m) if k>0 # python index 0
)
Model solving with the CP Optimizer solver:
res = mdl.solve()
! --------------------------------------------------- CP Optimizer 22.1.1.0 --
! Minimization problem - 42 variables, 36 constraints
! Initial process time : 0.01s (0.01s extraction + 0.00s propagation)
! . Log search space : 186.1 (before), 186.1 (after)
! . Memory usage : 510.2 kB (before), 510.2 kB (after)
! Using parallel search with 16 workers.
! ----------------------------------------------------------------------------
! Best Branches Non-fixed W Branch decision
0 42 -
+ New bound is 47
! Using iterative diving.
* 79 73 0.03s 1 (gap is 40.51%)
* 72 145 0.03s 1 (gap is 34.72%)
* 61 217 0.03s 1 (gap is 22.95%)
* 60 331 0.03s 1 (gap is 21.67%)
* 55 708 0.03s 1 (gap is 14.55%)
55 708 1 1 F -
+ New bound is 55 (gap is 0.00%)
! ----------------------------------------------------------------------------
! Search completed, 5 solutions found.
! Best objective : 55 (optimal - effective tol. is 0)
! Best bound : 55
! ----------------------------------------------------------------------------
! Number of branches : 139857
! Number of fails : 6009
! Total memory usage : 7.7 MB (7.6 MB CP Optimizer + 0.1 MB Concert)
! Time spent in solve : 0.03s (0.03s engine + 0.01s extraction)
! Search speed (br. / s) : 6659857.1
! ----------------------------------------------------------------------------
print(f'The schedule has a makespan of: {res.get_objective_value()} u.t.')
The schedule has a makespan of: 55 u.t.
Plotting the solution on a gantt chart:
visu.timeline('Solution for job-shop example instance')
visu.panel('Machines')
for i in range(m):
visu.sequence(name=f'$M_{{{i+1}}}$',
intervals=[(res.get_var_solution(x[i][j]), j, f'$J_{{{j+1}}}$') for j in range(n)])
visu.panel('Jobs')
for j in range(n):
visu.sequence(name=f'$J_{{{j+1}}}$',
intervals=[(res.get_var_solution(x[MAC[j, k]][j]), j, f'$M_{{{MAC[j, k]+1}}}$') for k in range(m)])
visu.show()
References
[1] Pinedo, M. Scheduling: theory, algorithms, and systems. Prentice-Hall. New York. 2016.
[2] Anaconda Software Distribution. Computer software. Vers. 2024.02-1. Anaconda, Feb. 2024.
[3] CPLEX, IBM ILOG. “V22.1.0: User’s Manual for CPLEX.” International Business Machines Corporation 46.53. 2022.
To cite this article (bibtex)
@misc{lrabreu,
author="Abreu, L. R.",
title="Job shop with minimization of total schedule duration (makespan) - solution using the CP Optimizer solve",
year=2024,
url=http://www.opl.ufc.br/en/post/jobshop/,
note = "[Online; accessed 2024-06-20]"
}
Levi R. Abreu
Department of Industrial Engineering
Assistant Professor at Federal University of Ceará with a PhD in Industrial Engineering from University of São Paulo. Interested in operations research, with a particular emphasis on machine scheduling.