The Research In Computational Complexity And Algorithm Convergence Efficiency For Mixed Shop Scheduling Problem

Based on the related research both at home and abroad, This article conducted a related study about mixed shop scheduling problem, involving modeling, computational complexity analysis, algorithm application, algorithm performance analysis and validation and some other issues.First of all, due to the large scale and complex systems of the MSP, network theory was used to establish a multi-level weighted graph model for the MSP in this article to express the network relationship between the multi-class structures within the MSP clearly.Secondly, the computational complexity of the MSP was analyzed. The computational complexity of a variety of operating modalities that the MSP contains was studied respectively. Using the reduction and transformation ideas of the complexity theory, the computational complexity of two kinds of operation modes within MSP was studied with knapsack problem approach of the complexity theory. Conclusions indicated that MSP was NP-hard problem, and its computational complexity was exponential or factorial level, so it was impossible to find the polynomial-time algorithm which could accurately obtained optimal solution.Thirdly, genetic algorithm (GA) was applied to solve the MSP and the convergence performance of genetic algorithms was analyzed. This paper presented a coding scheme that decimal integer and real numbers were combined. Based on this coding scheme, a specific genetic manipulation was implemented in order to make crossover not lose inheritance and mutation achieve population diversity; using the knowledge of Markov chain theory, the GA designed was proved to be convergent to the global optimum, and the probability was 1. Then, the convergence speed of the GA was analyzed, and the regulation how the values of parameters impacted the convergence speed of the algorithm was given.Finally, the simulation was conducted. Computer programs to solve the MSP with designed GA and other heuristic algorithms were compiled and ran by using software Matlab 7.0 to achieve programming. Minizing the makespan of MSP was chosen as the criterion. By comparing with the results of heuristic algorithm, the designed GA was validated feasible and effective. Then the simulation also demonstrated how the algorithm parameters affect on the convergence rate. Studies showed that is compatible with the theoretical analysis of the algorithm convergence rate.