An approximate evaluation method for neighbourhood solutions in job shop scheduling problem. Issue 3 (13th September 2022)

• Record Type: Journal Article
• Authors: Gui, Lin; Li, Xinyu; Gao, Liang; Xie, Jin
• Other Names: Li Xinyu guestEditor.; Wen Long guestEditor.
• Is Part Of: IET collaborative intelligent manufacturing. Volume 4:Issue 3(2022)
• Page Start: 157
• Page End: 165
• Publication Date: 2022-09-13
• Subjects: approximate evaluation method -- domain knowledge -- job shop scheduling -- local search; Production management -- Periodicals; Production engineering -- Periodicals; Production management; Production engineering; Electronic journals; Periodicals; 658.5
• DOI: 10.1049/cim2.12049
• Languages: English
• ISSNs: 2516-8398

Abstract

Abstract: Job shop scheduling problem is a classical scheduling problem, and it is very difficult to work out. To solve it well, the meta‐heuristic algorithm is a good choice, and the evaluation method of neighbourhood solutions, which affects the efficiency of the algorithm and the quality of the solution, is one of the keys in the algorithm. We propose an approximate evaluation method by exploring domain knowledge in neighbourhood solutions. Firstly, we reduce the computational time of the evaluation by analysing the unnecessary computational operations. Secondly, according to the domain knowledge, we prove that the evaluated value of the neighbourhood solution is the exact value under certain conditions. At the same time, a set of critical parameters are calculated to correct the estimated value of the neighbourhood solutions that do not meet the conditions to improve the evaluation accuracy. With all of these, an approximate evaluation method for neighbourhood solutions in job shop scheduling problems is proposed. The experiments on different numerical instances show the superiority of the method proposed.