Research On The Distributed Blocking Flow Shop Scheduling Problem And Its Solving Algorithm

Intelligent manufacturing is one of the five projects of “made in China 2025” plan and is an important research content of current manufacturing system.Scheduling strategy and control algorithm of manufacturing system are the key and bottleneck to improve enterprise productivity and meet market demand.The Flow Shop Scheduling Problem(FSP)plays an important role in modern manufacturing,transportation,machinery automation and other systems,and is one of the key supporting technologies for modern enterprises and manufacturing industries.Generally,the classic flow shop scheduling problem assumes that there are no infinite buffer capacities between consecutive machines.However,in many real-world industries,the buffer capacities between machines is limited or even zero,due to technical requirements or processing characteristics.In this case,the flow shop scheduling problem will be transformed into a blocking flow shop scheduling problem(BFSP).Menwhile,as the development of technology and science,the production model of various companies has changed from single factory to a multi-factory.The Distributed Blocking Flow Shop Scheduling Problem(DBFSP)with multi-factory has become one of the hot issues in the scheduling field.Moreover,DBFSP is a classic NP-Hard problem,the difficulty of solving DBFSP increases exponentially as the problem size increases.The traditional mathematical methods have been unable to effectively solve the DBFSP.Therefore,no matter from the application level of the practical problem or the theoretical research level of the scheduling problem,finding an efficient and accurate algorithm is of great significance to solve the distributed blocking flow shop scheduling problem.As a group-based heuristic search algorithm,the differential evolution(DE)algorithm has attracted various attention owing to its advantages such as simple theory and easy to implement.However,the traditional DE algorithm is not directly used to solve combinatorial optimization problems with discrete characteristics because the population of DE is generated and encoded by the floating-point vectors.In this study,the operating mechanism of the DE was researched.After the operating theory of the DE was analyzed,the framework and the update mechanism of algorithm are changed to improve the search performance and efficiency of algorithm.The improved algorithm is applied to solve the single-objective real parameter optimization problem and nonseparable problem.Meanwhile,based on the characteristics of the DBFSP problem and the characteristics of the DE algorithm,the DE algorithm was adjusted and successfully applied to the scheduling problem.The main research contents and results in this study are as follows.(1).Previous research has shown that DE has various disadvantages such as easily trapped in local optimum,converging prematurely in the early evolution,and having high sensitivity to control parameters.In order to solve the above problems,a collaborative LSHADE algorithm with comprehensive learning mechanism(LSHADE-CLM)is proposed in this paper to solve the single-objective real parameter optimization problem.In the LSHADE-CLM algorithm,a novel collaborative mutation mechanism including “/(80)9) (70)0)/” and “/(80)9) (70) /1” is proposed in the mutation operation.In the “/(80)9) (70)0)/ ” strategy with comprehensive learning mechanism,the population covariance matrix is utilized to generate candidate solutions and guide the search direction.Meanwhile,a competitive reward mechanism is implemented to control the mutation factor to generate a trial vector for the cooperative mechanism.Moreover,the dimensional reset strategy is applied to enhance the diversity of the population at the dimensional level when stagnation is identified at certain dimension.The simulated results on the standard test set and the comparison results of two rigorous hypothesis tests indicate that LSHADE-CLM outperforms the compared algorithms and is an effective method to solve the single-objective real parameter optimization problem.(2).For the lack of theoretical analysis of DE algorithm,the convergence and time complexity of LSHADE-CLM algorithm are analyzed in this study.The LSHADE-CLM converges to the global optimal solution with the probability 1 based on the finite homogenous Markov chain model.Meanwhile,the LSHADE-CLM is mapped into the discrete domain by the LOV rule.The proposed DLSHADE-CLM(Discrete LSHADE-CLM,DLSHADE-CLM)algorithm is proposed and applied to solve the blocking flow shop scheduling problem.The experimental results obtained by the standard benchmark set were shown that the proposed DLSHADE-CLM algorithm is an effective algorithm for solving BFSP.(3).Based on the research of distributed blocking flow shop scheduling problem,an ensemble discrete differential evolution algorithm was proposed for soloving the distributed blocking flow shop scheduling with minimizing makespan criterion(EDE).In the EDE algorithm,the candidates are represented as discrete job permutations.The mutation,crossover and selection operators are redesigned to assist the EDE algorithm to execute in the discrete domain.Meanwhile,based on the characteristics of DBFSP,two heuristics method and one random strategy are integrated to provide a set of desirable initial solution for the distributed environment.The front delay,blocking time and idle time are considered in heuristic methods.Moreover,an elite retention strategy is introduced in the EDE algorithm framework to balance exploitation and exploration ability of the EDE algorithm.The proposed algorithm is tested in a standard test set and compared with various state-of-the-art algorithms.The experimental results and analysis were shown that the proposed EDE algorithm is an effective algorithm for solving DBFSP.