Petri net modeling and scheduling for cyclic job shops with blocking

Abstract

Cyclic scheduling is an effective scheduling method in the repetitive discrete manufacturing environment. We investigate the scheduling problem for general cyclic job shops with blocking where each machine has an input buffer of finite capacity. We develop Petri net models for the-shops. We propose a sequential buffer control policy that restricts the jobs to enter the input buffer of the next machine in a specified sequence. We show that the scheduling model of a cyclic shop with finite buffers under such a buffer control policy can be transformed into a scheduling model of a cyclic shop with no buffer that can be modeled as a timed marked graph. In addition, we characterize the structural properties for deadlock detection. Finally, we present a mixed integer programming model to find an optimal deadlock-free schedule that minimizes the cycle time. (C) 1998 Elsevier Science Ltd. All rights reserved.