MILP Task Scheduling for Federated Fog
A Mixed-Integer Linear Program in Pyomo that places DAG tasks across federated fog nodes to hit a deadline, paired with a greedy heuristic that holds up at 1,000 tasks where the exact solver stops finishing. Published at IEEE Cloud Summit 2025, Washington, D.C.
DAG workflow → MILP partition (Pyomo) → Federated fog nodes → Greedy fallback at scale
Decisions
Optimal, then honest about it
The MILP guarantees optimal task placement, but scheduling interdependent tasks across heterogeneous fogs is NP-hard. It stops being usable somewhere past 100 tasks.
A greedy heuristic for scale
Assign each task to the fog with the earliest finish time, respecting dependencies and communication delay. Lower per-task accuracy, but it holds up at 1,000 tasks.
Measure the trade-off, don't assume it
We swept slack, fog-node count, and DAG size to map exactly where optimal stops being worth the compute. That curve is the actual contribution.
Provably optimal and actually usable are different objectives. The paper's real result is the line where one stops being worth the other.
— Amisha
Python · Pyomo · MILP · DAG scheduling