关键词: 引力搜索算法, 混合零空闲, 流水车间调度, 迭代贪婪, 总流水时间

Abstract: Aiming at the mixed no-idle Permutation flow shop scheduling problem with minimized total flow time,an effective Greedy Gravitational Search Algorithm (GGSA) was proposed.A rule called the Ranked-Order-Value (ROV) was applied to the improved algorithm,which enabled the continuous Gravitational Search Algorithm (GSA) to be used in all sequencing problems.Furthermore,the gravitational search algorithm was improved.Nawaz-Enscore-Ham (NEH) heuristic rule was added to the initialization to construct high quality initial solutions to improve search efficiency.The variable Iterative Greedy (vIG) algorithm was embedded to improve the accuracy of algorithm with its better local development ability.The Referenced Insertion Scheme (RIS) and the simulated annealing convergence criterion was introduced in vIG,the former could enhance the local search ability and accelerate the convergence speed,while the latter could help the algorithm jump out of the local optimum to some extent.The simulation results based on the well-known benchmark suites showed the effectiveness of the proposed algorithm.

Key words: gravitational search algorithm, mixed no-idle, flow shop scheduling, iterative greedy, total flow time