离散与声求解带启动时间批量流水线调度问题

《离散与声求解带启动时间批量流水线调度问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、离散与声求解带启动时间批量流水线调度问题　　摘要：分别在有等待和无等待的情况下，深入分析了带有启动时间的批量调度问题，以最小化最大完成时间为目标，提出了两种离散和声搜索算法。针对算法本质连续而问题离散的矛盾，对和声搜索算法进行改进。首先提出了基于工序的编码方式，采用inver-over和重组两种离散算子产生候选解的进化机制；并利用改进的NEH（Nawaz-Enscore-Ham）方法进行初始化，产生的高质量和多样化的初始种群有效地指导了算法的进化方向，提高收敛速度；最后将一种简单而有效的局部邻域搜索方法嵌入到和声搜索算法中以增强其局部搜索能力。仿真实验和比较结果表明了所提算法的有效性。关键词：

2、和声搜索；批量流水线调度；启动时间；最大完工时间；局部搜索中图分类号：TP18文献标志码：ADiscreteharmonysearchalgorithmforlot-streamingflowshopschedulingproblemwithsetuptimeAbstract：14Inthispaper，twodiscreteHarmonySearch（HS）algorithmswereproposedtosolvelot-streamingflowshopschedulingproblemwithsetuptimeunderboththewaitandno-waitcases.Theobje

3、ctivewastominimizethemaximumcompletiontimeormakespan.UnliketheoriginalHSalgorithm，theproposedalgorithmrepresentedaharmonyasadiscretejobpermutationandappliedinver-overandreconstructionoperatorstogenerateanewmechanism.AnefficientinitializationschemebasedonthemodifiedNawaz-Enscore-Ham（NEH）heuristicwasp

4、resentedtoconstructaninitialpopulationwithacertainlevelofqualityanddiversity.Asimplebuteffectivelocalsearchwasaddedtoenhancetheintensificationcapability.Thecomputationalresultsandcomparisonsshowthattheproposedalgorithmiseffectiveandefficientinfindingbettersolutionsfortheproblemconsidered.Keywords：Ha

5、rmonySearch（HS）；lot-streamingflowshopscheduling；setuptime；makespan；localsearch0引言14批量流水线调度问题即将工件划分为若干个子批量，通过移动完成加工的子批量进行下一道工序来允许同一工件在相邻的机床上重叠操作[1]，以减少机床的等待时间，这在当今时代是一种基于时间的有效加速生产的技术。此类问题广泛存在于实际生产环境中，很多研究人员对其进行了研究[2-5]。和声搜索（HarmonySearch，HS）源于对乐曲创作过程的模拟，是一种新型的群智能优化算法，首先被Geem等用于求解函数优化问题。由于其结构简单、容易实现等优

6、点，而后又被成功应用于多维多极值函数优化[6-9]、交通路径[9]、土坡稳定分析[10]。HS算法在解决连续问题上有更好的优化性能，由于其连续的本质，对于组合优化问题有一定的局限性。基于以上情况，将HS离散化，采用简单而高效的离散算子，产生较高质量的解，并通过插入局部邻域搜索提高搜索效率和算法开发能力。1批量流水线调度问题1.1问题描述批量流水线调度问题（Lot-streamingFlowShopScheduling14Problem，LFSSP）可描述为将n个工件j∈J={1，2，…，n}划分成若干个小批量，按一定顺序依次通过m台机床i∈M={1，2，…，m}进行加工；同时约定一个批量在某一

7、时刻只能在一台机床上加工，一台机床某一时刻只能加工一个批量。每台机床上工件的顺序相同。为了加速生产，将每个工件在所有机床上都被划分为l（j）个等大的批量，工件j的每个批量在机床i上的加工时间为p（i，j）。只要一个小批量被加工完成即可被送到下一台机床上进行下一道工序。工件j在机床i上的启动时间为s（i，j）。在无等待的限制条件下，同一批量的所有工序必须连续加工，即要求任一批量在某台机床上的完成时间