摘要
针对以最小化总流水时间为目标的混合零空闲流水车间调度问题,提出一种有效的贪婪引力搜索算法(GGSA)进行求解。引入了基于升序排列(ROV)规则的编码方式,使引力搜索算法(GSA)能够应用于离散优化问题;其次,对GSA进行了改进:在初始化中加入NEH(Nawaz-Enscore-Ham)启发式规则构造高质量的初始解,以提高搜索效率;引入可变迭代贪婪(vIG)算法,利用其较强的局部开发能力,提高算法精度;同时,在vIG算法中加入参照插入方案(RIS)和模拟退火收敛判据,前者可以加强局部搜索能力、加快收敛速度,后者可以帮助算法在一定程度上跳出局部最优。最后,通过对典型测试算例进行仿真,验证了所提出算法的有效性。
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.
作者
赵芮
顾幸生
ZHAO Rui;GU Xingsheng(Key Laboratory of Advanced Control and Optimization for Chemical Process, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China)
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2021年第7期1909-1917,共9页
Computer Integrated Manufacturing Systems
基金
国家自然科学基金资助项目(61973120,61573144,61773165,61673175)。
关键词
引力搜索算法
混合零空闲
流水车间调度
迭代贪婪
总流水时间
gravitational search algorithm
mixed no-idle
flow shop scheduling
iterative greedy
total flow time
