Models and algorithms for a flexible manufacturing system

TR Number



Journal Title

Journal ISSN

Volume Title


Virginia Polytechnic Institute and State University


This thesis considers a Flexible Manufacturing System (FMS) comprised of programmable machine tools which are capable of performing multiple operations and which are interconnected by computer-controlled automated material handling equipment. The specific problem addressed is a job-shop type of situation in which at least a given number of each type of job needs to be performed on a given set of machines. The flexibility in the system arises in the form that each job can be performed in a variety of ways with each possible manner of performing it, called an Alternate Routing Combination (ARC), being defined by specifying the number of operations needed and the associated machine sequence. The problem is to select a set of jobs and their associated ARCs to be performed, and schedule their operations on the machines so as to optimize various objectives such as minimizing makespan or maximizing machine utilization, or minimizing total flowtime. This problem is mathematically modeled, and heuristic algorithms are presented along with computational results for the case of minimizing the makespan.