基于改进生物地理学优化算法的分布式装配置换流水车间调度问题  

Distributed Assembly Permutation Flowshop Scheduling Problem Based on Modified Biogeography-Based Optimization Algorithm

作　　者：黄佳琳 张丫丫 顾幸生 HUANG Jialin;ZHANG Yaya;GU Xingsheng(Key Laboratory of Advanced Control and Optimization for Chemical Processes,Ministry of Education,East China University of Science and Technology,Shanghai 200237,China)

机构地区：[1]华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海200237

出　　处：《华东理工大学学报（自然科学版）》2020年第6期758-769,共12页Journal of East China University of Science and Technology

基　　金：国家自然科学基金(61573144,61773165,61673175)。

摘　　要：提出了一种改进的生物地理学优化(MBBO)算法,以最小化最大完工时间为目标,求解分布式装配置换流水车间调度问题。MBBO算法在初始化阶段利用加工时间最短(SPT)规则和NR2规则对生成的可行解进行初步优化;然后在变异阶段采用基于工厂完工时间的工件插入启发式方法调整工件的工厂分配及加工顺序;最后结合模拟退火算法,跳出局部最优解,增强算法的全局搜索能力。对900个小型实例和540个大型实例进行仿真计算,并与现有的12种启发式与元启发式算法以及基本生物地理学优化(BBO)算法进行比较,证明了MBBO算法的优越性,同时更新了70个实例的最新已知最优方案。It is usually assumed in flowshop scheduling problem that all of the processing procedures are performed in one factory,which is termed as single factory production mode.Nowadays,the distributed manufacturing,due to its low cost,low risk,and high quality,has been becoming the main development trend in the industrial production.Therefore,it is necessary to study the distributed scheduling problem.The distributed assembly permutation flowshop scheduling problem plays an important role in modern supply chains and manufacturing systems.In this paper,a modified biogeography-based optimization(MBBO)algorithm is proposed for solving distributed assembly permutation flowshop scheduling problem to achieve the goal of minimizing makespan.In the initialization phase,the proposed MBBO uses SPT and NR2 rules to optimize the feasible solutions.Then,in the mutation phase,the job insertion heuristic method based on the factory completion time is used to adjust the factory assigning and the processing order of the jobs.Moreover,the simulated annealing algorithm is combined to avoid the local optimal solutions and enhances the global search ability.Finally,simulation experiments are made via 900 small instances and 540 large instances,and the comparison is provided with the existing 12 heuristic and metaheuristic algorithms as well as the basic biogeography-based optimization algorithm.These results verify the superiority of the proposed MBBO.Meanwhile,the new best known solutions for 70 instances are found.

关 键 词：生产调度 生物地理学优化算法 分布式 装配置换流水车间 改进 

分 类 号：TB497[一般工业技术] TP18[自动化与计算机技术—控制理论与控制工程]