Multi-population Whale Swarm Algorithm For Open Shop Scheduling Problem

The open shop has widely applications in various industries,and open shop scheduling problem is an important branch of production scheduling.In this paper,basic open shop scheduling problem,open shop scheduling problem considering transportation time and distributed open shop scheduling problem considering transportation time are systematically studied.Based on the framework of whale swarm algorithm,an improved algorithm is proposed to solve each problem according to its characteristics.Aiming at the basic open shop scheduling problem,a mixed integer linear programming model and a disjunctive graph model were established to minimize the makespan,and a multipopulation discrete whale algorithm was proposed.Based on the movement strategy,this algorithm designs an improved Levenstein distance calculation method.Combined with the search advantages of different populations,a multi-population parallel cooperative search strategy was adopted.Based on the two neighborhood structures,tabu operations are embedded in the local search to accelerate the convergence speed of the algorithm.Finally,the validity of the multi-population whale colony algorithm is verified by the comparison test of standard calculation and engineering example.For the open shop scheduling problem with transportation time,a mathematical model is established.Considering the effect of transportation time on completion time,a corresponding heuristic rule,the minimum delay heuristic rule,was designed to solve the problem.The neighborhood structure is further improved to make it more consistent with the characteristics of the problem.Finally,an example is given to verify the effectiveness of this algorithm.For distributed open shop scheduling problem with transportation time,a mathematical model is established and an improved multi-population whale swarm algorithm is proposed.In the improved algorithm,the corresponding coding strategy is designed.A heuristic initialization rule based on the minimum load difference is proposed.In the process of searching,step forward strategy is adopted to improve the efficiency of searching the optimal solution.Four kinds of neighborhood structures are designed and embedded into the framework of variable neighborhood descent search algorithm for local search.Finally,the validity of the improved multi-population whale swarm algorithm is verified through the test of the example set.At the end of this paper,the research work of this paper is summarized,and the future research direction is prospected.