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 http://citeseer.ist.psu.edu/499726.html
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:
bln_exact.ecl
The (exact) optimization algorithms from the paper
bln_approx.ecl
The approximation algorithms from the paper
fd_jobshop.ecl, ic_jobshop.ecl
A support library for the above, including benchmark data