Research And Implementation Of Parallel Machine Scheduling Based On Hybrid Cuckoo Search

Parallel machine scheduling is a typical model of actual production scheduling problems.Parallel machine scheduling problem is usually regarded as NP-hard problem.When the problem scale is large,it is very difficult to accurately solve the parallel machine scheduling problem in a limited time.Cuckoo search algorithm is a novel heuristic intelligent optimization algorithm.Because of its proven feature of global convergence,it has been widely used to solve a variety of difficult combinatorial optimization and production scheduling problems.This paper takes the cuckoo search algorithm as the main framework,designs the coding scheme and improves the algorithm flow,and proposes a hybrid cuckoo search algorithm based on the bi-directional sorting encoding scheme to minimize the maximum completion time of the identical parallel machine scheduling problem.The main contents of this paper are as follows:(1)This paper proposes a bi-directional sorting encoding scheme,which requires the scheduling plan to arrange the jobs on the machine in descending order and the machines in ascending order according to their loads.Using the encoding scheme to encode the discrete scheduling plan,a greedy local search process is realized in the corresponding decoding process.The construction and transformation of scheduling plan by bi-directional sorting coding scheme can transform parallel machine scheduling problem from a combinatorial problem to a permutation problem.(2)A novel discrete Levy flight process is designed,which realizes the random transformation of permutation based on modular arithmetic.The scheduling plan of bidirectional sorting coding scheme is executed random walk to simulate the global search and convergence process of discrete scheduling plan.In addition,a neighborhood structure and the corresponding neighborhood actions are proposed,and a shaking factor is constructed.An improved variable neighborhood search algorithm is designed,which can effectively realize the local search of the parallel machine scheduling problem.(3)The bionic process of the cuckoo search algorithm is researched,and an improved cuckoo search algorithm execution process is designed.Firstly,in the initialization process of the algorithm,selecting an excellent initial population can improve the quality of the initial solution and accelerate the convergence speed;secondly,based on the elite strategy,design an intelligent cuckoo to achieve better results by actively abandoning poor nests,enhance the efficiency of local search and improve the final convergence effect.(4)Design three comparative experiments to verify the proposed hybrid cuckoo search algorithm based on bi-directional sorting encoding scheme.Firstly,the parallel machine scheduling problem is solved based on the same coding scheme and algorithm framework to verify the evaluation metric proposed in this paper;secondly,the effectiveness of the proposed bi-directional sorting encoding scheme is evaluated by comparing the encoding scheme using real number field to map discrete problems;finally,it is compared with an improved cuckoo search scheduling algorithm proposed in recent years to verify the effectiveness of the hybrid cuckoo search algorithm proposed in this paper.The experimental results show that the approximation coefficient evaluation metric proposed in this paper is more reasonable.Compared with other encoding schemes,the bi-directional sorting encoding scheme is more competitive in solving the parallel machine scheduling problems.The parallel machine scheduling algorithm based on hybrid cuckoo search removes the preset fixed value of the number of jobs on the machine by the improved cuckoo search algorithm,and can obtain a better scheduling result.