Research On Complex Shop Scheduling Problem Based On Quantum Intelligent Algorithm

Scheduling is a hot topic in the research of manufacturing system,and is also one of the most difficult problems in theoretical research.In this paper,we review the research progress of scheduling problem,and study no-wait flow shop scheduling problem(NWFSSP)with sequence-independent setup times(SISTs)and release dates(RDs)and no-wait flow shop scheduling problem with sequence-dependent setup times(SDSTs)and release dates.Based on the analysis of the characteristics of the problem,a novel hybrid quantum-inspired evolutionary algorithm and a heuristic method are designed to solve the problem.Simulation results show the effectiveness of the proposed algorithm.The main work of this paper is summarized as follows:(1)In this paper,an improved quantum evolutionary algorithm and a specially designed local search method are proposed to solve the no-wait flow shop scheduling problem with sequence-independent setup times and release dates,which has been proved to be a NP-hard problem.The criterion is to minimize the makespan.The proposed algorithm is compared with other algorithms,and the experimental results show that the improved quantum-inspired evolutionary algorithm achieves better performance.(2)In this paper,a novel hybrid quantum evolutionary algorithm is proposed,which is combined with a specially designed local search to solve the no-wait flow shop scheduling problem with sequence-dependent setup times and release dates.First of all,according to the nature of the problem,given the speed-up evaluation method,which makes the algorithm can search more areas in the same period of time;and then,put forward the improved quantum probability amplitude observation operation in order to enhance the global search algorithm to search the solution space efficiency;finally,design the speed-up search method for Ni+(?),two strategies for SP_FBNic(?)strategy,and integration them into the interchange-based neighborhoods.Therefore,the algorithm can improve the searching ability of the promising region.In the performance test,the algorithm is tested in detail,including the optimization of the parameters,including the contrast test of the global algorithm and the comparison test of the complete algorithm.The effectiveness and robustness of the proposed algorithm are verified by comparing the simulation results with 6 international journals.