批量流水线调度问题的混合离散蛙跳算法  

Hybrid discrete shuffled frog-leaping algorithm for lot-streaming flowshop scheduling problem

作　　者：潘玉霞[1] 潘全科[2] 桑红燕[2] 

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

出　　处：《计算机集成制造系统》2010年第6期1265-1271,共7页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(60874075;70871065);华中科技大学数字制造装备与技术国家重点实验室开放课题资助项目;博士后科学基金资助项目(20070410791)~~

摘　　要：研究了以提前/拖后惩罚指标为目标的批量流水线调度问题,给出了该问题的数学模型以及小批量的调整策略。根据蛙跳算法的原理,采用基于工序的编码方式并利用两点交叉操作设计了新的位置生成公式,提出了解决该问题的离散蛙跳算法。为进一步增强算法的开发能力和效率,结合扰动策略、模拟退火概率接受准则和插入邻域搜索对该算法进行改进。对随机生成的实例进行了广泛的试验,结果表明了所提算法的高效性。The lot-streaming flow shop scheduling problem to minimize the total Earliness /Tardiness（E/T）penalty was studied.According to the principle of frog-leaping algorithm,a novel allocation function was designed by adopting sequence-based coding method and two-point crossover operator.Then,a novel discrete Shuffled Frog-Leaping Algorithm（SFLA）was put forward to solve the problem.To further enhance development capability and efficiency of the algorithm,the proposed SFLA was improved with perturbation tactic,simulated annealing acceptance criteria and inserting neighborhood search.Extensive experiments based on the randomly generated instances were conducted.Computational results and comparison verified the effectiveness of the proposed algorithm.

关 键 词：批量流水线 调度 蛙跳算法 模拟退火 插入邻域搜索 数学模型 

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