Coordinate Multi-agent With Organization In Distributed Scheduling System

Numerous scheduling and planning problems in various industrial environments are known to be extremely challenging, especially large scale scheduling and planning optimization problems. Airport Ground Service Scheduling (AGSS) problem is such a problem.After a brief review of researches on AGSS related areas, formulations of AGSS problem are presented from constraint satisfaction view. Furthermore, AGSS problem is classified as a NP-complete (PSPACE-complete in some cases) scheduling problem.A dynamic distributed scheduling model is structured for AGSS problem then, and a dynamic distributed scheduling environment run-and-schedule is put forward to collect and uniform AGSS related data. DSAFO (Dynamic Scheduling Agents with Federation Organization) is a novel multi-agent algorithm for AGSS problem. To fulfill constraint satisfactions and optimizations in AGSS, DSAFO employs two strategies: local heuristics and global coordination, based on roles of agents in a federation organization.In a typical AGSS solving process, DSAFO accepts real-time flights data from run-and-schedule environment; decomposes flight service goals into operations, according to gathered data; divides the solution space dynamically into rational partitions with multi-agents; conquers each partition with local heuristics within an agent; optimizes the solution simultaneously via coordination among partitions from global view; and dispatches the solution to real world aircraft service resources simultaneously.The complexity of DSAFO is bounded between quadratic and cubic polynomial time. Though experiments show that DSAFO is unstable and influenced by several parameters, this algorithm is good at satisfying all constraints, jumping out of local minimum, and finding near optimal solutions for consumption of resources and man-days. After careful experiments and theoretical analysis on parameters in DSAFO, a comparison is presented with three opponent algorithms, including a MMAS approach and two traditional heuristics.Finally a brief conclusion of DSAFO and the future research directions in AGSS are given at the end of this thesis.