Models and algorithms for job selection, routing, and scheduling in a flexible manufacturing system

ÊThis paper considers a flexible manufacturing system (FMS) comprised of programmable machine tools capable of performing multiple operations and which are interconnected by computer-controlled automated material handling equipment. The specific problem addressed is similar to a job-shop problem in which at least a certain number of each of several types of jobs needs to be performed on a given set of machines. The factor which contributes to the flexibility in the system is that each job can be performed in a variety of ways, with each possible manner of performing it called an ‘alternate routing combination’ (ARC). An ARC for a job specifies the number of operations and the associated machine sequence. The problem is to select a set of jobs to be performed along with their associated ARCs and to schedule their operations on the machines so as to minimize the makespan. This problem is mathematically modelled, and exact and heuristic algorithms are presented together with computational results.