A Knowledge-Based Cuckoo Search Algorithm to Schedule a Flexible Job Shop with Sequencing Flexibility

Zheng Cai Cao, Cheng Ran Lin, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

86 Scopus citations

Abstract

Scheduling of complex manufacturing systems entails complicated constraints such as the mating operational one. Focusing on the real settings, this article considers an extended version of a flexible job shop problem that allows the precedence between the operations to be given by an arbitrary directed acyclic graph instead of a linear order. In order to obtain its reliable and high-performance schedule in a reasonable time, this article contributes a knowledge-based cuckoo search algorithm (KCSA) to the scheduling field. The proposed knowledge base is initially trained off-line on models before operations based on reinforcement learning and hybrid heuristics to store scheduling information and appropriate parameters. In its off-line training phase, the algorithm SARSA is used, for the first time, to build a self-adaptive parameter control scheme of the CS algorithm. In each iteration, the proposed knowledge base selects suitable parameters to ensure the desired diversification and intensification of population. It is then used to generate new solutions by probability sampling in a designed mutation phase. Moreover, it is updated via feedback information from a search process. Its influence on KCSA's performance is investigated and the time complexity of the KCSA is analyzed. The KCSA is validated with the benchmark and randomly generated cases. Various simulation experiments and comparisons between it and several popular methods are performed to validate its effectiveness. Note to Practitioners-Complex manufacturing scheduling problems are usually solved via intelligent optimization algorithms. However, most of them are parameter-sensitive, and thus selecting their proper parameters is highly challenging. On the other hand, it is difficult to ensure their robustness since they heavily rely on some random mechanisms. In order to deal with the above obstacles, we design a knowledge-based intelligent optimization algorithm. In the proposed algorithm, a reinforcement learning algorithm is proposed to self-adjust its parameters to tackle the parameter selection issue. Two probability matrices for machine allocation and operation sequencing are built via hybrid heuristics as a guide for searching a new and efficient assignment scheme. To further improve the performance of our algorithm, a feedback control framework is constructed to ensure the desired state of population. As a result, our algorithm can obtain a high-quality schedule in a reasonable time to fulfill a real-time scheduling purpose. In addition, it possesses high robustness via the proposed feedback control technique. Simulation results show that the knowledge-based cuckoo search algorithm (KCSA) outperforms well some existing algorithms. Hence, it can be readily applied to real manufacturing facility scheduling problems.

Original languageEnglish (US)
Article number8896918
Pages (from-to)56-69
Number of pages14
JournalIEEE Transactions on Automation Science and Engineering
Volume18
Issue number1
DOIs
StatePublished - Jan 2021

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Keywords

  • Cuckoo search (CS) algorithm
  • flexible job shop
  • knowledge base
  • reinforcement learning (RL)
  • scheduling

Fingerprint

Dive into the research topics of 'A Knowledge-Based Cuckoo Search Algorithm to Schedule a Flexible Job Shop with Sequencing Flexibility'. Together they form a unique fingerprint.

Cite this