摘要
This paper studies a hybrid flow shop scheduling problem (hybrid FSSP) with multiprocessor tasks, in which a set of independent jobs with distinct processor requirements and processing times must be processed in a k-stage flow shop to minimize the makespan criterion. This problem is known to be strongly nondeterministic polynomial time (NP)-hard, thus providing a challenging area for meta-heuristic approaches. This paper develops a simulated annealing (SA) algorithm in which three decode methods (list scheduling, permutation scheduling, and first-fit method) are used to obtain the objective function value for the problem. Additionally, a new neighborhood mechanism is combined with the proposed SA for generating neighbor solutions. The proposed SA is tested on two benchmark problems from the literature. The results show that the proposed SA is an efficient approach in solving hybrid FSSP with multiprocessor tasks, especially for large problems.
学科与关键词
- A novel metaheuristic approach for the flow shop scheduling problemNearchou, ACENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2004, 17(3): 289-300.被引 38
- An adaptive hybrid metaheuristic for permutation flowshop schedulingMoccellin, JV*; dos Santos, MOCONTROL AND CYBERNETICS, 2000, 29(3): 761-771.被引 3
- An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardinessNaderi, B.; Zandieh, M.*; Balagh, A. Khaleghi Ghoshe; Roshanaei, V.EXPERT SYSTEMS WITH APPLICATIONS, 2009, 36(6): 9625-9633.被引 142
