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

Authors: Sherif A. Fahmy, Tarek Y. ElMekkawy, Subramaniam Balakrishnan

Addresses: Department of Mechanical and Manufacturing Engineering, University of Manitoba, 75A Chancellors Circle, Winnipeg, MB R3T 5V6, Canada. ' Department of Mechanical and Manufacturing Engineering, University of Manitoba, 75A Chancellors Circle, Winnipeg, MB R3T 5V6, Canada. ' Department of Mechanical and Manufacturing Engineering, University of Manitoba, 75A Chancellors Circle, Winnipeg, MB R3T 5V6, Canada

Abstract: 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]

Keywords: deadlock-free scheduling; job shop scheduling; limited buffers; mathematical formulations; mixed integer programming; MIP; insertion algorithm; rank matrix; flexible job shops.

DOI: 10.1504/EJIE.2008.017685

European Journal of Industrial Engineering, 2008 Vol.2 No.3, pp.231 - 252

Published online: 26 Mar 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article