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

基于批量流水线调度问题的混合离散果蝇优化算法 　　摘要：提出了一种混合离散果蝇优化算法，求解以最大完工时间为目标的批量流水线调度问题。与传统的果蝇算法不同，首先，该算法采用基于工序的编码方式，使得算法适合解决调度问题；其次，混合了贪婪迭代进化机制进行群体间相互协作的学习，以此平衡算法的全局开发能力和局部搜索能力。仿真试验表明了所提果蝇算法的有效性和高效性。 　　关键词： 果蝇优化算法；批量流水线调度问题；贪婪迭代 　　中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）30-0146-03 　　Hybrid Discrete Fruit Fly Optimization Algorithm for Lot-streaming Flow Shop Scheduling Problem 　　PAN Yu-xia1， JIA Bao-xian2 　　（1.Department of Basic Computer Education， Sanya University ，Sanya 572000，China；2.School of Computer Science，Liaocheng University， Liaocheng 252059，China ） 　　Abstract： This paper presents a Hybrid Discrete Fruit Fly Optimization Algorithm （HDFOA） for solving the Lot-streaming flow shop scheduling problem（LFSP） with makespan criteria.Unlike the traditional FOA， the proposed algorithm applies the job-permutation-based representation ，make sure it is suitable for scheduling problem. Second， Iterative Greedy is made for the whole group， so that the who group keeps in good balance between global exploration and local exploitation. Finally， to improve the efficiency of the scheduling algorithm . Computational results show that the FOA presented in this paper is very effective and efficient for the LFSP. 　　Key words： fruit fly optimization algorithm； lot-streaming flow shop scheduling problem； iterative greedy 　　1 概述 　　批量流水线调度问题（Lot-streaming Flowshop Scheduling Problem ，LFSP） 广泛应用于冶金、塑料、化工等工业生产中，具有重要的理论研究背景和实际应用价值。随着市场竞争的日益激烈和客户需求的多样化，多品种中小批量生产模式占据了主导地位。因此对批量流水线调度问题的研究已成为学术界和工程界的关注焦点。 　　果蝇优化算法（Fruit Fly Optimization Algorithm，FOA）是近几年刚兴起的一类全局进化优化算法，于2011年由台湾博士潘文超提出的。该算法源于对果蝇觅食行为的模拟，已经在求解数学函数极值[3]，自动化仓库拣选作业调度问题[4]等方面得到成功的应用。由于FOA提出时间不长，理论研究尚不成熟，就已经在求解连续和离散问题方面显示了特有的优势。因此FOA算法的相关研究迫切需要开展。 　　2 批量流水线调度模型 　　为了减小机床的等待时间，将每个工件按等量分配的原则划分成若干个小批量。各个工件的小批量加工完成后就能被传送到下一台机床上加工，所有小批量的加工顺序都相同。假设工件按机床1到[m]的顺序加工，给定一个工序[π=δ1，δ2，…，δn]，工件[j]被划分成[sj]个小批量，[ltij]是工件[j]的小批量在机床[i]上的加工时间， [ctijk]为工件[j]的第[k]个小批量在机床[i]上的完成时间，[cj]为工件[j]的完成时间，则LFSP的数学模型为： 　　1）[ct1，δ1，1=lt1，δ1] 　　第一个工件的第一个小批量在第一台机床上的完