ferrox/scheduling/
greedy.rs

1use async_trait::async_trait;
2use converge_pack::{AgentEffect, Context, ContextKey, ProposedFact, Suggestor};
3use std::time::Instant;
4use tracing::warn;
5
6use super::problem::{SchedulingPlan, SchedulingRequest, TaskAssignment};
7
8pub(super) const REQUEST_PREFIX: &str = "scheduling-request:";
9const PLAN_PREFIX: &str = "scheduling-plan-greedy:";
10
11/// Schedules tasks via Earliest-Deadline-First + earliest-available skilled agent.
12///
13/// **Algorithm:** O(n·m·log n) where n = tasks, m = agents.
14///
15/// **When to use:** latency-sensitive pipelines where a good schedule is needed
16/// in microseconds. Use alongside [`CpSatSchedulerSuggestor`] in a Formation;
17/// the Engine will emit both plans and the highest-confidence one (CP-SAT optimal)
18/// will be accepted for execution.
19///
20/// **Confidence:** capped at 0.65 — greedy cannot prove optimality.
21///
22/// [`CpSatSchedulerSuggestor`]: super::cpsat::CpSatSchedulerSuggestor
23pub struct GreedySchedulerSuggestor;
24
25#[async_trait]
26impl Suggestor for GreedySchedulerSuggestor {
27    fn name(&self) -> &str {
28        "GreedySchedulerSuggestor"
29    }
30
31    fn dependencies(&self) -> &[ContextKey] {
32        &[ContextKey::Seeds]
33    }
34
35    fn complexity_hint(&self) -> Option<&'static str> {
36        Some(
37            "O(n·m·log n) — EDF + earliest-available; deterministic, sub-ms for n ≤ 10 000 tasks",
38        )
39    }
40
41    fn accepts(&self, ctx: &dyn Context) -> bool {
42        ctx.get(ContextKey::Seeds)
43            .iter()
44            .any(|f| f.id.starts_with(REQUEST_PREFIX) && !own_plan_exists(ctx, request_id(&f.id)))
45    }
46
47    async fn execute(&self, ctx: &dyn Context) -> AgentEffect {
48        let mut proposals = Vec::new();
49
50        for fact in ctx
51            .get(ContextKey::Seeds)
52            .iter()
53            .filter(|f| f.id.starts_with(REQUEST_PREFIX))
54        {
55            let rid = request_id(&fact.id);
56            if own_plan_exists(ctx, rid) {
57                continue;
58            }
59
60            match serde_json::from_str::<SchedulingRequest>(&fact.content) {
61                Ok(req) => {
62                    let plan = solve_greedy(&req);
63                    // Greedy is fast but can't prove optimality — cap confidence at 0.65.
64                    let confidence = (plan.throughput_ratio() * 0.65).min(0.65);
65                    proposals.push(
66                        ProposedFact::new(
67                            ContextKey::Strategies,
68                            format!("{PLAN_PREFIX}{rid}"),
69                            serde_json::to_string(&plan).unwrap_or_default(),
70                            self.name(),
71                        )
72                        .with_confidence(confidence),
73                    );
74                }
75                Err(e) => {
76                    warn!(id = %fact.id, error = %e, "malformed scheduling-request");
77                }
78            }
79        }
80
81        if proposals.is_empty() {
82            AgentEffect::empty()
83        } else {
84            AgentEffect::with_proposals(proposals)
85        }
86    }
87}
88
89fn request_id(fact_id: &str) -> &str {
90    fact_id.trim_start_matches(REQUEST_PREFIX)
91}
92
93fn own_plan_exists(ctx: &dyn Context, request_id: &str) -> bool {
94    let plan_id = format!("{PLAN_PREFIX}{request_id}");
95    ctx.get(ContextKey::Strategies)
96        .iter()
97        .any(|f| f.id == plan_id)
98}
99
100/// Pure EDF + earliest-available scheduling.  No OR-Tools dependency.
101pub fn solve_greedy(req: &SchedulingRequest) -> SchedulingPlan {
102    let t0 = Instant::now();
103
104    // Sort tasks by earliest deadline first.
105    let mut ordered: Vec<_> = req.tasks.iter().collect();
106    ordered.sort_by_key(|t| t.deadline_min);
107
108    let mut next_free = vec![0i64; req.agents.len()];
109    let mut assignments: Vec<TaskAssignment> = Vec::new();
110
111    for task in &ordered {
112        // Find capable agent whose earliest available time after release is smallest.
113        let best = req
114            .agents
115            .iter()
116            .filter(|a| a.capabilities.contains(&task.required_capability))
117            .min_by_key(|a| next_free[a.id].max(task.release_min));
118
119        if let Some(agent) = best {
120            let start = next_free[agent.id].max(task.release_min);
121            let end = start + task.duration_min;
122            if end <= task.deadline_min {
123                next_free[agent.id] = end;
124                assignments.push(TaskAssignment {
125                    task_id: task.id,
126                    task_name: task.name.clone(),
127                    agent_id: agent.id,
128                    agent_name: agent.name.clone(),
129                    start_min: start,
130                    end_min: end,
131                });
132            }
133        }
134    }
135
136    assignments.sort_by_key(|a| a.start_min);
137    let makespan = assignments.iter().map(|a| a.end_min).max().unwrap_or(0);
138    let scheduled = assignments.len();
139
140    SchedulingPlan {
141        request_id: req.id.clone(),
142        assignments,
143        tasks_total: req.tasks.len(),
144        tasks_scheduled: scheduled,
145        makespan_min: makespan,
146        solver: "greedy-edf".to_string(),
147        status: "feasible".to_string(),
148        wall_time_seconds: t0.elapsed().as_secs_f64(),
149    }
150}
ferrox/scheduling/greedy.rs

ferrox/scheduling/
greedy.rs
