Scheduling problems are concerned with determining a plan for the execution of a given set of tasks. Addressing these challenges effectively is crucial in the industry, as it allows to reduce cost without compromising quality. One classical scheduling problem is the Job-Shop, in which $n$ jobs must be completed using $m$ machines. Each job is composed of multiple tasks of varying execution time, which must be processed in a given order and on specific machines. The aim is to find a schedule that minimizes the makespan (total length of the process).
Because of its highly combinatorial nature, Constraint Programming (CP) is particularly interesting for solving this problem. In the following we describe the JobShop problem and present how to state and solve it using the CP solver Artelys Kalis.
A problem instance $P = (M,T,J)$ consists of:
Each job $i \in J$ is composed of a subset $T_i$ of $\tau_i$ tasks. Hence a job can be represented as a sequence $\{task(i,1), task(i,2),...,task(i,\tau_i)\}$.
Each $task(i,j)$ is associated with a machine $m_{ij} \in M$, and has a duration $d_{ij}$.
$t_{ij}$ = starting time of $task(i,j)$, $\forall i \in J, \forall j \in T_i$.
We seek a schedule that minimizes the makespan, that is the total duration between the start of the first task to be processed across all machines, and the end of the last one.
The makespan, often called $C_{max}$, can be defined as the maximum completion time (starting time plus duration), across all tasks:
$$C_{max} = \max\limits_{i,j}\ (t_{ij}+d_{ij})$$Starting times are non negative and we set a time horizon $MaxTime$. For instance, this horizon could represent one working day.
$t_{i,j} \geq 0, \quad \forall i \in J, \forall j \in T_i $
$t_{i,j} + d_{i,j} \leq MaxTime, \quad \forall i \in J, \forall j \in T_i$
Given two consecutive tasks in the same job, the first one must be completed before the next one can start. Those are called conjunctive constraints.
$t_{i,j} + d_{i,j} \leq t_{i,j+1}, \quad \forall i \in J, \forall j \in T_i$
A machine can process only one task at a time. As a result, if $task(i,j)$ and $task(k,l)$ are associated with the same machine ($m_{ij}$ = $m_{kl}$), then one of them must be completed before the machine is available again to process the other one. Those are called disjunctive constraints:
$t_{i,j} + d_{i,j} \leq t_{k,l} \quad$ or $\quad t_{k,l} + d_{k,l} \leq t_{i,j} \quad \forall i,k \in J, \forall j \in T_i, \forall l \in T_k$ such that $m_{ij} = m_{kl}$
Let us start by taking a look at the data.
file = open('jobshop33.dat', 'r')
data = file.read()
print(data)
# instance 3 jobs, 3 machines 3 3 2 4 0 1 1 2 0 2 1 2 2 5 0 2 1 4 2 2
The first line represents the number of jobs and the number of machines. Here 3 jobs are to be processed on 3 machines.
Each following line represents a job as a sequence of tasks. Each task is represented by its corresponding pair of machine and duration $(m_{ij},d_{ij})$. Here the first task of the first job must be processed on machine 2, and its completion lasts 1 unit of time. The second task must be processed on machine 0, for 3 units of time, and so on.
Then we parse this data:
# Parse data
lines = data.split('\n')
# Remove unnecessary comments
for line in lines:
if line.startswith("#"):
lines.remove(line)
# Parse first line with machines nb and jobs nb
firstLine = lines[0].split()
nb_jobs = int(firstLine[0])
nb_machines = int(firstLine[1])
# Parse each job
# For each job, parse each pair of numbers (m, d) where m is the machine id the task must be processed on
# and d is the duration of the task
machine_used = [[]]*nb_jobs
task_duration = [[]]*nb_jobs
for j in range(nb_jobs):
line = lines[j+1]
parts = line.split()
nb_tasks = len(parts)/2
machine_used[j] = [0]*nb_tasks
task_duration[j] = [0]*nb_tasks
for t in range(nb_tasks):
machine_used[j][t] = int(parts[2*t])
task_duration[j][t] = int(parts[2*t+1])
In each line, odd indices correspond to machines, and even indices to processing times. We store this information in nested lists machine_used
and task_duration
.
Here are the machines to use and task durations for each job:
for j in range(nb_jobs):
print("Job " + str(j) + ":")
print("\t m " + str(machine_used[j]))
print("\t d " + str(task_duration[j]))
Job 0: m [2, 0, 1] d [4, 1, 2] Job 1: m [0, 1, 2] d [2, 2, 5] Job 2: m [0, 1, 2] d [2, 4, 2]
import sys, os
from kalis import *
In Artelys Kalis, problem statement and solving are carried out inside a KSession
object. The first thing to do is to create it.
# Creation of the Kalis session
session = KSession()
Our problem comprises variables, constraints, and might have solutions after search. In Artelys Kalis KProblem
objects hold the modeling entities and solution objects.
# Creation of the problem in this session
problem = KProblem(session, "JobShop");
We initialize a KProblem
object variable called problem
. "JobShop" is the internal name of the problem.
Note how the first parameter set our KProblem
into our KSession
. Everytime we will initialize a Kalis object, the syntax will be similar.
Since scheduling problems are often addressed with Constraint Programming, Kalis implements user-friendly classes specifically designed to facilitate their statement. Tasks and resources (machines in our example), are gathered into a schedule.
s = KSchedule(problem, "JobShop Schedule", 0, 10000);
Here we define a KSchedule
object called s
into our Kproblem
. The third and fourth parameters correspond to the time window involved in the first constraint. Our timeline starts at 0 and our horizon is 10000 units of time. "JobShop Schedule" is the internal name of s
.
We move on and define our machines and tasks into this schedule s
. We use KUnaryResource
objects, which represent resources that can process at most one task at a time.
# Create resource list
machine = [KUnaryResource(s, "M%i" % m) for m in range(nb_machines)]
For the tasks, we use the constructor of KTask
.
# Create task list
task = {
(j, t): KTask(s, "J%iT%i" % (j,t), 0, s.getTimeMax(), task_duration[j][t], task_duration[j][t])
for j in range(nb_jobs)
for t in range(len(task_duration[j]))
}
Our tasks are set to last between 0 unit of time and s.getTimeMax()
, the horizon of our schedule, which we set at 10000 above. Last parameters state the minimum and maximum durations of our tasks. In our example each task has a specific, inflexible duration. Hence both parameters are set at task_duration[j][t]
.
Then we use the requires()
method of the class KTask
in order to associate each task to its corresponding machine.
# Post resource usage for each task
for j in range(nb_jobs):
for t in range(len(machine_used[j])):
task[j, t].requires(machine[machine_used[j][t]],1)
This method takes two input parameters : the resource to associate, and the amount of resource capacity our task requires. For the Job-Shop problem, all machines are unary resources, e.g. have a capacity of 1, and each task requires this unary capacity.
Finally we specify that tasks are ordered for a given job using the startsAfter()
method.
# Post precedence constraints between the tasks of a same job
for j in range(nb_jobs):
for t in range(1, len(task_duration[j])):
task[j, t].startsAfter(task[j, t-1])
And that's it! We do not need to explictly state disjunctive constraints because we implemented resources as KUnaryResources
and, consequently, our machines will naturally process only one task at a time (Kalis implements these constraints internally). Also note that the variables are implicitly declared in the KSchedule
, which will assign a starting time to each KTask
.
Once the problem has been fully built, we call the optimize()
method for Kalis to solve the problem. For a scheduling problem, this method minimizes the makespan by default.
s.optimize()
2
We might also want to optimize another objective than the makespan. If so, before calling optimize()
, we would use the setObjective()
method to define an objective function. Then, the setSense()
method to specify the sense of optimization. If we wish to minimize : setSense(KProblem::Minimize);
.
As mentioned earlier, solutions are comprised in ourKProblem
, which holds the modeling entities. We combine the getProblem()
and getSolution()
method on our KSchedule
object to obtain the solution.
sol = s.getProblem().getSolution()
sol
is a KSolution
object. It contains the value of each decision variable and information about the resolution such as computation time or number of nodes explored in the search-tree.
The code below displays the solution:
# Get schedule per machine
machine_sol = [[]]*nb_machines
for m in range(nb_machines):
machine_sol[m] = []
for j in range(nb_jobs):
for t in range(len(task_duration[j])):
if machine_used[j][t] == m:
machine_sol[m].append(('Task(' + str(j) + ',' + str(t) + ')',[sol.getValue(task[j,t].getStartDateVar()),
sol.getValue(task[j,t].getEndDateVar())]))
print "Solution:"
for m in range(nb_machines):
machine_sol[m].sort(key=lambda x: x[1])
print "Machine " + str(m) + ": " + str(machine_sol[m])
print "\nMakespan: " + str(sol.getValue(s.getMakeSpan())) + "\n"
Solution: Machine 0: [('Task(1,0)', [0, 2]), ('Task(2,0)', [2, 4]), ('Task(0,1)', [4, 5])] Machine 1: [('Task(1,1)', [2, 4]), ('Task(2,1)', [4, 8]), ('Task(0,2)', [8, 10])] Machine 2: [('Task(0,0)', [0, 4]), ('Task(1,2)', [4, 9]), ('Task(2,2)', [9, 11])] Makespan: 11
We get the schedule of each machine: sequence of tasks and time intervals.
Finally, here is the timeline for the optimal schedule, considering that one unit of time corresponds to one hour:
import datetime as dt
import plotly.offline as offline
import plotly.figure_factory as ff
start_date = dt.datetime(2018, 1, 1, 8, 0, 0)
df = []
for j in range(nb_jobs):
for t in range(len(task_duration[j])):
df.append(dict(Task='Machine '+str(machine_used[j][t]),
Start= start_date+dt.timedelta(hours=sol.getValue(task[j,t].getStartDateVar())),
Finish= start_date+dt.timedelta(hours=sol.getValue(task[j,t].getEndDateVar())),
Resource='Job '+str(j)))
# Display the Gantt chart
figure = ff.create_gantt(df, title = 'Optimal Schedule', index_col='Resource', show_colorbar=True, group_tasks=True)
offline.init_notebook_mode()
offline.iplot(figure, filename='gantt-jobshop')
We can finally free the memory by deleting the Kalis session.
del session
Below you can find the entire program described in that Notebook running on a larger instance of this problem. The resulting gantt chart is the timeline obtained for 10 jobs and 10 machines!
import sys, os
from kalis import *
import datetime as dt
import plotly.offline as offline
import plotly.figure_factory as ff
#Load data
file = open('abz6.dat', 'r')
data = file.read()
print(data)
# Parse data
lines = data.split('\n')
# Remove unnecessary comments
for line in lines:
if line.startswith("#"):
lines.remove(line)
# Parse first line with machines nb and jobs nb
firstLine = lines[0].split()
nb_jobs = int(firstLine[0])
nb_machines = int(firstLine[1])
# Parse each job
# For each job, parse each pair of numbers (m, d) where m is the machine id the task must be processed on
# and d is the duration of the task
machine_used = [[]]*nb_jobs
task_duration = [[]]*nb_jobs
for j in range(nb_jobs):
line = lines[j+1]
parts = line.split()
nb_tasks = len(parts)/2
machine_used[j] = [0]*nb_tasks
task_duration[j] = [0]*nb_tasks
for t in range(nb_tasks):
machine_used[j][t] = int(parts[2*t])
task_duration[j][t] = int(parts[2*t+1])
# Display parsed data
for j in range(nb_jobs):
print("Job " + str(j) + ":")
print("\t m " + str(machine_used[j]))
print("\t d " + str(task_duration[j]))
# Creation of the Kalis session
session = KSession()
# Creation of the problem in this session
problem = KProblem(session, "JobShop");
s = KSchedule(problem, "JobShop Schedule", 0, 10000);
# Create resource list
machine = [KUnaryResource(s, "M%i" % m) for m in range(nb_machines)]
# Create task list
task = {
(j, t): KTask(s, "J%iT%i" % (j,t), 0, s.getTimeMax(), task_duration[j][t], task_duration[j][t])
for j in range(nb_jobs)
for t in range(len(task_duration[j]))
}
# Post resource usage for each task
for j in range(nb_jobs):
for t in range(len(machine_used[j])):
task[j, t].requires(machine[machine_used[j][t]],1)
# Post precedence constraints between the tasks of a same job
for j in range(nb_jobs):
for t in range(1, len(task_duration[j])):
task[j, t].startsAfter(task[j, t-1])
s.optimize()
sol = s.getProblem().getSolution()
# Get schedule per machine
machine_sol = [[]]*nb_machines
for m in range(nb_machines):
machine_sol[m] = []
for j in range(nb_jobs):
for t in range(len(task_duration[j])):
if machine_used[j][t] == m:
machine_sol[m].append(('Task(' + str(j) + ',' + str(t) + ')',[sol.getValue(task[j,t].getStartDateVar()),
sol.getValue(task[j,t].getEndDateVar())]))
print "Solution:"
for m in range(nb_machines):
machine_sol[m].sort(key=lambda x: x[1])
print "Machine " + str(m) + ": " + str(machine_sol[m])
print "\nMakespan: " + str(sol.getValue(s.getMakeSpan())) + "\n"
# instance abz6: Adams, and Zawack 10x10 instance (Table 1, instance 6) 10 10 7 62 8 24 5 25 3 84 4 47 6 38 2 82 0 93 9 24 1 66 5 47 2 97 8 92 9 22 1 93 4 29 7 56 3 80 0 78 6 67 1 45 7 46 6 22 2 26 9 38 0 69 4 40 3 33 8 75 5 96 4 85 8 76 5 68 9 88 3 36 6 75 2 56 1 35 0 77 7 85 8 60 9 20 7 25 3 63 4 81 0 52 1 30 5 98 6 54 2 86 3 87 9 73 5 51 2 95 4 65 1 86 6 22 8 58 0 80 7 65 5 81 2 53 7 57 6 71 9 81 0 43 4 26 8 54 3 58 1 69 4 20 6 86 5 21 8 79 9 62 2 34 0 27 1 81 7 30 3 46 9 68 6 66 5 98 8 86 7 66 0 56 3 82 1 95 4 47 2 78 0 30 3 50 7 34 2 58 1 77 5 34 8 84 4 40 9 46 6 44 Job 0: m [7, 8, 5, 3, 4, 6, 2, 0, 9, 1] d [62, 24, 25, 84, 47, 38, 82, 93, 24, 66] Job 1: m [5, 2, 8, 9, 1, 4, 7, 3, 0, 6] d [47, 97, 92, 22, 93, 29, 56, 80, 78, 67] Job 2: m [1, 7, 6, 2, 9, 0, 4, 3, 8, 5] d [45, 46, 22, 26, 38, 69, 40, 33, 75, 96] Job 3: m [4, 8, 5, 9, 3, 6, 2, 1, 0, 7] d [85, 76, 68, 88, 36, 75, 56, 35, 77, 85] Job 4: m [8, 9, 7, 3, 4, 0, 1, 5, 6, 2] d [60, 20, 25, 63, 81, 52, 30, 98, 54, 86] Job 5: m [3, 9, 5, 2, 4, 1, 6, 8, 0, 7] d [87, 73, 51, 95, 65, 86, 22, 58, 80, 65] Job 6: m [5, 2, 7, 6, 9, 0, 4, 8, 3, 1] d [81, 53, 57, 71, 81, 43, 26, 54, 58, 69] Job 7: m [4, 6, 5, 8, 9, 2, 0, 1, 7, 3] d [20, 86, 21, 79, 62, 34, 27, 81, 30, 46] Job 8: m [9, 6, 5, 8, 7, 0, 3, 1, 4, 2] d [68, 66, 98, 86, 66, 56, 82, 95, 47, 78] Job 9: m [0, 3, 7, 2, 1, 5, 8, 4, 9, 6] d [30, 50, 34, 58, 77, 34, 84, 40, 46, 44] Solution: Machine 0: [('Task(9,0)', [0, 30]), ('Task(4,5)', [249, 301]), ('Task(2,5)', [301, 370]), ('Task(0,7)', [419, 512]), ('Task(7,6)', [512, 539]), ('Task(8,5)', [544, 600]), ('Task(6,5)', [600, 643]), ('Task(3,8)', [643, 720]), ('Task(1,8)', [720, 798]), ('Task(5,8)', [798, 878])] Machine 1: [('Task(2,0)', [0, 45]), ('Task(1,4)', [295, 388]), ('Task(5,5)', [388, 474]), ('Task(9,4)', [477, 554]), ('Task(4,6)', [554, 584]), ('Task(3,7)', [595, 630]), ('Task(7,7)', [630, 711]), ('Task(8,7)', [711, 806]), ('Task(0,9)', [806, 872]), ('Task(6,9)', [872, 941])] Machine 2: [('Task(1,1)', [47, 144]), ('Task(6,1)', [144, 197]), ('Task(2,3)', [197, 223]), ('Task(5,3)', [225, 320]), ('Task(0,6)', [337, 419]), ('Task(9,3)', [419, 477]), ('Task(7,5)', [477, 511]), ('Task(3,6)', [539, 595]), ('Task(4,9)', [740, 826]), ('Task(8,9)', [853, 931])] Machine 3: [('Task(5,0)', [0, 87]), ('Task(4,3)', [105, 168]), ('Task(0,3)', [168, 252]), ('Task(9,1)', [252, 302]), ('Task(3,4)', [383, 419]), ('Task(2,7)', [457, 490]), ('Task(1,7)', [490, 570]), ('Task(8,6)', [600, 682]), ('Task(7,9)', [741, 787]), ('Task(6,8)', [792, 850])] Machine 4: [('Task(7,0)', [0, 20]), ('Task(3,0)', [20, 105]), ('Task(4,4)', [168, 249]), ('Task(0,4)', [252, 299]), ('Task(5,4)', [320, 385]), ('Task(1,5)', [388, 417]), ('Task(2,6)', [417, 457]), ('Task(9,7)', [672, 712]), ('Task(6,6)', [712, 738]), ('Task(8,8)', [806, 853])] Machine 5: [('Task(1,0)', [0, 47]), ('Task(6,0)', [47, 128]), ('Task(0,2)', [128, 153]), ('Task(7,2)', [153, 174]), ('Task(5,2)', [174, 225]), ('Task(3,2)', [225, 293]), ('Task(8,2)', [294, 392]), ('Task(9,5)', [554, 588]), ('Task(4,7)', [588, 686]), ('Task(2,9)', [686, 782])] Machine 6: [('Task(7,1)', [20, 106]), ('Task(2,2)', [151, 173]), ('Task(8,1)', [228, 294]), ('Task(0,5)', [299, 337]), ('Task(6,3)', [393, 464]), ('Task(3,5)', [464, 539]), ('Task(5,6)', [539, 561]), ('Task(4,8)', [686, 740]), ('Task(9,9)', [758, 802]), ('Task(1,9)', [802, 869])] Machine 7: [('Task(0,0)', [0, 62]), ('Task(4,2)', [80, 105]), ('Task(2,1)', [105, 151]), ('Task(9,2)', [302, 336]), ('Task(6,2)', [336, 393]), ('Task(1,6)', [417, 473]), ('Task(8,4)', [478, 544]), ('Task(7,8)', [711, 741]), ('Task(3,9)', [741, 826]), ('Task(5,9)', [878, 943])] Machine 8: [('Task(4,0)', [0, 60]), ('Task(0,1)', [62, 86]), ('Task(3,1)', [105, 181]), ('Task(1,2)', [181, 273]), ('Task(7,3)', [273, 352]), ('Task(8,3)', [392, 478]), ('Task(2,8)', [490, 565]), ('Task(9,6)', [588, 672]), ('Task(5,7)', [672, 730]), ('Task(6,7)', [738, 792])] Machine 9: [('Task(4,1)', [60, 80]), ('Task(5,1)', [87, 160]), ('Task(8,0)', [160, 228]), ('Task(2,4)', [228, 266]), ('Task(1,3)', [273, 295]), ('Task(3,3)', [295, 383]), ('Task(7,4)', [383, 445]), ('Task(6,4)', [464, 545]), ('Task(9,8)', [712, 758]), ('Task(0,8)', [758, 782])] Makespan: 943
start_date = dt.datetime(2018, 1, 1, 8, 0, 0)
# Display the Gantt chart
df = []
for j in range(nb_jobs):
for t in range(len(task_duration[j])):
df.append(dict(Task='Machine '+str(machine_used[j][t]),
Start= start_date+dt.timedelta(hours=sol.getValue(task[j,t].getStartDateVar())),
Finish= start_date+dt.timedelta(hours=sol.getValue(task[j,t].getEndDateVar())),
Resource='Job '+str(j)))
figure = ff.create_gantt(df, title = 'Optimal Schedule', index_col='Resource', show_colorbar=True, group_tasks=True)
offline.init_notebook_mode()
offline.iplot(figure, filename='gantt-jobshop')
del session