Improved SP-MCTS-based scheduling for multi-constraint hybrid flow shop

Jian Guo, Yaoyao Shi, Zhen Chen, Tao Yu, Bijan Shirinzadeh, Pan Zhao

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)


As a typical non-deterministic polynomial (NP)-hard combinatorial optimization problem, the hybrid flow shop scheduling problem (HFSSP) is known to be a very common layout in real-life manufacturing scenarios. Even though many metaheuristic approaches have been presented for the HFSSP with makespan criterion, there are limitations of the metaheuristic method in accuracy, efficiency, and adaptability. To address this challenge, an improved SP-MCTS (single-player Monte-Carlo tree search)-based scheduling is proposed for the hybrid flow shop to minimize the makespan considering the multi-constraint. Meanwhile, the Markov decision process (MDP) is applied to transform the HFSSP into the problem of shortest time branch path. The improvement of the algorithm includes the selection policy blending standard deviation, the single-branch expansion strategy and the 4-Rule policy simulation. Based on this improved algorithm, it could accurately locate high-potential branches, economize the resource of the computer and quickly optimize the solution. Then, the parameter combination is introduced to trade off the selection and simulation with the intention of balancing the exploitation and exploration in the search process. Finally, through the analysis of the calculated results, the validity of improved SP-MCTS (ISP-MCTS) for solving the benchmarks is proven, and the ISP-MCTS performs better than the other algorithms in solving large-scale problems.

Original languageEnglish
Article number6220
Number of pages19
JournalApplied Sciences
Issue number18
Publication statusPublished - 8 Sep 2020


  • Hybrid flow shop
  • Markov decision process (MDP)
  • Scheduling policy
  • Single-player monte-carlo tree search (SP-MCTS)

Cite this