Study And Design Of Hierarchical Job Scheduling Model Based On Ant Colony Optimization Algorithm

Job scheduling is a key issue in enterprise production and operation management, it is to solve how to distribute resources according to time sequence to optimize the predetermined target. GSP (Group Shop Scheduling Problem) is a simplified model for many practical production scheduling problems. It is a typical NP-hard problem, which has been proved unable to obtain optimal solution in polynomial time. Ant colony algorithm is a new heuristic algorithm for solving combinatorial optimization problem. As it possesses the features of fine new-solution-discovery ability, strong robustness and parallelism nature, it gradually becomes the research hotspot.The thesis describes the mathematical model and disjunctive graph model of GSP, analyzes its characteristics, studies the principle, theoretical framework and improved thoughts of the basic ant colony algorithm, mainly studies the algorithm thinking of one improved ant colony algorithm– MMAS (MAX-MIN Ant System), and goes deep into its application in GSP solution - MMAS-HC-GSP.The research took the national 863 project"Utility Engine MES (manufacturing execution system) based on RFID"as its background, summarizes the research results of the project and the demand for production scheduling, puts forward a HJSM (hierarchical job scheduling model) for GSP solution.HJSM consists of workshop scheduling and workbench scheduling. Workshop scheduling divides jobs into several subsets, and ganrantees their connexity in corresponding disjunctive graph, creates conditions for workbench scheduling, which realizes optimized scheduling for jobs with relatively short production cycle constraints on the basis of workshop scheduling.In the workshop scheduling design, the thesis brings forward the new concept of"related job set"through analyzing the correlation degree of the resources needed in jobs, and offers algorithm and data structure design to solve related job sets. In the workbench scheduling design, the thesis analyses the features of GSP disjunctive graph model, offers a generating algorithm of the disjunctive graph and its data structure design; it takes MMAS-HC-GSP as the core scheduling algorithm, presents the algorithm for its critical steps and the specific design for its data structure.The thesis designs the testing instance based on the background project. The test result shows that the model design has reached the expected target, and is able to provide preferable decision-making support for production scheduling. The proposal of HJSM has certain practical significance on the function extension of the background project MES, provides a new thought for production scheduling research, it is also of certain reference significance for the subsequent research and realization of production scheduling system.