Characteristic Analysis And Improved Tactic Research Of Traditional Optimization Methods In Solving Job-shop Scheduling Problem

Job-shop scheduling problem is an NP-hard combinatorial optimization problem, of which the research is focused on feasible and efficient scheduling algorithms. Currently, heuristic algorithms are applied to solve the problem in most of researches. Traditional optimization methods can solve common constraint problems efficiently. However, there are a few researches of using traditional optimization methods to solve the Job-shop scheduling problem. Complex method and penalty function method are efficient methods to solve constraint problems. Topological sort algorithm can make appropriate schedules of tasks. Considering minimum make-span as the optimization objective, the thesis analyzes flows and characteristics of solving the Job-shop scheduling problem by complex method, penalty function method and algorithm based on topological sort, realizes the scheduling program and develops the Job-shop scheduling system.Firstly, the thesis analyses the model of Job-shop scheduling problem and the steps of solving common constraint problems by complex method, proposes some improved tactics for solving the Job-shop scheduling problem by complex method, structures the solution flow, and researches the solution characteristics of complex method.Secondly, by using the thought of penalty function method to solve constraint problems through transforming them into non-constraint problems, the thesis expresses the constraints of Job-shop scheduling problem by penalty terms, combines penalty function method with cyclic coordinate method that can solve non-constraint problems and executes one-dimensional search of variables considered in the problem starting from initial solution to achieve the aim of finding optimal solution. Meanwhile, the flow and the characteristics of penalty function method in solving Job-shop problem are analyzed in the thesis.Thirdly, the algorithm based on topological sort is proposed by combining the topological sort method in graph theory with the equipments distribution rules of Job-shop scheduling problem in the thesis. According to the relationship that a topological sequence of the directed acyclic graph can be gained if operations in each feasible solution are ordered by the beginning time, the scheduling problem is divided into topological sort sub-problem and equipments distribution sub-problem. By solving the two sub-problems, the flow and the characteristics of the algorithm are analyzed.Finally, a Job-shop scheduling system is developed in the thesis by C++Builder software and Microsoft SQL Server software, in which the programs of complex method, penalty function method and the algorithm based on topological sort are realized. By instance research in the system, the feasibility of those methods is proved and the characteristics of those methods in solving the Job-shop scheduling problem are compared.