Scheduling of deadlock and failure-prone automated manufacturing systems via hybrid heuristic search

Jian Chao Luo, Ke Yi Xing, Meng Chu Zhou, Xiao Ling Li, Xin Nian Wang

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


This work focuses on the scheduling problem of deadlock and failure-prone automated manufacturing systems, and presents a new scheduling method by combining a robust supervisory control policy and hybrid heuristic search. It aims to minimise makespan, i.e. the completion time of the last part. Based on the extended reach ability graph of the system, it establishes a new heuristic function and two dispatching rules to guide the search process for a schedule. By embedding a robust supervisory control policy into the search process, it develops a polynomial robust dynamic window search algorithm. Failure and repair events of unreliable resources may occur during the execution of a schedule obtained by the proposed algorithm and may make the schedule infeasible. To reduce the influence caused by them and ensure all parts to be finished, this work proposes two event-driven strategies. The first one suspends the execution of the parts requiring failed resources and those to be started until all failed resources are repaired and permits only those parts that have already been processed on working machines to be completed. The second one invokes the proposed algorithm to obtain a new schedule at the vertex generated after a resource failure or repair event and executes the new schedule. Both strategies are effective while the latter performs better at the expense of more computation.

Original languageEnglish (US)
Pages (from-to)3283-3293
Number of pages11
JournalInternational Journal of Production Research
Issue number11
StatePublished - Jun 3 2017

All Science Journal Classification (ASJC) codes

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


  • automated manufacturing system
  • heuristic search
  • rescheduling
  • robust supervisory control policy
  • scheduling


Dive into the research topics of 'Scheduling of deadlock and failure-prone automated manufacturing systems via hybrid heuristic search'. Together they form a unique fingerprint.

Cite this