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

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

提出了一种改进的生物地理学优化(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.