用改进的蛙跳算法求解一类模糊Flow Shop调度问题  

An Improved Shuffled Frog Leaping Algorithm for Fuzzy Flow Shop Scheduling Problem

作　　者：徐晓[1] 徐震浩[1] 顾幸生[1] 王雪[1] 

机构地区：[1]华东理工大学信息科学与工程学院,上海200237

出　　处：《华东理工大学学报（自然科学版）》2010年第5期702-707,共6页Journal of East China University of Science and Technology

基　　金：国家自然科学基金项目(60774078);国家"863"高技术研究发展计划项目(2009AA04Z141);上海市基础研究重点项目(08JC1408200);上海市自然科学基金项目(10ZR1408300)

摘　　要：对加工时间不确定的Flow Shop调度问题进行研究,提出了一种改进的蛙跳算法(NewShuffled Frog Leaping Algorithm,NSFLA)。蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)的局部搜索采用类似粒子群算法的搜索机制,全局搜索采用洗牌策略即种群间定期进行信息交换。为了解决SFLA的局部搜索易出现不合法调度的问题,在交换子和交换序概念的基础上,提出了交换序构造的初始位置随机机制和交换子的随机插入机制这两种追踪策略。仿真实验结果验证了NSFLA解决模糊Flow Shop问题的有效性。A new shuffled frog leap algorithm（NSFLA） is presented for the flow shop scheduling problem（FSSP） with uncertain processing time.A particle swarm optimization-like method is applied in the local search of SFLA,while a shuffle strategy where the information is periodically exchanged between complexes is used in global search.To cope with the problem that the local search of SFLA easily generates illegal solutions,two tracking strategies,i.e.,randomization of the initial position in swap sequence constructing and random inserting of the swap operator,are proposed by means of the concepts of the swap operator and swap sequence.Numerical simulation results show the effectiveness of the NSFLA for fuzzy flow shop scheduling problem.

关 键 词：蛙跳算法 不确定性 FlowShop调度 交换子和交换序 

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