JOBSHOP is a set of C programs for the job-shop scheduling problem.
The codes are based on the paper "A computational study of the job-shop scheduling problem" by David Applegate and William Cook (which appeared in ORSA Journal on Computing, Vol 3 No 2, 1991). The codes were written and tested on a variety of unix workstations in 1990. A set of test problems is included in the gzipped tarfile prob.tar.gz.
***CODES*** Gzipped Tar File: code.tar.gz
DUMBO: An implementation of the naive branch and bound algorithm.
Usage: dumbo [-s schedule_file] [-0] probfile bound
-s: a file containing a list of machines to pre-schedule
-0: machine and job #'s start from 0, not 1
EDGE: An implementation of edge_finder.
Usage: edge [-s schedule_file] [-0] probfile bound
-s: a file containing a list of machines to pre-schedule
-0: machine and job #'s start from 0, not 1
BOTTLE: An implementation of the shifting bottleneck algorithm of Adams, Balas, and Zawack, as described in Applegate and Cook.
Usage bottle: [-n: process_name] [-s] jobshop_file
-s simple run
SLUG: An implementaion of the shuffle heuristic.
Usage slug: [-n integer] [-b integer] [-o integer] [-r] prob_file etimes_file
-n: number of machines to fix
-b: bound on the solution wanted
-o: fix only this machine
-r: reverse the rule for choosing the machines to fix
ONEMACH: An implementation of Carlier's single machine algorithm.
Usage onemach: /* INTERACTIVE */
***FILES***
Source files:
boteval.c dumbo.c edges.c init.c onemach.c printp.c
botmain.c edge.c edgesub.c jobsort.c onemain.c slug.c
bottle.c edgemain.c getprob.c lbound.c preempt.c
Include files:
bottle.h jobdefs.h
Makefile:
Makefile
Last modified: June 18, 2002
William Cook, wcook@isye.gatech.edu