Deadlock-free scheduling of flexible job shops with limited capacity buffers

In this paper, Mixed Integer Programming (MIP) formulations of the deadlock-free job shop scheduling problem are proposed. The presence of buffer space with limited capacity is considered. This research work also proposes a novel operations insertion algorithm based on the rank matrix (or Latin rectangle). In this algorithm, rank matrices are used to generate the schedules and to check for deadlock situations. Finally, an insertion algorithm is proposed to insert transportation operations in the obtained schedules. Performance evaluations of the proposed mathematical models and the proposed algorithm are conducted. The results show that the mathematical models outperform a model presented earlier in the literature. The results also show that the proposed algorithm obtains the same or better solutions when compared to other solution methodologies reported in the literature. [Submitted 31 July 2007; Revised 14 October 2007; Accepted 14 October 2007]