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: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:
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
- 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