As recent production facilities are usually operated with unmanned material-handling system, the development of deadlock avoidance algorithm and efficient scheduling method becomes important. Related researches on deadlock avoidance usually focus on real-time control of manufacturing system using deadlock avoidance policy. But few off-line optimization of deadlock-free schedule has been reported. This paper presents the optimization method for deadlock-free scheduling in Job-Shop system without any buffer. The proposed method uses candidate lists of waiting operations, and deadlock avoidance policy.
To verify this approach, simulation results are presented for minimizing makespan in three problems of different types. The simulation results show that the deadlock avoidance policy has different effects on each type of problems. And the proposed LOEM (Last Operation Exclusion Method) reduces makespan and also improves computing time for optimization.