The Gravitational Search Algorithm And Its Applied Research For The Shop Scheduling Problem

The shop scheduling problem is widely existed in the modern manufacturing systems,which is the key technology for improving the efficiency of enterprises.The blocking flow shop problem(BFSP)is one of the key models in the manufacturing systems,and has been proved as a strongly NP-Hard problem.The difficulty of solving BFSP is exponentially increased when the scale of the scheduling problem is expanded.Meanwhile,it is difficult for the traditional mathematical methods to solve the problem and even the optimal solution is not found.Therefore,designing an effective scheduling strategy is a hot and difficulty domain in the field of the scheduling issues both in the manufacturing production and in the theoretical research of the scheduling problem.The Gravitational Search Algorithm(GSA)is a new intelligent opti mization algorithm,which is inspired by the Newton's law of gravity.GSA has various advantages such as simple theory and easy to implement.It has been widely applied in various domains.In the paper,the operation mechanism of GSA is deeply studied,and the advantages and the disadvantages of GSA are analyzed.The framework of GSA and the unique operating mechanism are modified.The performance of the modified algorithm is improved.The i mproved algorithm is applied to solve the single-objective real parameter optimization proble m.The characteristics of the BFSP and GSA were analyzed.A modified algorithm is proposed,and it was used to solve the scheduling problem.The main research contents and results in this paper are as follows:(1)It is found that GSA has various disadvantages such as high sensitivity to the parameters and easy to stagnate in the end of evolution through the analysis of GSA.To solve the above problems,a hybrid algorithm based on self-adaptive gravitational search algorithm and differential evolution(SGSADE)is proposed to solve the single-objective real parameter optimization problem in the paper.In SGSADE,in order to overcome the disadvantage of high sensitivity to the parameters,a self-adaptive mechanis m is applied to adjust the key parameters and for improving the convergence speed and balancing exploration and exploitation.The diversity of the population is maintained in the location update operation by using crossover and mutation operation from differential evolution.To further improve the performance of SGSADE,a new perturbation based on Levy flight theory is embedded to enhance exploitation capacity.The simulated results on the standard test set and the comparison results of two rigorous hypothesis tests indicate that SGSADE outperforms the compared algorithms.(2)A discrete gravitational search algorithm(DGSA)is proposed for BFSP with total flow time mini mization.In DGSA,a new method based on variable profile fitting(VPF)and NEH heuristic,named VPF_NEH(n),is introduced for balancing the quality and the diversity of the initial population to configure the DGSA.In the update phase of the acceleration,velocity and po sition,the original continuo us methods has mis matched the scheduling proble m.Therefore,three key operators are introduced to DGSA including the variable neighborhood operators(VNO),path relinking and the plus operator during the location updating of the candidates.The objective of the operation is to prevent the premature convergence of the population and to balance the exploration and exploitation in the process of optimization.The simulated results on the test set indicate the effectiveness and superiority of the DGSA for solving the BFSP.(3)In view of the lack of theoretical analysis of the GSA,the conv ergence of SGSADE and the time complexity of DGSA are analyzed.The SGSADE converges to the global optimal solution with the probability 1 based on the finite ho mogeno us Markov chain model.The upper bound of the expected runti me is given based on the Method of Fitness-Based Partitions for DGSA.