{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solving the JobShop scheduling problem using Artelys Kalis"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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).\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Description of the problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Parameters\n",
"\n",
"A problem instance $P = (M,T,J)$ consists of:\n",
"\n",
"- A set $M$ of machines\n",
"- A set $T$ of tasks\n",
"- A set $J$ of jobs.\n",
"\n",
"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)\\}$.\n",
"\n",
"Each $task(i,j)$ is associated with a machine $m_{ij} \\in M$, and has a duration $d_{ij}$.\n",
"\n",
"\n",
"### Variables\n",
"\n",
"$t_{ij}$ = starting time of $task(i,j)$, $\\forall i \\in J, \\forall j \\in T_i$.\n",
"\n",
"### Objective\n",
"\n",
"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.\n",
"\n",
"The makespan, often called $C_{max}$, can be defined as the maximum completion time (starting time plus duration), across all tasks:\n",
"\n",
"$$C_{max} = \\max\\limits_{i,j}\\ (t_{ij}+d_{ij})$$\n",
"\n",
"### Constraints\n",
"\n",
"Starting times are non negative and we set a time horizon $MaxTime$. For instance, this horizon could represent one working day.\n",
"\n",
"$t_{i,j} \\geq 0, \\quad \\forall i \\in J, \\forall j \\in T_i $\n",
"\n",
"$t_{i,j} + d_{i,j} \\leq MaxTime, \\quad \\forall i \\in J, \\forall j \\in T_i$\n",
"\n",
"\n",
"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*.\n",
"\n",
"$t_{i,j} + d_{i,j} \\leq t_{i,j+1}, \\quad \\forall i \\in J, \\forall j \\in T_i$\n",
"\n",
"\n",
"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*:\n",
"\n",
"$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}$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Implementation using the Python API"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Model data"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let us start by taking a look at the data."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"# instance 3 jobs, 3 machines\n",
"3 3\n",
"2 4 0 1 1 2\n",
"0 2 1 2 2 5\n",
"0 2 1 4 2 2\n",
"\n"
]
}
],
"source": [
"file = open('jobshop33.dat', 'r')\n",
"\n",
"data = file.read()\n",
"\n",
"print(data)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The first line represents the number of jobs and the number of machines. Here 3 jobs are to be processed on 3 machines.\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Then we parse this data:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"# Parse data\n",
"lines = data.split('\\n')\n",
"\n",
"# Remove unnecessary comments\n",
"for line in lines:\n",
" if line.startswith(\"#\"):\n",
" lines.remove(line)\n",
" \n",
"# Parse first line with machines nb and jobs nb\n",
"firstLine = lines[0].split()\n",
"nb_jobs = int(firstLine[0])\n",
"nb_machines = int(firstLine[1])\n",
"\n",
"# Parse each job\n",
"# For each job, parse each pair of numbers (m, d) where m is the machine id the task must be processed on\n",
"# and d is the duration of the task\n",
"machine_used = [[]]*nb_jobs\n",
"task_duration = [[]]*nb_jobs\n",
"for j in range(nb_jobs):\n",
" line = lines[j+1]\n",
" parts = line.split()\n",
" nb_tasks = len(parts)/2\n",
" machine_used[j] = [0]*nb_tasks\n",
" task_duration[j] = [0]*nb_tasks\n",
" for t in range(nb_tasks):\n",
" machine_used[j][t] = int(parts[2*t])\n",
" task_duration[j][t] = int(parts[2*t+1])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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`.\n",
"\n",
"Here are the machines to use and task durations for each job:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"hideCode": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Job 0:\n",
"\t m [2, 0, 1]\n",
"\t d [4, 1, 2]\n",
"Job 1:\n",
"\t m [0, 1, 2]\n",
"\t d [2, 2, 5]\n",
"Job 2:\n",
"\t m [0, 1, 2]\n",
"\t d [2, 4, 2]\n"
]
}
],
"source": [
"for j in range(nb_jobs):\n",
" print(\"Job \" + str(j) + \":\")\n",
" print(\"\\t m \" + str(machine_used[j]))\n",
" print(\"\\t d \" + str(task_duration[j]))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### The Kalis Environment"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"hideCode": false,
"hideOutput": false,
"hidePrompt": false
},
"outputs": [],
"source": [
"import sys, os\n",
"\n",
"from kalis import *"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### The KSession Class\n",
"\n",
"In Artelys Kalis, problem statement and solving are carried out inside a `KSession` object. The first thing to do is to create it."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"# Creation of the Kalis session\n",
"session = KSession()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Building the model\n",
"\n",
"Our problem comprises *variables*, *constraints*, and might have *solutions* after search. In Artelys Kalis `KProblem` objects hold the modeling entities and solution objects. "
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"# Creation of the problem in this session\n",
"problem = KProblem(session, \"JobShop\");"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We initialize a `KProblem` object variable called `problem`. \"JobShop\" is the internal name of the problem.\n",
"\n",
"Note how the first parameter set our `KProblem` into our `KSession`. Everytime we will initialize a Kalis object, the syntax will be similar.\n",
"\n",
"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."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"s = KSchedule(problem, \"JobShop Schedule\", 0, 10000);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"# Create resource list\n",
"machine = [KUnaryResource(s, \"M%i\" % m) for m in range(nb_machines)]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For the tasks, we use the constructor of `KTask`."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"# Create task list\n",
"task = {\n",
" (j, t): KTask(s, \"J%iT%i\" % (j,t), 0, s.getTimeMax(), task_duration[j][t], task_duration[j][t])\n",
" for j in range(nb_jobs)\n",
" for t in range(len(task_duration[j]))\n",
" }"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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]`.\n",
"\n",
"Then we use the `requires()` method of the class `KTask` in order to associate each task to its corresponding machine. "
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"# Post resource usage for each task\n",
"for j in range(nb_jobs):\n",
" for t in range(len(machine_used[j])):\n",
" task[j, t].requires(machine[machine_used[j][t]],1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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.\n",
"\n",
"Finally we specify that tasks are ordered for a given job using the `startsAfter()` method."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"# Post precedence constraints between the tasks of a same job\n",
"for j in range(nb_jobs): \n",
" for t in range(1, len(task_duration[j])):\n",
" task[j, t].startsAfter(task[j, t-1])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Solving the problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"hideOutput": false,
"hidePrompt": false,
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"s.optimize()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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);`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As mentioned earlier, solutions are comprised in our`KProblem`, which holds the modeling entities. We combine the `getProblem()` and `getSolution()` method on our `KSchedule` object to obtain the solution."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"sol = s.getProblem().getSolution()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The code below displays the solution:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"hideOutput": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Solution:\n",
"Machine 0: [('Task(1,0)', [0, 2]), ('Task(2,0)', [2, 4]), ('Task(0,1)', [4, 5])]\n",
"Machine 1: [('Task(1,1)', [2, 4]), ('Task(2,1)', [4, 8]), ('Task(0,2)', [8, 10])]\n",
"Machine 2: [('Task(0,0)', [0, 4]), ('Task(1,2)', [4, 9]), ('Task(2,2)', [9, 11])]\n",
"\n",
"Makespan: 11\n",
"\n"
]
}
],
"source": [
"# Get schedule per machine\n",
"machine_sol = [[]]*nb_machines\n",
"for m in range(nb_machines):\n",
" machine_sol[m] = []\n",
" for j in range(nb_jobs):\n",
" for t in range(len(task_duration[j])):\n",
" if machine_used[j][t] == m:\n",
" machine_sol[m].append(('Task(' + str(j) + ',' + str(t) + ')',[sol.getValue(task[j,t].getStartDateVar()),\n",
" sol.getValue(task[j,t].getEndDateVar())]))\n",
"\n",
"\n",
"print \"Solution:\"\n",
"for m in range(nb_machines):\n",
" machine_sol[m].sort(key=lambda x: x[1])\n",
" print \"Machine \" + str(m) + \": \" + str(machine_sol[m]) \n",
" \n",
"print \"\\nMakespan: \" + str(sol.getValue(s.getMakeSpan())) + \"\\n\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We get the schedule of each machine: sequence of tasks and time intervals.\n",
"\n",
"Finally, here is the timeline for the optimal schedule, considering that one unit of time corresponds to one hour:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"hideCode": false,
"hidePrompt": false
},
"outputs": [
{
"data": {
"text/html": [
"