ECLiPSe Code Samples

Jobshop Scheduling

In the Jobshop Scheduling Problem, one is given a set of jobs and a set of resources. Each job consists of a set of activities (or tasks) that must be processed in a given order. Each activity is associated with an integral processing time and a resource on which it must be processed without interruption. A resource can only process one activity at a time. The objective is to find start times for each task such that the makespan (maximum completion time of all activities) is minimised.

A paper that presents algorithms for this problem from a constraint programming point of view, which is appropriate for implementation in ECLiPSe, is the following:

Baptiste, LePape, Nuijten:
Constraint-Based Optimization and Approximation for Job-Shop Scheduling
AAAI SIGMAN workshop on Int.Man.Systems, IJCAI95, Montreal
Available from
An ECLiPSe implementation of the techniques described in the paper can be found in the package jobshop.tgz which contains the following ECLiPSe source files:
The (exact) optimization algorithms from the paper
The approximation algorithms from the paper
fd_jobshop.ecl, ic_jobshop.ecl
A support library for the above, including benchmark data