Real time scheduling problems in a general flexible manufacturing system.

Abstract

This dissertation addresses three problems which arise during the real-time scheduling of a flexible manufacturing system (FMS) which produces a large variety of part types in relatively small volumes. Two of these problems, the Workcenter Scheduling Problem (WSP) and the Shop Scheduling Problem (SSP) have not been directly addressed by any researcher in the past. While the third problem, the Multiple-Machine Tardiness Problem (MTP) is well-researched, we propose a different solution approach. WSP and MTP consider the objective of minimizing mean tardiness in a dynamic system. The proposed solution approach to both problems requires decomposing the dynamic problem into a series of static problems, and implementing the solutions to these static problems on a rolling basis. WSP considers a single-machine system in which jobs are processed in batches, and a constant changeover time is incurred while switching from one part type to another. We show the static WSP to be NP-complete, and present some characteristics of the optimal sequence. An optimum-seeking and two heuristic solution procedures are developed for this problem. Computational studies indicate the effectiveness of these procedures. MTP addresses a multiple-machine system with r and om material flows. For the static problem, we propose an optimum-seeking method, and a heuristic procedure which generates an active schedule for the entire FMS at each instance. Experimental results reveal that this heuristic method can yield substantial improvement over dispatching rules studied in prior research, for both static and dynamic problems. SSP deals with a static system in which the primary objective is to minimize mean tardiness and the secondary objective is to maximize the sum of job release times. A heuristic solution method is proposed which decomposes SSP into two subproblems. These subproblems address the two objectives independently. Computational studies show the relative merit of addressing the dual-objective problem and the effectiveness of the suggested solution procedure under various test scenarios.