摘要
The permutation flowshop scheduling problem with the objective of minimizing total flow time is known as a NP-hard problem, even for the two-machine cases. Because of the computational complexity of this problem, a multi-start simulated annealing (MSA) heuristic, which adopts a multi-start hill climbing strategy in the simulated annealing (SA) heuristic, is proposed to obtain close-to-optimal solutions. To examine the performance of the MSA algorithm, a set of computational experiments was conducted on a well-known benchmark-problem set from the literature. The experiment results show that the performance of the traditional single-start SA can be significantly improved by incorporating the multi-start hill climbing strategy. In addition, the proposed MSA algorithm is highly effective and efficient as compared with the other state-of-the-art meta-heuristics on the same benchmark-problem instances. In terms of both solution quality and computational expense, the proposed algorithm contributes significantly to this extremely challenging scheduling problem.
学科与关键词
- ALGORITHMS FOR BICRITERIA MINIMIZATION IN THE PERMUTATION FLOW SHOP SCHEDULING PROBLEMMokotoff, Ethel*Journal of Industrial and Management Optimization, 2011, 7(1): 253-282.被引 4
- An adaptive hybrid metaheuristic for permutation flowshop schedulingMoccellin, JV*; dos Santos, MOCONTROL AND CYBERNETICS, 2000, 29(3): 761-771.被引 3
- A Hybrid Algorithm for Multi-Objective Optimization of Minimizing Makespan and Total Flow Time in Permutation Flow Shop Scheduling ProblemsRobert, R. B. Jeen*; Rajkumar, R.Information Technology and Control, 2019, 48(1): 47-57.被引 6
