The Job Shop Scheduling Problem
Description
An n by m JSSP is defined by n jobs and m machines. Each job consists of a chain of m tasks. Each machine can handle at most one task at a time. Each task needs to be processed during an uninterrupted period of a given length on a given machine. The goal is to find a schedule, that is, an allocation of the tasks to time intervals to machines, that has minimal length. More on the JSSP...
Business and Industrial Applications
This problem has a lot of business and industrial applications.
Data
Data provided in the problem definition - Java file (11kb) [view] - is taken from http://mscmga.ms.ic.ac.uk/jeb/pub/.
Modelling & Solving
We have defined a very simple constraint model - Java file (11kb) [view] - using Koalog Constraint SolverTM scheduling API.
To solve the problem, we use a basic solver - Java file (6kb) [view] - and minimizer - Java file (2kb) [view].
Results
Although very simple, our model allows us to solve the very hard problem MT10 (still open before 1989) rather easily. Starting with a first solution of cost 1219 (because we don't set any good upper bound), we reach the optimum 930 and prove the optimality in 11 minutes and 293 kilobacktracks. The proof of optimality itself (using 929 as an upper bound) takes a bit more than 2 minutes and 39 kilobacktracks.
These results are very promising since we don't use any complex heuristic.