Metaheuristic and Classical Approaches in Production Scheduling: Campbell Dudek Smith, Dannenbring, and Variable Neighborhood Descent
Abstract
The flow shop scheduling problem is well known to be NP-hard when involving m machines and n jobs. To address such combinatorial optimization problems, both classical heuristics and metaheuristic algorithms are often employed to generate near-optimal solutions within a reasonable computational time. This study investigates the performance of two classical heuristic methods—Campbell Dudek Smith (CDS) and Dannenbring—alongside a metaheuristic approach, Variable Neighborhood Descent (VND), in solving the flow shop scheduling problem. The objective is to determine an effective job sequence that minimizes the total completion time (makespan). A set of benchmark case studies is utilized to evaluate the methods, and the resulting makespan values are compared to assess their efficiency. The findings highlight the trade-offs between classical and metaheuristic approaches, providing insights into their applicability for practical production scheduling problems.
References
Y. Zhu, X. Wu, and C. Zhang, “A robust genetic algorithm with convexity criterion for ordered fl ow shop scheduling,” Processes, vol. 11, no. 5, p. 1583, 2023, doi: 10.3390/pr11051583.
R. Kumar, A. Singh, and P. Gupta, “Hybrid diff erential evolution and variable neighborhood search for permutation fl ow shop scheduling,” Applied Mathematics and Computation, vol. 421, p. 126957, 2022, doi: 10.1016/j.amc.2022.126957.
H. Liu, J. Chen, and X. Li, “A deep reinforcement learning–enhanced genetic algorithm for complex scheduling problems,” Expert Systems with Applications, vol. 223, p. 119965, 2023, doi: 10.1016/j.eswa.2023.119965.
J. de Armas, & J. A. Moreno-Pérez, (2025). A Survey on Variable Neighborhood Search for Sustainable Logistics. Algorithms, 18(1), 38. https://doi.org/10.3390/a18010038
D. D. Bedworth and J. E. Bailey, Integrated Production Control Systems: Management, Analysis, Design. New York, NY, USA: John Wiley & Sons, 1987.
A. Duarte, N. Mladenovic, J. Sanchez-Oro, and R. Todosijevic, “Handbook of Heuristics,” in Handbook of Heuristics, 2016, pp. 1–27. doi: 10.1007/978-3-319-07153-4.
G. Dueck and T. Scheuer, “Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing,” J. Comput. Phys., vol. 90, no. 1, pp. 161–175, 1990, doi: 10.1016/0021-9991(90)90201-B.
R. O. M. Diana and S. R. de Souza, “Analysis of variable neighborhood descent as a local search operator for total weighted tardiness problem on unrelated parallel machines,” Comput. Oper. Research, vol. 117, no. 5, pp. 1–15, 2020, [Online]. Available: http://dx.doi.org/10.1016/j.bpj.2015.06.056%0Ahttps://academic.oup.com/bioinformatics/article-abstract/34/13/2201/4852827%0Ainternal-pdf://semisupervised-3254828305/semisupervised.ppt%0Ahttp://dx.doi.org/10.1016/j.str.2013.02.005%0Ahttp://dx.doi.org/10.10
A. Lamghari, R. Dimitrakopoulos, and J. A. Ferland, “A variable neighbourhood descent algorithm for the open-pit mine production scheduling problem with metal uncertainty,” J. Oper. Res. Soc., vol. 65, no. 9, pp. 1305–1314, 2014, doi: 10.1057/jors.2013.81.
