Skip to main content

Capstone: A Scheduling Optimizer With a Budget

Build a command-line planning tool for one exclusive resource. Each job has a stable ID, integer start/finish, signed profit and positive integer cost. Time intervals are half-open and must have start < finish. Jobs are indivisible and can be selected at most once; empty schedules are allowed. This is a synthetic planning model, not a claim about a particular production scheduler.

Estimated effort: 7–10 hours after the core labs. Reuse your own reviewed interval solver, then implement the budget extension. Preserve a baseline and a changed- requirement decision record.

Stage 1: weighted compatibility​

Implement maximum-profit selection without a budget. Sort internally by finish while preserving original IDs. Compute the compatible predecessor prefix with finish <= start, then derive take/skip tabulation and reconstruction. Return profit and selected IDs in chronological order. Reject invalid input and verify all reported IDs, nonoverlap, uniqueness and recomputed profit independently.

Fixture: A=(0,2,3,cost=1), B=(2,4,3,cost=1), C=(0,4,7,cost=3). Unbudgeted optimum is C for profit 7. Earliest-finish cardinality greedy chooses A,B for profit 6; use this to explain why the objective requires a different proof.

Stage 2: add a total budget​

Budget B is a nonnegative integer. Selected costs must sum to at most B. For budget 2 on the fixture, C is infeasible; A,B give optimum 6. The old prefix-only best value hides how much budget its schedule consumed.

Let D(i,b) be best profit from the first i finish-sorted jobs with budget at most b. Skip reads D(i-1,b). If job i-1 costs c<=b, take reads profit[i-1]+D(p(i-1),b-c), where p is a compatible prefix count. Bases for no jobs are zero at every b. Prove that a taken job's predecessors are all compatible and that taking/skipping covers every schedule.

Retain full states for reconstruction or justify another strategy. Keeping only the previous prefix row is not enough: p can refer much farther back. Derive O(n log(n+1)+n(B+1)) arithmetic work and O((n+1)(B+1)) full-table storage, plus numeric and output costs. Explain why the budget dimension is pseudo-polynomial.

Stage 3: independent verification​

Enumerate all subsets for tiny job sets, filtering by both nonoverlap and budget, then compare the best profit. Independently validate the chosen schedule even when its scalar value matches the oracle. Include touching boundaries, ties, duplicate-valued distinct jobs, all-negative profits, zero budget, an over-budget job, input permutation, and a case whose take predecessor is several rows earlier.

Useful properties: increasing budget cannot reduce the optimum; permuting input does not change optimal profit; adding an infeasible over-budget job cannot improve it. These properties supplement the oracle but do not prove optimality. Document stable IDs so permutation tests compare identity correctly.

Deliverables and acceptance​

  • A runnable CLI and documented input/output examples for both stages.
  • State cards, both proofs, reconstruction explanation and resource estimates.
  • Tiny exhaustive optimum checks plus an independent output validator.
  • A design note showing how the new budget invalidates the old state.
  • One measured run with environment, input size, included work and memory method; a separate statement of untested scale and limitations.

Accept any optimum satisfying the contract. Reject illegal schedules, hidden greedy substitutions and unsupported performance claims. Explain additional requirements before implementation: multiple resources, preemption, travel times, dependencies or stochastic durations are not automatically covered by this model. Use C7/C8 for review and a fresh changed constraint after 7–14 days.