蛙跳算法与批量无等待流水线调度问题的优化  

Shuffled frog-leaping algorithm for lot-streaming no-wait flowshop scheduling problem

作　　者：谢圣献[1] 潘全科[1] 潘玉霞[2] 贾保先[1] 

机构地区：[1]聊城大学计算机学院,山东聊城252059 [2]海南大学三亚学院,海南三亚572022

出　　处：《计算机应用研究》2010年第8期2909-2912,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(60874075;70871065);数字制造装备与技术国家重点实验室开放课题(华中科技大学);博士后科学基金资助项目(20070410791);山东省软件科学研究计划资助项目(2009RKB125);山东省教育厅资助项目(J08LJ20)

摘　　要：针对以makespan为指标的批量无等待流水线调度问题,提出了一种有效的离散蛙跳算法。首先采用基于工序的编码方式使蛙跳算法直接应用于调度问题;其次采用基于NEH与改进NEH和随机产生相结合的初始化方法,保证了初始解的高质量和分布性;再次采用交叉或变异方法产生新解,保持了种群的优越性和多样性;最后对全局最优解执行快速局部搜索,有效地降低了算法的时间复杂度,平衡算法的全局和局部开发能力。对随机生成不同规模的实例进行广泛的实验,通过仿真实验结果的比较,表明所得蛙跳算法的有效性和高效性。This paper proposed an effective shuffled frog-leaping algorithm （ SFLA） for solving the lot-streaming flow shop scheduling problem with the criterion of minimizing maximum completion time （i. e. ,makespan） under no-wait production cases. Firstly,the proposed SFLA represented an individual or frog as a job permutation to make the original SFLA suitable for scheduling problem. Secondly,designed an initialization method based on the NEH heuristic. Thirdly,used a crossover operator or mutation operator to produce a new individual. Finally,in order to further enhance the algorithm’s exploitation capability and efficiency,embedded a fast local search algorithm based on the insert or swap neighborhood in the proposed shuffled frog-leaping algorithm. This can reduce CPU time. The computational results and comparisons show that the proposed SFLA is effective and efficient for random instants in finding better solutions for the problem considered.

关 键 词：批量无等待流水线调度 蛙跳算法 快速局部搜索 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]