Modeling adversary scheduling with QCSP⁺

ABSTRACT

We consider cumulative scheduling problems in the presence of an adversary. In such setting the scheduler tries to manage the available resources in so as to meet the scheduling deadline, while the adversary is allowed to change some parameters---like the resource consumption of some tasks---up to a certain limit. We ask whether a robust schedule exists, i.e., one that is guaranteed to work whatever (malicious) actions the opponent may take. We propose to model this family of decision problems using a variant of Quantified Constraint Satisfaction Problems called QCSP⁺, and to solve them by using the solver QeCode.

References

1. A. Aggoun and N. Beldiceanu. Extending CHIP in Order to Solve Complex Scheduling and Placement Problems. Mathematical and Computer Modelling, 17(7):57--73, April 1993.
2. C. Ansótegui, C. P. Gomes, and B. Selman. The Achilles' Heel of QBF. In Manuela M. Veloso and Subbarao Kambhampati, editors, AAAI, pages 275--281. AAAI Press AAAI Press / The MIT Press, 2005.
3. P. Baptiste, C. Le Pape, and W. Nuijten. Constraint-Based Scheduling. Operations Research and Management Science. Kluwer Academic Publishers, 2001.
4. J. F. Bard. Practical Bilevel Optimization: Algorithms and Applications, volume 30 of Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, 1999.
5. N. Beldiceanu and M. Carlsson. A New Multi-resource Cumulatives Constraint with Negative Heights. In Pascal Van Hentenryck, editor, CP, volume 2470 of Lecture Notes in Computer Science, pages 63--79. Springer, 2002.
6. M. Benedetti, A. Lallouet, and J. Vautard. QCSP Made Practical by Virtue of Restricted Quantification. In Manuela Veloso, editor, International Joint Conference on Artificial Intelligence, pages 38--43, Hyderabad, India, January 6--12 2007. AAAI.
7. J. Bidot, T. Vidal, P. Laborie, and J. C. Beck. A General Framework for Scheduling in a Stochastic Environment. In Manuela M. Veloso, editor, IJCAI, pages 56--61, 2007.
8. L. Bordeaux and E. Monfroy. Beyond NP: Arc-Consistency for Quantified Constraints. In P. Van Hentenryck, editor, Principles and Practice of Constraint Programming, volume 2470 of LNCS, pages 371--386, Ithaca, NY, USA, 2002. Springer.
9. G. G. Brown, W. M. Carlyle, J. Royset, and R. K. Wood. On the Complexity of Delaying an Adversary's Project. In The Next Wave in Computing, Optimization and Decision, volume 29 of Operations Research/Computer Science Interfaces Series, chapter 1. Springer, 2005.
10. M. Ghallab, D. Nau, and P. Traverso. Automated Planning. Morgan Kaufmann, 2004.
11. R. Graham, E. Lawler, E. Lenstra, and A. Rinnooy Kan. Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Annals of Discrete Mathematics, 5:287--326, 1979.
12. R. Kolisch, C. Schwindt, and A. Sprecher. Benchmark Instances for Project Scheduling Problems, 1998.
13. S. F. Smith N. Policella, A. Oddi and A. Cesta. Generating Robust Partial Order Schedules. In M. Wallace, editor, Principles and Practice of Constraint Programming, volume 3258, pages 496--511. Springer, 2004.
14. P. Nightingale. Consistency and the Quantified Constraint Satisfaction Problem. PhD thesis, University of St Andrews, 2007.
15. C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1994.
16. N. Policella. Scheduling with Uncertainty: A Proactive Approach Using Partial Order Schedules. PhD thesis, University of Rome "La Sapienza", March 2005.
17. C. Schulte and G. Tack. Views and Iterators for Generic Constraint Implementations. In Peter van Beek, editor, CP, volume 3709 of Lecture Notes in Computer Science, pages 817--821. Springer, 2005.
18. C. W. Wu, K. N. Brown, and J. C. Beck. Scheduling with Uncertain Durations: Generating Beta-Robust Schedules using Constraint Programming. In ICAPS 2006 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems, 2006.

Index Terms

• Computing methodologies

  • Machine learning

    • Machine learning approaches

      • Markov decision processes

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

• Mathematics of computing

  • Probability and statistics

    • Probabilistic representations

      • Decision diagrams

• Theory of computation

  • Computational complexity and cryptography

    • Oracles and decision trees

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Logic

    • Constraint and logic programming

  • Theory and algorithms for application domains

    • Machine learning theory

      • Markov decision processes

      • Reinforcement learning

        • Sequential decision making