Paper Info
Title
Total flow time minimization in no-wait job shop using a hybrid discrete group search optimizer
Abstract
The no-wait job shop scheduling problem is a well-known NP-hard problem and it is typically decomposed into timetabling subproblem and sequencing subproblem. By adopting favorable features of the group search technique, a hybrid discrete group search optimizer is proposed for finding high quality schedules in the no-wait job shops with the total flow time criterion. In order to find more promising sequences, the producer operator is designed as a destruction and construction (DC) procedure and an insertion-based local search, the scrounger operator is implemented by differential evolution scheme, and the ranger operator is designed by hybridizing best insert moves. An efficient initialization scheme based on Nawaz–Enscore–Ham (NEH) heuristic is designed to construct the initial population with both quality and diversity. A speed-up method is developed to accelerate the evaluation of the insertion neighborhood. Computational results based on well-known benchmark instances show that the proposed algorithm clearly outperforms a hybrid differential evolution algorithm and an iterated greedy algorithm. In addition, the proposed algorithm is comparable to a local search method based on optimal job insertion, especially for large-size instances.
Year
DOI
Venue
2019
10.1016/j.asoc.2019.05.007
Applied Soft Computing
Keywords
Field
DocType
Scheduling,Job shop,Group search,Metaheuristics,No-wait
Population,Mathematical optimization,Heuristic,Job shop,Differential evolution,Schedule,Operator (computer programming),Local search (optimization),Initialization,Mathematics
Journal
Volume
ISSN
Citations 
81
1568-4946
1
PageRank 
References 
Authors
0.35
0
4
Name
Order
Citations
PageRank
Guanlong Deng151.76
Zhiwang Zhang28111.15
Tianhua Jiang374.48
Shuning Zhang4239.40