基于批量流水线调度问题的混合离散果蝇优化算法

《基于批量流水线调度问题的混合离散果蝇优化算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于批量流水线调度问题的混合离散果蝇优化算法　　摘要：提出了一种混合离散果蝇优化算法，求解以最大完工时间为目标的批量流水线调度问题。与传统的果蝇算法不同，首先，该算法采用基于工序的编码方式，使得算法适合解决调度问题；其次，混合了贪婪迭代进化机制进行群体间相互协作的学习，以此平衡算法的全局开发能力和局部搜索能力。仿真试验表明了所提果蝇算法的有效性和高效性。　　关键词：果蝇优化算法；批量流水线调度问题；贪婪迭代　　中图分类号：TP18文献标识码：A文章编号：1009-3044（2015）30-0146-03　　HybridDiscre

2、teFruitFlyOptimizationAlgorithmforLot-streamingFlowShopSchedulingProblem　　PANYu-xia1，JIABao-xian2　　（1.DepartmentofBasicComputerEducation，SanyaUniversity，Sanya572000，China；2.SchoolofComputerScience，LiaochengUniversity，Liaocheng252059，China）　　Abstract：Thispaperpresentsa

3、HybridDiscreteFruitFlyOptimizationAlgorithm（HDFOA）forsolvingtheLot-streamingflowshopschedulingproblem（LFSP）withmakespancriteria.UnlikethetraditionalFOA，theproposedalgorithmappliesthejob-permutation-basedrepresentation，makesureitissuitablefor7schedulingproblem.Second，I

4、terativeGreedyismadeforthewholegroup，sothatthewhogroupkeepsingoodbalancebetweenglobalexplorationandlocalexploitation.Finally，toimprovetheefficiencyoftheschedulingalgorithm.ComputationalresultsshowthattheFOApresentedinthispaperisveryeffectiveandefficientfortheLFSP.　　Ke

5、ywords：fruitflyoptimizationalgorithm；lot-streamingflowshopschedulingproblem；iterativegreedy　　1概述　　批量流水线调度问题（Lot-streamingFlowshopSchedulingProblem，LFSP）广泛应用于冶金、塑料、化工等工业生产中，具有重要的理论研究背景和实际应用价值。随着市场竞争的日益激烈和客户需求的多样化，多品种中小批量生产模式占据了主导地位。因此对批量流水线调度问题的研究已成为学术界和工程界的关注焦点。　　果蝇优化

6、算法（FruitFlyOptimizationAlgorithm，FOA）是近几年刚兴起的一类全局进化优化算法，于2011年由台湾博士潘文超提出的。该算法源于对果蝇觅食行为的模拟，已经在求解数学函数极值[3]，自动化仓库拣选作业调度问题[4]等方面得到成功的应用。由于FOA提出时间不长，理论研究尚不成熟，就已经在求解连续和离散问题方面显示了特有的优势。因此FOA算法的相关研究迫切需要开展。　　2批量流水线调度模型7　　为了减小机床的等待时间，将每个工件按等量分配的原则划分成若干个小批量。各个工件的小批量加工完成后就能被传送到下一台

7、机床上加工，所有小批量的加工顺序都相同。假设工件按机床1到[m]的顺序加工，给定一个工序[π=δ1，δ2，…，δn]，工件[j]被划分成[sj]个小批量，[ltij]是工件[j]的小批量在机床[i]上的加工时间，[ctijk]为工件[j]的第[k]个小批量在机床[i]上的完成时间，[cj]为工件[j]的完成时间，则LFSP的数学模型为：　　1）[ct1，δ1，1=lt1，δ1]　　第一个工件的第一个小批量在第一台机床上的完成时间；　　2）[cti，δ1，1=cti-1，δ1，1+lti，δ1]，[i=2，...，n]　　第一个工件

8、的第一个小批量在第[i]台机床上的完成时间；　　3）[ct1，δ1，k=ct1，δ1，k-1+lt1，δ1]，[k=2，...，sδj]　　第一个工件的第[k]个小批量在第一台机床上的完成时间；　　4）[ct1，δj，1=ct1，δj-1，sδj-