Stable multi-project scheduling of airport ground handling services by heterogeneous agents

ABSTRACT

This paper addresses decentralized multi-project scheduling under uncertainty. The problem instance we study is the scheduling of airport ground handling services, where aircraft turnarounds can be seen as multiple projects, ground handling services as activities, and service providers as resources. In this environment aircraft requiring ground handling services and the corresponding service providers are self-interested autonomous parties. Moreover, the environment is well-known for its large number of disturbances.

We employ a heterogeneous multiagent scheduling framework with two types of autonomous agents representing aircraft and ground service providers respectively. We use online scheduling to cope with uncertainty in the release time of project: the uncertainty in aircraft arrival time at an airport. To balance the interests of the two types of agents in this heterogeneous multiagent system, we propose a market-based mechanism to assign time slots to aircraft turnaround activities. We study the use of this mechanism in a cooperative and a non-cooperative setting.

In a dynamic environment such as airport ground handling, the execution of project schedules may be invalidated by various disruptions. As a result project agents may incur high costs if they have to reschedule some of their activities. The insertion of slack time between activities is a well known solution. The delay cost incurred by inserting slack should balance the expected costs of rescheduling some activities. Since in a dynamic multiagent system it is hard to analytically calculate optimal slack time between activities, we propose that agents determine these slack time using a co-evolutionary learning approach.

Experiment show that our decentralized scheduling approach scores on average as high as well-established OR-based heuristics, and that slack times to keep a schedule stable can be learned.

REFERENCES

• 1: G. Confessore, S. Giordani, and S. Rismondo. A market-based multi-agent system model for decentralized multi-project scheduling. Annals of Operations Research, 150:115--135, 2007.
• 2: R. Dawkins. The Selfish Gene: 30th Anniversary Edition -- with a New Introduction by the Author. Oxford University Press, 2006.
• 3: Kenneth A. De Jong , William M. Spears, An Analysis of the Interacting Roles of Population Size and Crossover in Genetic Algorithms, Proceedings of the 1st Workshop on Parallel Problem Solving from Nature, p.38-47, October 01-03, 1990
• 4: E. L. Demeulemeester and W. Herroelen. Project Scheduling -- A Research Handbook. Springer, 2002.
• 5: U. Dorndorf. Project Scheduling with Time Windows: From Theory to Applications. Physica-Verlag, 2002.
• 6: Junling Hu , Michael P. Wellman, Nash q-learning for general-sum stochastic games, The Journal of Machine Learning Research, 4, p.1039-1069, 12/1/2003
• 7: G. Knotts, M. Dror, and B. C. Hartman. Agent-based project scheduling. IIE Transactions, 32:387--401, 2000.
• 8: R. Kolisch and A. Sprecher. Psplib -- a project scheduling problem library. European Journal of Operational Research, 96:205--216, 1997.
• 9: I. S. Kurtulus and E. Davis. Multi-project scheduling: Categorization of heuristic rules performance. Management Science, 28(2):161--172, 1982.
• 10: Y. Lee, S. R. T. Kumara, and K. Chatterjee. Multiagent based dynamic resource scheduling for distributed multiple projects using a market mechanism. Journal of Intelligence Manufacturing, 14:471--484, 2003.
• 11: R. Leus. The generation of stable project plans. PhD thesis, Katholieke Universiteit Leuven, Belgium, 2003.
• 12: A. Lova and P. Tormos. Analysis of scheduling schemes and heuristic rules performance in resource-constrained multiproject scheduling. Annals of Operations Research, 102(1--4):263--286, Feb 2001.
• 13: K. Neumann, C. Schwindt, and J. Zimmermann. Project Scheduling with Time Windows and Scarce Resources. Springer, 2nd edition, 2001.
• 14: J. Paredis. Coevolutionary algorithms. In T. Bäck, D. B. fogel, and Z. Michalewicz, editors, Evolutionary Computation 2: Advanced Algorithms and Operators, pages 224--238. Institute of Physics Publishing, Bristol, UK, 2000.
• 15: K. Sycara, S. Roth, N. Sadeh, and M. S. Fox. Distributed constrained heuristic search. IEEE Transactions on Systems, Man, and Cybernetics, 21(6):1446--1461, Nov./Dec. 1991.
• 16: S. van de Vonder, E. Demeulemeester, W. Herroelen, and R. Leus. The trade-off between stability and makespan in resource-constrained project scheduling. International Journal of Production Research, 44(2):215--236, January 2006.
• 17: J. Weibull. Evolutionary Game Theory. The MIT Press, 1997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Design, Experimentation

Keywords:
airport ground handling, multiagent system, uncertainty