Simultaneous scheduling of machines and the material handling system in a flexible manufacturing system

Abstract

The scheduling of material handling system is a crital issue in a Flexible Manufacturing System (FMS), although it has little importance in a job shop. The purpose of this dissertation is to exploit the interactions between the machine scheduling and the scheduling of the material handling system in an FMS and to integrate them by addressing them simultaneously. In the FMS under consideration, the material transfer between machines is done by a number of identical Automated Guided Vehicles (AGVs). Upon completing a loaded trip the AGV is designated to its next pick-up station. Therefore, the travel times of the empty trips depend on the ending and the starting points of the successive loaded trips assigned to a vehicle.This concept of sequence-dependent travel times increases the difficulty of the problem. As a first step, the combined machine and material handling system scheduling problem is formulated as a nonlinear mixed integer programming model which turned out to be of intractable size for real-world problems. Then, the problem is decomposed into two subproblems, one having the characteristics of the machine scheduling problem while the other is a vehicle scheduling problem and an iterative solution procedure is developed. At each iteration, a new machine schedule, generated by a heuristic procedure, is investigated for its feasibility to the vehicle scheduling subproblem. To do this, the operation completion times obtained from the, machine schedule are used to construct "time windows" for each material handling trip, and the second subproblem is handled as a "sliding time window" problem. The procedure is numerically tested on a number of example problems.