VEHICLE SCHEDULING IN 2-CYCLE FLEXIBLE MANUFACTURING SYSTEMS

Flexible manufacturing systems (FMSs) have received much attention rec ently due to their importance for designing modern factories producing small lots of complicated products to specific customer orders. One o f the most important problems arising in this context is scheduling pa rts on machines and, connected with it, an appropriate routing of auto mated guided vehicles (AGVs) ensuring on-time delivery of parts to par ticular machines. This paper general a new approach to model flexible manufacturing systems, motivated by the practical application. The obj ective is to develop algorithmic procedures that integrate the product ion schedules with the routing of automated guided vehicles in FMS. Th e transportation system of the FMS model consists of two cycles, leadi ng to two separate machining centers. These cycles are interconnected, with a common stretch at the inspection and retrieval area, so that t he AGVs can switch between the cycles to obtain a higher routing flexi bility. In order to keep a complex system simple, a routing strategy i s proposed that maintains a steady, regular, cyclic flow of all availa ble vehicles. We develop, by means of a number theoretic concept, vehi cle schedules that are collision-free for any cycle sequence. For a gi ven production plan, we then present an efficient dynamic programming approach to check whether or not the required raw material (for machin ing parts) can be supplied in time to the various NC-machines. This me thod also solves an open problem in processor scheduling where a set o f jobs with a restricted number of distinct processing times is to be scheduled before deadlines on m parallel processors.