THE GENERALIZED SHIFTING BOTTLENECK PROCEDURE

We generalize the Shifting Bottleneck Procedure (SEP), proposed by Ada ms et al. in 1988 for jobshop scheduling, to solve various types of sc heduling problems including openshops, assembly shops and shops where only a partial ordering on operations pertaining to each job or machin e is specified. In its original version, SEP uses a clever definition of the bottleneck value of a machine to iteratively construct a schedu le by solving a number of a certain one machine scheduling problem. We show how the same definition can be extended to measure the bottlenec k value of a job. The optimization procedure then proceeds to iterativ ely fix both job and machine sequences. The outcome of this study is a unified solution procedure for solving various classes of scheduling problems namely openshops, jobshops, assembly shops and shops with par tial precedence constraints. Computational testing on a set of randoml y generated problems demonstrates that performance depends on the dist ribution of the work content of jobs and machines: the higher the coef ficient of variation of the work content, the better the solutions.