Member-only story
Expansion on the Job Shop Problem
Contents
What’s the job shop problem?
It’s an optimisation problem that involves scheduling multiple jobs on multiple machines. Each job has a sequence of tasks that must be executed in a specific order, each task has a specific duration and can be processed on a specific machine. The problem is to find the optimal schedule for all jobs that minimizes the length of the schedule (makespan).
We can break down this problem into variables and constraints, along with an objective function and then use the constraint programming solver (i.e. a SAT solver) to find the optimal solution, in our case, minimise the makespan. In this example we will be using Google’s OR-Tools library.
The constraints provided in the original problem are as follows:
- No task for a job can be started until the previous task for that job is completed.
- A machine can only work on one task at a time.
- A task, once started, must run to completion.
We can represent each job as a list that consists of tasks labelled by a pair of numbers (m,p) where m is the number of the machine and p is the processing time…
