Discrete Artificial Bee Colony Algorithm For Distributed No-wait Flowshop Scheduling Problem

Distributed manufacturing has become one of the main manufacturing modes.No-wait flowshop scheduling problem(NWFSP)has always been one of the typical problems in the field of scheduling.Distributed NWFSP(DNWFSP)widely exists in real-world production.This paper takes DNWFSP as the research object.Considering heterogeneity on factories and multi-objective optimization,distributed heterogeneous NWFSP(DHNWFSP)and multiobjective DHNWFSP(MDHNWFSP)are studied.Based on the characteristics of the problem,and using artificial bee colony(ABC)as the main method,a corresponding algorithm is proposed to solve the above problems.The main work of this paper is as follows.For DNWFSP,a mixed-integer linear programming(MILP)model of DNWFSP with makespan as objective is established,and the calculation method of the completion time is given.Discrete ABC(DABC)are proposed for this problem.In DABC,four neighborhood structures based on the characteristics of DNWFSP are presented,which are used to generate feasible neighborhood solutions in the phases of employed bees and onlookers to improve the quality of populations.In view of the influence of neighborhood moving speed on algorithm convergence,combined with the characteristics of DNWFSP coding,an acceleration method for neighborhood evaluation was proposed.In the phase of scouts,a variable neighborhood descent algorithm based on four local search methods is adopted to enhance the capability of exploitation.Finally,tested with benckmarks,and the effectiveness and efficiency of the proposed algorithm on DNWFSP are verified by comparing with other algorithms of DNWFSP.For DHNWFSP,based on DNWFSP,the differences in the number of machines,machine processes,and raw material transportation conditions in each factory are considered,that is,heterogeneity.A MILP model of DHNWFSP with makespan as an objective is established and the calculation method of makespan is given.Combined with the characteristics of DHNWFSP,the initialization phase of the DABC algorithm and the acceleration method of neighborhood evaluation is improved.Tested on different scales of DHNWFSP.Compared with CPLEX and other algorithms,DABC has the same effect as other algorithms on small scale problems.In terms of large-scale problems,DABC is significantly better than other algorithms,and the current optimal solution for almost all the examples can be obtained.For MDHNWFSP with sequence-dependent setup time(MDHNWFSP-SDST),a multiobjective optimization model was established to minimize makespan and total tardiness.Based on the characteristics of MDHNWFSP-SDST and multi-objective,a multi-objective DABC algorithm based on Pareto optimality is proposed.In this algorithm,the improved PWQ algorithm(IPWQ)is used to initialize the population.In the phase of employed bees,considering the characteristics of the distributed scheduling problem,four neighborhood structures are used to generate feasible solutions to improve the population quality.In the phase of onlookers,an improved position-based crossover(IPBX)is used to generate the offspring population.Through IPBX,the diversity of the population is preserved while the superior characteristics of the parent are also preserved.In the phase of scouts,a multi-objective local search method is embedded to explore the solution space sufficiently.Finally,the effectiveness of the proposed algorithm on uniformity,convergence and comprehensive performance indexes is verified with other multi-objective algorithms.Finally,the research work of this paper is summarized,and the directions for future works are given.