A Planning/Scheduling Methodology for the Constrained Resource Problem

Naiping Keng, David Y. Y. YunIJCAI 1989

Introduction

In the field of Artificial Intelligence, many complex tasks are modeled as Constraint Satisfaction Problems (CSPs). A particularly challenging subset is the Constrained Resource Problem (CRP), where multiple tasks compete for a limited, non-sharable set of resources. Traditional solvers often struggle with two primary issues: "myopia"—making locally optimal choices that lead to global failures—and "premature commitment," which restricts future options unnecessarily. These errors lead to exponential backtracking, making large-scale problems computationally infeasible.

This paper proposes a dynamic planning and scheduling framework designed to provide "good advice" at every decision point, effectively minimizing or even eliminating the need for costly backtracking.

The Four-Corner Methodology

The core of the proposed approach is a cyclic, four-step methodology that balances task criticality with resource availability. This framework ensures that the most difficult parts of a problem are addressed first while preserving maximum flexibility for subsequent steps.

The four-corner planning and scheduling framework illustrating the cycle of task selection and resource assignment.
  1. Task Selection (Most-Constraint Policy): The system dynamically identifies the "most critical" task—the one with the lowest "survivability" given current resource competition. By tackling the hardest part of the problem first, the solver avoids being forced into impossible states later in the process.
  2. Solution Space Formulation: For the selected critical task, the system identifies all currently feasible resource assignments.
  3. Resource Assignment (Least-Impact Policy): The solver selects the resource that is "least crucial" to other tasks. This minimizes the negative impact on the remaining unassigned goals, preserving their flexibility.
  4. Constraint Propagation: Once a resource is assigned, the system updates the status of all related tasks and resources (the "domino effect"), generating a new agenda for the next cycle.

The innovation lies in the mathematical quantification of Criticality (how much a task is squeezed by its peers) and Cruciality (how much a specific choice squeezes others).

Experimental Evaluation: The N-Queens Problem

The methodology was evaluated using the N-queens problem, a classic benchmark for constraint satisfaction, with board sizes ranging from N=4 to N=100. The performance was compared against a "simple heuristic method" that selects the row with the fewest options and the column that maximizes future options.

Performance comparison on the N-queens problem showing (a) the number of backtracks and (b) the CPU time required for the proposed approach versus a simple heuristic.

Key Results

  • Backtrack-Free Performance: Using the proposed approach, no backtracking was required 76% of the time. Even in the most difficult cases, the maximum number of backtracks was only 13, with an average of less than 1.
  • Stability vs. Instability: While the simple heuristic method occasionally performed well, it was highly unstable. In several instances, it required over 1,000,000 backtracks for the same problems where the proposed method required none.
  • Computational Trade-off: As shown in Figure 2(b), the proposed method has higher computational overhead per step due to the need to recalculate criticality and cruciality. However, because it avoids the exponential time-sink of massive backtracking, its total execution time remains predictable and competitive as problem size increases.

Conclusion

By combining a "most-constraint" task selection policy with a "least-impact" resource assignment strategy, this framework provides a robust solution for complex CRPs. While the per-step CPU cost is higher, the dramatic reduction in backtracking leads to superior reliability and scalability. Future work focuses on parallelizing the criticality calculations to further reduce execution time and extending the model to more complex domains like VLSI switchbox routing and job-shop scheduling.

Summary updated

BibTeX
@inproceedings{keng1989planning,
  author = {Naiping Keng and David Y. Y. Yun},
  title = {{A Planning/Scheduling Methodology for the Constrained Resource Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure