An improved simulated annealing algorithm based on residual network for permutation flow shop scheduling

  • PDF / 880,957 Bytes
  • 11 Pages / 595.276 x 790.866 pts Page_size
  • 97 Downloads / 216 Views

DOWNLOAD

REPORT


ORIGINAL ARTICLE

An improved simulated annealing algorithm based on residual network for permutation flow shop scheduling Yang Li1 · Cuiyu Wang1 · Liang Gao1 · Yiguo Song2 · Xinyu Li1 Received: 30 June 2020 / Accepted: 18 September 2020 © The Author(s) 2020

Abstract The permutation flow shop scheduling problem (PFSP), which is one of the most important scheduling types, is widespread in the modern industries. With the increase of scheduling scale, the difficulty and computation time of solving the problem will increase exponentially. Adding the knowledge to intelligent algorithms is a good way to solve the complex and difficult scheduling problems in reasonable time. To deal with the complex PFSPs, this paper proposes an improved simulated annealing (SA) algorithm based on residual network (SARes). First, this paper defines the neighborhood of the PFSP and divides its key blocks. Second, the Residual Network (ResNet) is used to extract and train the features of key blocks. And, the trained parameters are stored in the SA algorithm to improve its performance. Afterwards, some key operators, including the initial temperature setting and temperature attenuation function of SA algorithm, are also modified. After every new solution is generated, the parameters trained by the ResNet are used for fast ergodic search until the local optimal solution found in the current neighborhood. Finally, the most famous benchmarks including part of TA benchmark are selected to verify the performance of the proposed SARes algorithm, and the comparisons with the-state-of-art methods are also conducted. The experimental results show that the proposed method has achieved good results by comparing with other algorithms. This paper also conducts experiments on network structure design, algorithm parameter selection, CPU time and other problems, and verifies the advantages of SARes algorithm from the aspects of stability and efficiency. Keywords Permutation flow shop scheduling · Improved simulated annealing algorithm · Residual networks · TA benchmark

Introduction Scheduling is an indispensable part of the modern manufacturing process. Intelligent workshop scheduling can not only ensure the orderly progress of workshop manufacturing process but also maximize the utilization of resources and reduce the waste in the manufacturing process, thus reducing the production and manufacturing cost [28]. The permutation flow shop scheduling problem (PFSP), which is one of the most important scheduling types, is widespread in the modern industries, including automobile [35], electronic [5], chemical [20] and other industries. Therefore, the effective

B

Xinyu Li [email protected]

1

The State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan, China

2

The State Key Laboratory of CAD&CG, Zhejiang University, Hangzhou, China

PFSP algorithm can improve the productivity of these industries well. However, the PFSP is a well-known NP—hard problem and is very hard to be solved