Research On Combinatorial Optimization And Job Shop Scheduling Problem Based On Fitness Landscape

Scheduling is a key factor for manufacturing productivity. In a manufacturing environment scheduling is that allocates machines for processing a number of jobs. Proper and effective scheduling can cut lead times, improve on-time delivery, reduce inventory, and increase the reputation of enterprise. Recently, with the competitive pressure of today's global market and consumer demand for variety, scheduling problem is becoming more and more important for the manufacturing industry.It is well-known that the Job Shop Problem is NP-hard, and the minimum Makespan problem of Job Shop scheduling is a classical combinatorial optimization problem. However, our theoretical understanding of these combinatorial optimizations is very limited, leading to significant problems for both researchers and practitioners. Specifically, the lack of a theory of problem impedes the development of more effective algorithms, prevents practitioners from identifying the algorithm most appropriate for a given problem.Based on analyzing combinatorial optimization and the model of JSP, we perform a novel analysis of the fitness landscapes of the Job Shop problem, prove that the JSP problem is very complexity; we research the configuration space of the JSP, trying to find the inherent characteristics of the Job Shop problem. Those results can provide theoretical basis for solving JSP. And on the basis, we give the methods framework to solving JSP. Those may provide a partial explanation for the remarkable success of the latter in solving the JSP.First, we introduced the general research methods of combinatorial optimization and the No Free Lunch theorem, and studied the fitness landscape of the knapsack problem and traveling salesman problem, and analyzed the global search. Then the relationship between fitness and the factors of impact of the fitness landscape space were analyzed. Second, the mathematical model and disjunction were given, and the complexity of this model was analyzed, and the characters of the fitness were studied, including the factors of impact of the Job Shop problem's fitness landscape space were analyzed, followed it show that the landscape of the JSP is non-regular. Then the relation between the backbone and the fitness of the JSP is studied.Third, in order to using the landscape characters of the Job Shop to solve the problem, we also discuss the characters of evolution algorithm. In the process solving combinatorial optimization, we research the principle of crossover processing and mutation processing, and how those can impact the global optima. We get three typical fitness landscapes of the Job Shop problem, and we develop a general, fast and easily implemented hybrid optimization algorithm which base on Job Shop Problem Fitness Landscape and the particle swarm optimization;The effectiveness and efficiency of the proposed algorithm are demonstrated by applying it to some benchmark Job Shop scheduling problems. The effectiveness of the hybrid optimization algorithm model is also validated. One scheduling tool DAPSOJSP is developed.Finally, conclusion is drawn and the future research focus is pointed out.