converge_optimization/scheduling/
mod.rs

1//! Scheduling algorithms and constraints
2//!
3//! This module provides scheduling primitives that can be used
4//! with constraint solvers or standalone heuristics.
5//!
6//! ## Concepts
7//!
8//! - **Interval**: A task with start, duration, and end
9//! - **Disjunctive**: Tasks that cannot overlap (single resource)
10//! - **Cumulative**: Tasks sharing resource capacity
11
12use crate::Result;
13use serde::{Deserialize, Serialize};
14
15/// An interval (task) in a schedule
16#[derive(Debug, Clone, Serialize, Deserialize)]
17pub struct Interval {
18    /// Interval identifier
19    pub id: usize,
20    /// Earliest start time
21    pub earliest_start: i64,
22    /// Latest end time
23    pub latest_end: i64,
24    /// Duration (fixed for now)
25    pub duration: i64,
26    /// Resource consumption (for cumulative)
27    pub demand: i64,
28}
29
30impl Interval {
31    /// Create a new interval
32    pub fn new(id: usize, earliest_start: i64, latest_end: i64, duration: i64) -> Self {
33        Self {
34            id,
35            earliest_start,
36            latest_end,
37            duration,
38            demand: 1,
39        }
40    }
41
42    /// Create interval with resource demand
43    pub fn with_demand(mut self, demand: i64) -> Self {
44        self.demand = demand;
45        self
46    }
47
48    /// Latest possible start time
49    pub fn latest_start(&self) -> i64 {
50        self.latest_end - self.duration
51    }
52
53    /// Earliest possible end time
54    pub fn earliest_end(&self) -> i64 {
55        self.earliest_start + self.duration
56    }
57
58    /// Check if interval can be scheduled
59    pub fn is_feasible(&self) -> bool {
60        self.earliest_start + self.duration <= self.latest_end
61    }
62}
63
64/// A scheduled interval (with assigned start time)
65#[derive(Debug, Clone, Serialize, Deserialize)]
66pub struct ScheduledInterval {
67    /// The interval
68    pub interval: Interval,
69    /// Assigned start time
70    pub start: i64,
71}
72
73impl ScheduledInterval {
74    /// End time of scheduled interval
75    pub fn end(&self) -> i64 {
76        self.start + self.interval.duration
77    }
78}
79
80/// A scheduling problem
81#[derive(Debug, Clone, Serialize, Deserialize)]
82pub struct SchedulingProblem {
83    /// Tasks to schedule
84    pub intervals: Vec<Interval>,
85    /// Resource capacity (for cumulative)
86    pub capacity: i64,
87    /// Whether tasks are disjunctive (no overlap)
88    pub disjunctive: bool,
89}
90
91impl SchedulingProblem {
92    /// Create a disjunctive scheduling problem
93    pub fn disjunctive(intervals: Vec<Interval>) -> Self {
94        Self {
95            intervals,
96            capacity: 1,
97            disjunctive: true,
98        }
99    }
100
101    /// Create a cumulative scheduling problem
102    pub fn cumulative(intervals: Vec<Interval>, capacity: i64) -> Self {
103        Self {
104            intervals,
105            capacity,
106            disjunctive: false,
107        }
108    }
109}
110
111/// Solution to a scheduling problem
112#[derive(Debug, Clone, Serialize, Deserialize)]
113pub struct SchedulingSolution {
114    /// Scheduled intervals with start times
115    pub schedule: Vec<ScheduledInterval>,
116    /// Makespan (latest end time)
117    pub makespan: i64,
118}
119
120/// Simple list scheduling heuristic for disjunctive problems
121pub fn list_schedule(problem: &SchedulingProblem) -> Result<SchedulingSolution> {
122    let mut schedule = Vec::new();
123    let mut current_time = 0i64;
124
125    // Sort by earliest start (EDD - Earliest Due Date variant)
126    let mut intervals = problem.intervals.clone();
127    intervals.sort_by_key(|i| i.earliest_start);
128
129    for interval in intervals {
130        // Find earliest feasible start
131        let start = current_time.max(interval.earliest_start);
132
133        if start + interval.duration > interval.latest_end {
134            return Err(crate::Error::infeasible(format!(
135                "Interval {} cannot be scheduled within time window",
136                interval.id
137            )));
138        }
139
140        schedule.push(ScheduledInterval {
141            start,
142            interval: interval.clone(),
143        });
144
145        if problem.disjunctive {
146            current_time = start + interval.duration;
147        }
148    }
149
150    let makespan = schedule.iter().map(|s| s.end()).max().unwrap_or(0);
151
152    Ok(SchedulingSolution { schedule, makespan })
153}
154
155#[cfg(test)]
156mod tests {
157    use super::*;
158
159    #[test]
160    fn test_simple_disjunctive() {
161        let intervals = vec![
162            Interval::new(0, 0, 100, 10),
163            Interval::new(1, 0, 100, 20),
164            Interval::new(2, 0, 100, 15),
165        ];
166
167        let problem = SchedulingProblem::disjunctive(intervals);
168        let solution = list_schedule(&problem).unwrap();
169
170        assert_eq!(solution.schedule.len(), 3);
171        assert_eq!(solution.makespan, 45); // 10 + 20 + 15
172    }
173
174    #[test]
175    fn test_interval_feasibility() {
176        let interval = Interval::new(0, 0, 10, 5);
177        assert!(interval.is_feasible());
178
179        let infeasible = Interval::new(0, 0, 3, 5);
180        assert!(!infeasible.is_feasible());
181    }
182}
converge_optimization/scheduling/mod.rs

converge_optimization/scheduling/
mod.rs
