基于链接学习的生物地理学算法求解置换流水车间调度问题  

Research on Permutation Flow-shop Scheduling Problems with Biogeography-based Optimization Based on Linkage Learning

作　　者：赵衡 刘颖艳 付礼鹏 ZHAO Heng;LIU Yingyan;FU Lipeng(School of Management,Tianjin University of Technology,Tianjin 300384,China;College of Tourism and Service Management,Nankai University,Tianjin 300350,China;College of Management and Economics,Tianjin University,Tianjin 300072,China)

机构地区：[1]天津理工大学管理学院,天津300384 [2]南开大学旅游与服务学院,天津300350 [3]天津大学管理与经济学部,天津300072

出　　处：《运筹与管理》2023年第5期1-8,共8页Operations Research and Management Science

基　　金：国家创新方法工作专项项目(2017IM060200)。

摘　　要：针对置换流水车间调度问题的特性,提出了一种基于链接学习的生物地理学算法(Biogeography-based optimization based on linkage learning,LLBBO)来对其求解。算法以生物地理学算法为架构,使用反向学习方法(Opposition-based learning,OBL)生成初始解,依据群体适应度值将群体分为优秀群体和劣势群体,使用信息熵的概念以及数理统计方法通过对这两个群体进行统计,分别建立概率矩阵模型以构建一种链接学习模型称为链接区块,使用链接区块依照算法迁移率对群体进行迁移操作实现群体更新。为进一步改善算法的搜寻性,提出一种NEH序列重组法对解序列执行局部搜索以进一步提高适应度。最后运用所提的LLBBO算法通过对基准例题的仿真测试和算法比较验证了所提算法的有效性。Permutation flow-shop scheduling problem(PFSP)is different kind of the combinatorial problems and is categorized as NP-Hard problem,which is a very typical production planning problem in the field of shop scheduling.The goal of solving PFSP is devoted to finding out an optimal permutation so that makespan is minimal.To find the solution of PFSP is a common challenge in which an algorithm may be trapped in the local optima of the objective function when the complexity is high,and there are several local optima in solution space.In response to the above issues,this study proposes a biogeography-based optimization based on linkage learning(LLBBO)for solving PFSP with the objective of minimizing the makespan.The main contribution of this study is to propose a novel algorithm that greatly improves the effectiveness and efficiency when compared with previous researches in solving benchmark PFSPs.Moreover,the proposed algorithm is expected to be applied to solving other combinatorial optimization problems.The algorithm takes biogeography-based optimization as architecture,using opposition-based learning mechanism to generate initial groups.The initial groups are divided into dominant group and disadvantage group according to population fitness,based on which the immigration and emigration rates are calculated and the habitat with high HSI has a higher immigration rate.After that,the information entropy is used to calculate the entropy value of each position of the solution sequence.By describing the degree of clutter of the workpiece on each machine,the key machine with a low degree of clutter can be effectively found out as the location covered by the linkage blocks.The linkage blocks are constructed based on the key locations calculated using information entropy.Linkage blocks are linkage structure units that mine frequently occurring segments at the same location or arrangement in the solution sequence based on the statistical information of the solution sequence of a population.These combination of linkage segments

关 键 词：置换流水车间调度 信息熵 链接学习 生物地理学算法 NEH算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]