A hybrid algorithm with a new neighborhood structure for job shop scheduling problems. (July 2022)

• Record Type: Journal Article
• Authors: Xie, Jin; Li, Xinyu; Gao, Liang; Gui, Lin
• Is Part Of: Computers & industrial engineering. Volume 169(2022)
• Publication Date: 2022-07
• Subjects: Job shop scheduling problems -- Tabu search -- Genetic algorithm -- Neighborhood structure; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108205
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A hybrid algorithm with a new neighborhood structure is designed for JSP. A crossover operator referring to a path relinking procedure is proposed. A mutation operator based on critical paths is designed. HA has updated two upper bounds for JSP, DMU56-4939 and DMU57-4647. Abstract: Job shop scheduling problems (JSP) arise from the scheduling of modern manufacturing enterprises. It is one of the most famous NP-complete problem. To evaluate the performance of algorithms, several famous benchmarks have been presented from 1990s. A few decades later, some instances had been found the optimal solutions, but more instances remain unresolved. Trying to update the new upper bounds, the paper presents a hybrid algorithm (HA) combining the genetic algorithm (GA) and the tabu search (TS) to solve JSP with the makespan criterion. GA has an excellent global search ability, and TS has a powerful local search ability. Our HA can combine their advantages and well balance the intensification and the diversification. In the GA part, the paper designs a crossover operator referring to a path relinking procedure and a mutation operator on a basis of critical paths. In the TS part, the paper adopts our previously proposed neighborhood structure, which can effectively expand the search space of neighborhood solutions. 135 famous benchmark instances are selected to evaluate the optimization effect of HA. Six state-of-the-art methods are selected to compare with HA. The results verify that the HA outperforms its compared algorithms in both computational efficiency and solution quality. Especially, the proposed HA has updated the upper bounds of two challenging instances, DMU56-4939 and DMU57-4647.