Research On Complex Scheduling Problems Based On Complex Network Theory

Scheduling, as a resource distributed plan, is recognized and well studied in various areas and departments. Real-world scheduling objects are always dynamic, stochastic, and indeterminate. Such scheduling objects are named as complex scheduling objects in this thesis and the corresponding scheduling problems are named as complex scheduling problems. Scheduling rules are the main methods to solve this type of scheduling problems for their simpleness and flexibility. However, most of existed scheduling rules are summarized from operators' experiences and there lacks a systematical designing method. Complex network, as a tool/theory to describe and analyze the structure of complex systems, may provide a totally fresh view for scheduling problems. Through building complex network models for those complex scheduling objects, the complex scheduling problems can be transferred to node traverse problems on complex networks. Then a lot of scheduling rules can be proposed under the background of complex network theory. In this thesis, three new scheduling rules are systematically proposed and applied to multi-resources independent task complex scheduling problems, and get very well results. The main contents of this thesis include following five parts:Propose three multi-properties complex network models based on the measurements of many real-world complex systems. The three models are region-fixed local-world model, ability-fixed local-world model, and game theory based dynamical evolving model.Describing complex scheduling problems with complex networks for the first time, the scheduling problems then can be considered as node traverse problems on complex networks, which provides new visual angles and methods to solve complex scheduling problems.The local properties of nodes in complex scheduling networks are considered as heuristic information for complex scheduling problems and used to design scheduling rules, through mapping the scheduling problems to global properties, e.g., average degree or average efficiency, of the networks. And several local properties of nodes, e.g., degree, clustering coefficient, and redundancy proposed by this thesis are all can be used to design scheduling rules. Provide detailed steps for modeling complex scheduling networks and following these steps, build complex scheduling network models for four types of complex scheduling objects, i.e., multi-resources independent task scheduling objects with the number of resources one event needed following uniform distribution, multi-resources independent task scheduling objects with the number of resources one event needed following power-law distribution, multi-resources dependent task scheduling objects with the number of resources one event needed following uniform distribution, and multi-resources dependent task scheduling objects with the number of resources one event needed following power-law distribution. Then give structural analysis for these complex scheduling networks.Propose three different scheduling rules based on the structure of complex scheduling networks: degree based rule, clustering coefficient based rule, and redundancy based rule. Then apply these scheduling rules to solving multi-resources independent task complex scheduling problems, and get better results compared with several other classical scheduling rules.