Layered Defense Scheduling

Resource-Constrained Project Scheduling (RCPSP)

Coordinate detection, tracking, jamming, and interception across defense layers. Each step requires shared resources (radar dishes, weapon systems) with limited capacity. Schedule all activities to minimize total response time — a classical RCPSP, NP-hard due to the renewable resource constraints.

The Scenario

Defense Pipeline

Three alien threats must each pass through a 4-stage defense pipeline: Detect → Track → Jam → Intercept. Each stage requires shared resources: radar capacity (R₁=2) for detection and tracking, weapon capacity (R₂=2) for jamming and interception. With 10 activities competing for 2 resource types, the schedule is resource-constrained — activities may need to wait even if their predecessors are complete.

Defense Domain	OR Element	Symbol	Example
Detection scan	Activity	j	Detect-1
Scan duration	Processing time	pˇ	1 time unit
Detect before track	Precedence	(j,k)	Detect-1 → Track-1
Radar dishes	Resource k=1	R₁ = 2	2 radar units
Weapon systems	Resource k=2	R₂ = 2	2 weapon units
Total response time	Makespan	C_max	12 time units

MINIMIZE C_max subject to: Sˇ ≥ 0 ∀ j // non-negative start Sˇ + pˇ ≤ Sₖ ∀ (j,k) ∈ Prec // precedence Sˇ + pˇ ≤ C_max ∀ j // makespan def Σ{j: Sˇ≤t<Sˇ+pˇ} rˇₖ ≤ Rₖ ∀ k, ∀ t // resource capacity // NP-hard (Blazewicz et al. 1983) // Serial SGS: schedule activities one at a time in priority order, // starting each as early as resource availability allows

Interactive Solver

Schedule Generator

★★☆ Heuristic (Serial SGS)

10 Activities · 2 Resources · 3 Threat Chains

Chain 1: Detect→Track→Jam→Intercept. Chain 2: same. Chain 3: Detect→Track (partial engagement). Serial SGS schedules activities one at a time, choosing by priority rule.

Solution Methods

The Algorithms

Serial Schedule Generation Scheme (SGS)

O(n² · T) per schedule — n activities, T time horizon

The SGS builds a schedule by selecting one activity at a time from the set of eligible activities (all predecessors completed). The selected activity is scheduled at the earliest time where resource availability permits. The priority rule determines which eligible activity is selected first.

Compute eligible set: activities whose all predecessors are already scheduled
Among eligible, pick the one with highest priority (LFT or Most Successors)
Find earliest start time where all required resources are available
Schedule the activity; update resource profiles
Repeat until all activities scheduled

LFT Priority: Latest Finish Time

Prioritize activities with the latest allowable finish time (from backward pass)

Activities on or near the critical path get high priority because delaying them directly increases makespan. LFT is one of the most effective single-pass priority rules for RCPSP (Kolisch & Hartmann, 2006).

Most Successors Priority

Prioritize activities with the most downstream dependents

Activities with many successors should be scheduled early because delays propagate through the precedence graph. This rule tends to front-load the critical-path activities.

References

Published Brucker, P., Drexl, A., Möhring, R., Neumann, K., & Pesch, E. (1999). “Resource-constrained project scheduling: Notation, classification, models, and methods.” European Journal of Operational Research, 112(1), 3–41.

Published Kolisch, R. & Hartmann, S. (2006). “Experimental investigation of heuristics for resource-constrained project scheduling.” European Journal of Operational Research, 168(1), 17–37.

Published Pinedo, M.L. (2016). Scheduling: Theory, Algorithms, and Systems, 5th ed. Springer.

Preparing for First Contact

If the aliens arrive, we suspect you will not be visiting a GitHub Pages site. We do recommend the Hungarian algorithm. It works on any planet.

All Defense Applications GitHub

👽🛸⚠️

Educational Fiction Disclaimer

This is a fictional educational scenario.

All data and parameters are entirely fictional
No military applications intended
The author advocates for peace