An Intelligent Algorithm Based On Block-structured Neighborhoods Solves The Reentrant Job Shop Scheduling Problem

In the intelligent manufacturing system,scheduling is a key factor affecting the production efficiency of enterprises.Proper and effective scheduling can help cut lead times,improve on-time delivery,reduce inventory,so as to increase the prestige of enterprises.Recently,with the upgrading of market competition as a result of the economic globalization and the variety and individuality of consumers' demands,scheduling is playing an increasingly important role in the manufacturing industry.Shop scheduling problem,there are some complex features such as nonlinear,strong constraints,multi-objective,uncertainty,and so on.Such problems also have a characteristic of largescale which usually results in modeling difficulty.Developing effective intelligent optimization algorithm for complex shop scheduling problem has become a hot research topic of the production scheduling field.The design and property analysis of the neighborhood structure is an important research issue in the field of combinatorial optimization.The effective neighborhood structure can significantly speed up the convergence of the algorithm and improve the search performance of the entire algorithm.Salp swarm algorithm(SSA)and flower pollination algorithm(FPA)are new swarmbased intelligence evolutionary algorithm can be used to solve complex continuous or discrete optimization problems.Bayesian evolutionary algorithm(BEA)is a new intelligent optimization algorithm based on conditional probability distribution model,can be used to solve the multi-variable related optimization problems effectively.In this paper,SSA,FPA and BEA based on block structure neighborhoods are applied to solve reentrant job shop scheduling problems(RJSSP).The main work is as follows.(1)Salp swarm algorithm(SSA)based on blocks on critical path is presented to minimize the maximum completion time(i.e.makespan)for reentrant job shop scheduling problem(RJSSP).Firstly,the mathematical model of RJSSP based on the disjunctive graph is established.Secondly,four kinds of neighborhood structures are defined after defining the insert operation based on block structure,and then a high-efficient local search integrating multiple neighbor-hoods is proposed.(2)Flower pollination algorithm(FPA)based on block structure properties is presented to minimize the total weighted tardiness(TWT)for reentrant job shop scheduling problem(RJSSP).Firstly,the mathematical model of RJSSP based on the disjunctive graph is established,and then its duality model is proved to be the model of maximum cost flow problem after it being determined the direction of the disjunctive arcs.Secondly,the extended reentrant-smallest-order-value(RSOV)encoding rule is designed to transform FPA's individuals from real vectors to job permutations so that FPA can be used to perform global search for finding high-quality solutions or regions in the solution space.Thirdly,eight kinds of neighborhood structures are defined,and the inner properties of block structures are analyzed based upon the properties of the maximum cost flow problem.The determination conditions of the four former neighborhood structures for improving TWT are obtained by the block structures' analyses,which can be used to avoid search in the invalid regions.Then,a high-efficient local search integrating multiple neighborhoods with the obtained determination conditions is proposed to execute a thorough search from the promising regions found by the global search.(3)Bayesian evolutionary algorithm(BEA)is presented to address the reentrant job shop scheduling problem with energy consumption threshold(RJSSP?ECT)to minimize makespan,the total weighted tardiness(TWT)and the total energy consumption(TEC).First,the mathematical model of RJSSP?ECT based on the disjunctive graph is established.Second,a Bayesian evolutionary algorithm based on a Bayesian probabilistic model and an adaptive model updating scheme is presented to execute exploration in solution space and find promising regions.Third,six kinds of neighborhood structures are defined,and the inner properties of block structures are analyzed based on the properties of RJSSP?ECT.For reducing the maximum completion time of all jobs on each machine,the determination conditions of these neighborhood structures are obtained by the analyses of block structures.Then these conditions are extended to RJSSP?ECT's optimization objectives to avoid invalid neighborhood search.Fourth,a high-efficient local search integrating multiple neighborhoods with the obtained determination conditions is proposed to execute a thorough search from the promising regions found by the global search.Simulation and experiment results demonstrate the effectiveness of the proposed algorithms.