The Shifting Bottleneck Procedure for Job Shop Scheduling.
Abstract
This report describes an approximation method for solving the minimum makespan problem of job shop scheduling. It sequences the machines one by one, successively, taking each time the machine identified as a bottleneck among the machines not yet sequenced. Every time after a new machine is sequenced, all previously established sequences are locally reoptimized. Both the bottleneck identification and the local reoptimization procedures are based on repeatedly solving certain one-machine scheduling problems. Besides this straight version of the Shifting Bottleneck Procedure, we have also implemented a version that applies the procedure to the nodes of a truncated search tree. Computational testing shows that our approach yields consistently better results than other procedures discussed in the literature. A high point of our computational testing occurred when the enumerative version of the Shifting Bottleneck Procedure found in a little over five minutes an optimal schedule to a notorious ten machines/ten jobs problem on which many algorithms have been run for hours without finding an optimal solution. Keywords: Heuristics.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1986
- Accession Number
- ADA173110
Entities
People
- Daniel Zawack
- Egon Balas
- Joseph Adams
Organizations
- Carnegie Mellon University