Efficient Reasoning about Infeasible One Machine Sequencing

Authors

  • Raúl Mencía University of Oviedo, Gijón, Spain
  • Carlos Mencía University of Oviedo, Gijón, Spain
  • Joao Marques-Silva IRIT, CNRS, Toulouse, France

DOI:

https://doi.org/10.1609/icaps.v33i1.27204

Keywords:

Plan and schedule execution, monitoring, and repair

Abstract

This paper addresses the tasks of explaining and correcting infeasible one machine sequencing problems with a limit on the makespan. Concretely, the paper studies the computation of high-level explanations and corrections, which are given in terms of irreducible subsets of the set of jobs. To achieve these goals, the paper shows that both tasks can be reduced to the general framework of computing a minimal set over a monotone predicate (MSMP). The reductions enable the use of any general-purpose algorithm for solving MSMP, and three well-known approaches are instantiated for the two tasks. Furthermore, the paper details efficient scheduling techniques aimed at enhancing the performance of the proposed algorithms. The experimental results confirm that the proposed approaches are efficient in practice, and that the scheduling optimizations enable critical performance gains.

Downloads

Published

2023-07-01

How to Cite

Mencía, R., Mencía, C., & Marques-Silva, J. (2023). Efficient Reasoning about Infeasible One Machine Sequencing. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 268-276. https://doi.org/10.1609/icaps.v33i1.27204