[Model] SequencingToMinimizeMaximumCumulativeCost

[isPANN]

Motivation

SEQUENCING TO MINIMIZE MAXIMUM CUMULATIVE COST (P191) from Garey & Johnson, A5 SS7. A precedence-constrained single-processor scheduling problem where each task has an integer cost (possibly negative, representing a "profit"), and the goal is to order tasks so that the running total of costs never exceeds a given bound K. NP-complete even when costs are restricted to {−1, 0, 1} (via reduction from REGISTER SUFFICIENCY, R137). Can be solved in polynomial time if the precedence order is series-parallel.

Associated rules:

• R137: REGISTER SUFFICIENCY → Sequencing to Minimize Maximum Cumulative Cost (this model is the target)

Definition

Name: SequencingToMinimizeMaximumCumulativeCost

Reference: Garey & Johnson, Computers and Intractability, A5 SS7

Mathematical definition:

INSTANCE: Set T of tasks, partial order < on T, a "cost" c(t) ∈ Z for each t ∈ T (if c(t) < 0, it can be viewed as a "profit"), and a constant K ∈ Z.
QUESTION: Is there a one-processor schedule σ for T that obeys the precedence constraints and which has the property that, for every task t ∈ T, the sum of the costs for all tasks t' with σ(t') ≤ σ(t) is at most K?

Variables

• Count: n = |T| (one variable per task, representing its position in the schedule)
• Per-variable domain: {0, 1, ..., n−1} — the position index of the task in a topological ordering
• Meaning: π(i) ∈ {0, ..., n−1} gives the position of task t_i in a linear extension of the partial order. The schedule must be a topological sort of the precedence DAG. At each position j, the cumulative cost Σ_{k≤j} c(t_{π^{-1}(k)}) must not exceed K.

Schema (data type)

Type name: SequencingToMinimizeMaximumCumulativeCost
Variants: none (no type parameters)

Field	Type	Description
costs	Vec<i64>	Cost c(t) for each task t ∈ T (may be negative)
predecessors	Vec<Vec<usize>>	For each task, list of tasks that must precede it
bound	i64	Upper bound K on maximum cumulative cost

Complexity

• Best known exact algorithm: The problem is NP-complete, even with costs restricted to {−1, 0, 1} [Abdel-Wahab, 1976]. It can be solved in polynomial time when the precedence order is series-parallel [Abdel-Wahab & Kameda, 1978; Monma & Sidney, 1977]. For general precedence constraints, exact algorithms use branch-and-bound or enumerate topological orderings. A dynamic programming approach over the lattice of antichains gives O*(2^w) where w is the width of the partial order (maximum antichain size). The brute-force complexity is O(n! · n) for enumerating all topological orderings.

Extra Remark

Full book text:

INSTANCE: Set T of tasks, partial order < on T, a "cost" c(t) ∈ Z for each t ∈ T (if c(t) < 0, it can be viewed as a "profit"), and a constant K ∈ Z.
QUESTION: Is there a one-processor schedule σ for T that obeys the precedence constraints and which has the property that, for every task t ∈ T, the sum of the costs for all tasks t' with σ(t') ≤ σ(t) is at most K?

Reference: [Abdel-Wahab, 1976]. Transformation from REGISTER SUFFICIENCY.

Comment: Remains NP-complete even if c(t) ∈ {-1,0,1} for all t ∈ T. Can be solved in polynomial time if < is series-parallel [Abdel-Wahab and Kameda, 1978], [Monma and Sidney, 1977].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all topological orderings of the precedence DAG; compute cumulative costs along each ordering; check if max cumulative cost ≤ K.)
• It can be solved by reducing to integer programming. (Binary ILP: x_{ij} ∈ {0,1} = task i at position j; enforce topological order constraints; compute cumulative cost at each position; add constraint that each cumulative sum ≤ K.)
• Other: Polynomial algorithm for series-parallel precedence [Abdel-Wahab & Kameda, 1978].

Example Instance

Input:
T = {t_1, t_2, t_3, t_4, t_5, t_6} (n = 6 tasks)
Costs: c = [2, −1, 3, −2, 1, −3]
Precedence constraints (DAG edges):

• t_1 < t_3 (t_1 must precede t_3)
• t_2 < t_3
• t_2 < t_4
• t_3 < t_5
• t_4 < t_6
• t_5 < t_6
  Bound K = 4.

Feasible schedule (topological order):
Order: t_2, t_1, t_4, t_3, t_5, t_6
Cumulative costs:

• After t_2: −1
• After t_1: −1 + 2 = 1
• After t_4: 1 + (−2) = −1
• After t_3: −1 + 3 = 2
• After t_5: 2 + 1 = 3
• After t_6: 3 + (−3) = 0

Maximum cumulative cost = 3 ≤ K = 4 ✓

Alternative (worse) order: t_1, t_2, t_3, t_4, t_5, t_6
Cumulative: 2, 1, 4, 2, 3, 0. Max = 4 ≤ K = 4 ✓ (just barely feasible).

Infeasible order for K = 3: t_1, t_2, t_3, t_4, t_5, t_6 has max cumulative = 4 > 3.

Answer: YES — a valid schedule with max cumulative cost ≤ K = 4 exists.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints (precedence + cumulative cost bound) from all existing problems
Correctness	⚠️ Warn	Monma & Sidney date is 1979, not 1977; complexity section lacks concrete algorithm bound
Well-written	⚠️ Warn	Name is extremely long; no concrete complexity string for declare_variants!; permutation encoding needs clarification

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The problem does not exist in the current codebase. It is a scheduling/sequencing decision problem from Garey & Johnson (A5 SS7) with at least one planned reduction (from Register Sufficiency). This adds a new node to the reduction graph in the scheduling domain, which is currently unrepresented. Pass.

Non-trivial

This is a genuinely distinct problem. The feasibility constraint combines precedence constraints (partial order on tasks) with a cumulative cost bound (running sum must never exceed K). No existing problem in the codebase has this structure — the closest problems are either graph-based (MIS, MaxCut) or set-based (SetCovering). The input structure (DAG + costs + bound) is unique. Pass.

Correctness

• Abdel-Wahab (1976): Verified. H. M. Abdel-Wahab's 1976 PhD thesis "Scheduling with Application to Register Allocation and Deadlock Problems" at the University of Waterloo established NP-completeness of this problem. ✅
• Abdel-Wahab & Kameda (1978): Verified. Published in Operations Research 26(1), 141–158 (1978). Gives polynomial-time algorithm for series-parallel precedence constraints. ✅
• Monma & Sidney (1977): ⚠️ The actual publication is 1979, not 1977. The paper is "Sequencing with Series-Parallel Precedence Constraints" in Mathematics of Operations Research 4(3), 215–224 (1979). The year should be corrected.
• Complexity section: The issue says "A dynamic programming approach over the lattice of antichains gives O*(2^w)" but does not provide a specific citation for this claim, nor a concrete complexity string suitable for declare_variants!. The brute-force bound O(n! · n) is mentioned but no best-known exact algorithm with a precise exponential base is given.

Well-written

Mostly complete, with some issues:

1. Name length: SequencingToMinimizeMaximumCumulativeCost is 43 characters. While technically valid, this is unusually long. Consider a shorter alias if the project conventions allow it.

2. No concrete complexity string: The declare_variants! macro requires a concrete expression like "2^num_tasks" or "num_tasks!". The current description is narrative rather than a parseable expression. The O*(2^w) bound (where w = width of the partial order) would need a getter method like num_tasks and a way to express the antichain width.

3. Variables section: The encoding uses permutations (each variable takes values 0..n-1), which means dims() would return [n, n, ..., n] (n copies of n). This is valid but should be explicitly stated. The brute-force solver would enumerate n^n configurations rather than n! permutations, which is much larger. This may need special handling or documentation.

4. Schema field predecessors: The field stores predecessors as Vec<Vec<usize>>, which is a standard adjacency list for a DAG. This is reasonable.

5. Example: The example is well-constructed with 6 tasks, shows both a feasible and an infeasible schedule, and is hand-verifiable. ✅

6. All template sections present: Motivation ✅, Name ✅, Reference ✅, Definition ✅, Variables ✅, Schema ✅, Complexity ⚠️ (narrative only), How to solve ✅, Example ✅.

Recommendations

• Fix the Monma & Sidney citation year from 1977 to 1979.
• Add a concrete complexity string for declare_variants! (e.g., "num_tasks!" for brute-force, or find and cite a better exact algorithm).
• Clarify how the permutation encoding interacts with dims() and the brute-force solver.