基于流水线调度问题的模型与局部搜索算法

《基于流水线调度问题的模型与局部搜索算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于流水线调度问题的模型与局部搜索算法郭盈刘心报（合肥工业大学管理学院合肥230009）摘要：在基于流水线的调度问题中，所有工件按照相同的顺序访问机器，但部分或全部工件可以不必在某些机器上进行加工。标准flowshop问题是这种流水线调度问题的一个特例。研究了带序依赖和机器依赖加工准备时间的流水线调度问题，针对该问题建立了一个基于序列的0-1混合整数规划模型，目标函数是总加权完工时间最小，提出了相应的局部搜索算法，实验结果证明了算法的有效性和可应用性，所提出的局部搜索算法的求解思路对同类流水线调度问题具有

2、指导意义。关键字：流水线调度工序跳跃总加权完工时间加工准备时间局部搜索非置换方案中图分类号：F273文献标识码：AModelandlocalsearchalgorithmfortheflowlineschedulingproblemwithmissingoperationsGUOYingLIUXinbao(SchoolofManagement,HefeiUniversityofTechnology,Hefei,AnhuiProvince,230009)Abstract:Intheflowlinesched

3、ulingproblemwithmissingoperations,alljobsvisitasetofmachinesfollowingasameandunidirectionalroutebutsomeoralljobscanskipsomemachines.Thestandardflowshopproblemisaspecialcaseofthistypeofflowlineschedulingproblem.Thispaperconsidersthistypeofflowlineschedulin

4、gproblemwiththesequenceandmachinedependentsetuptimes.Forthisproblem,amathematicalmodelbasedonthejobsequenceisformulatedby0-1mixedintegerproblemandtheobjectiveistofindthenon-permutationschedulesthatminimizethetotalweightedcompletiontimes.Alocalsearchalgori

5、thmispresentandcomputationalresultsdemonstratetheeffectivity,efficiencyandpracticabilityofthenewalgorithm.Theideaoftheproposedalgorithmbeabletoprovideresearchersandpractitionersasuggestforothertypesoftheflowlineproblemswithmissingoperations.Keywords:flowl

6、inemissingoperationstotalweightedcompletiontimessetuptimeslocalsearchnon-permutation60前言*本研究由“国家自然科学资金（71171071）”资助。第一作者：郭盈，女，1982年生，博士生，主要研究方向：生产调度，carol.g@163.com；通讯作者：刘心报，博士，教授，lxinbao@126.com.经典flowshop问题，假设所有工件都必须按照完全相同的工艺路线在所有的机器上进行加工。而在实际的生产环境中，加工路

7、线往往更加灵活，比如有的工件可以不必在某些机器上进行加工，这类问题称之为允许工序跳跃的流水线调度问题。由于放宽了工艺路线的约束条件，标准的flowshop问题只是该类流水线调度问题的一个特例。事实上，这种流水线调度问题在实际的生产环境中十分常见，尤其是基于流水线或单元制造系统的离散加工制造业。然而，对于该类问题，学术界目前的研究成果还甚少。1994年，Rajendran[1]首次提及在基于流水线的制造单元中允许工序跳跃的实际生产情况，同时强调了跳跃的工序对于最后的调度结果的影响甚大；1998年，Parth

8、asarathy和Rajendran[2]讨论了这种广泛存在于基于流水线制造单元的调度问题，但这两篇论文都没有提出针对此类问题的相应算法。2002年，Pugazhendhi等人[3]首次对该类问题提出了一个启发式算法，并指出置换（permutationschedule，PS）调度方案可以较好地适用于传统flowshop问题，但并不适合允许工序跳跃的流水线调度问题，因为PS调度方案可能引发机器“强制空闲”6从而影响最终结果，文章