Vehicle scheduling in 2-cycle flexible manufacturing systems

Flexible manufacturing systems (FMSs) have received much attention recently due to their importance for designing modern factories producing small lots of complicated products to specific customer orders. One of the most important problems arising in this context is scheduling parts on machines and, connected with it, an appropriate routing of automated guided vehicles (AGVs) ensuring on-time delivery of parts to particular machines. This paper gives a new approach to model flexible manufacturing systems, motivated by the practical application. The objective is to develop algorithmic procedures that integrate the production schedules with the routing of automated guided vehicles in FMS. The transportation system of the FMS model consists of two cycles, leading to two separate machining centers. These cycles are interconnected, with a common stretch at the inspection and retrieval area, so that the AGVs can switch between the cycles to obtain a higher routing flexibility. In order to keep a complex system simple, a routing strategy is proposed that maintains a steady, regular, cyclic flow of all available vehicles. We develop, by means of a number theoretic concept, vehicle schedules that are collision-free for any cycle sequence. For a given production plan, we then present an efficient dynamic programming approach to check whether or not the required raw material (for machining parts) can be supplied in time to the various numerically controlled machines. This method also solves an open problem in processor scheduling where a set of jobs with a restricted number of distinct processing times is to be scheduled before deadlines on m parallel processors.