Scheduling Example

📋

1. Problem Formulation

The Setup

We have 4 operations: A, B, C, D.
Constraints: B after A, D after C.
We want to find the optimal schedule (sequence of operations) to minimize cost.

graph TD Start((Start)) --> A Start --> C A --> B A --> C C --> A C --> D B --> C B --> D D --> A D --> B

DP Elements

States: Partial Schedules (e.g., {A}, {A,C}, {A,B}).
Controls: Decisions at Stage 0, 1, and 2 (which operation to do next).
Cost: Associated with each transition (arc).
Goal: Find the path with minimum total cost.

Strategy: Start from the last decision and go backwards!

2️⃣

2. Stage 2 (The End)

We look at the states where 3 operations are done, and we need to choose the last one.

Solving Stage 2

Solve the stage 2 sub-problems using terminal costs.
Record optimal cost-to-go and optimal decision for each state.

graph LR subgraph "Stage 2 Decisions" ABC -->|D| ABCD((End)) ABD -->|C| ABCD ACD -->|B| ABCD BCD -->|A| ABCD end style ABCD fill:#dcfce7,stroke:#16a34a

(Simplified view: From 3-op states to Done)

1️⃣

3. Stage 1 (Middle)

Now we step back. We are at states with 2 operations done. We choose the 3rd operation, knowing the optimal cost from Stage 2.

Solving Stage 1

For each state (e.g., AB, AC, CD...), consider all possible next operations.
Calculate Cost = (Immediate Cost) + (Optimal Cost from Stage 2).
Pick the minimum.

graph LR subgraph "Stage 1 Decisions" AB -->|C| ABC AB -->|D| ABD AC -->|B| ABC AC -->|D| ACD end style ABC fill:#fcd34d,stroke:#f59e0b style ABD fill:#fcd34d,stroke:#f59e0b style ACD fill:#fcd34d,stroke:#f59e0b

0️⃣

4. Stage 0 (Start)

Finally, we are at the start. We choose the 1st operation.

Solving Stage 0

Stage 0 problem is the entire problem.
Calculate Cost = (Immediate Cost) + (Optimal Cost from Stage 1).
The result is the global optimal cost \( J^* \).

graph LR subgraph "Stage 0 Decisions" Start((Start)) -->|A| A Start -->|C| C end style A fill:#fcd34d,stroke:#f59e0b style C fill:#fcd34d,stroke:#f59e0b

Forward Pass

Once we have \( J^* \) and the optimal decisions at each stage, we can construct the optimal sequence going forward from the start!

🧠

5. Recap: The DP Idea

Principle of Optimality

The tail of an optimal sequence is optimal for the tail subproblem.

DP Algorithm Idea

Solve all the tail subproblems of a given length using the solution of all the tail subproblems of shorter time length.