应用萤火虫算法求解基于学习效应的PFSP 问题
2015-04-17叶春明凌远雄
杜 贞,叶春明,凌远雄
DU Zhen,YE Chunming,LING Yuanxiong
上海理工大学 管理学院,上海200093
Department of Management,University of Shanghai for Science and Technology,Shanghai 200093,China
1 引言
置换流水车间调度问题(Permutation Flow-shop Scheduling Problem,PFSP)是实际生产车间中一类重要的流水车间调度问题,尤其适用于单件大批量生产背景的制造型企业。该问题可以被描述为:n个工件在m台不同的机器上加工,每个工件有m道不同的工序,每道工序要在不同的机器上加工完成;n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同;每台机器每次只能加工一个工件,每个工件每次只能由一台机器加工;已知每个工件在每台机器上的加工时间;求解的目标是确定最优加工顺序,使得按照该顺序加工工件时总完工时间最小。
对PFSP 的求解方法,可以分为三种类型:精确方法、启发式算法以及智能优化算法。研究表明,精确算法只适用于小规模问题的求解,启发式算法求解质量较差[1],而当m>2 时,PFSP 问题已是NP 难题[2],因此随着问题规模的增加,调度问题的解空间容量巨大,其求解过程更加复杂。由于精确方法和启发式算法的局限性,目前对该问题的求解方法趋向于使用更高效的智能优化算法,包括遗传算法、禁忌搜索算法、模拟退火法、蚁群优化算法以及粒子群算法等[3]。本文采用的萤火虫算法[4-5]是一种比较新颖的算法,在生产调度方面的研究刚刚起步,但也取得了一些成果:文献[6-8]分别应用该算法求解PFSP 和Job-shop 调度问题,通过对PFSP 中的典型Car 类测试问题和Job-shop 调度问题的FT、LA 两类测试问题进行仿真测试,并将结果与粒子群等算法的结果进行对比,验证了算法的可行性和有效性。……p>
