u_schedule/models/
time_constraints.rs

1//! Time constraints and duration estimation for scheduling.
2//!
3//! Provides constraint-oriented time boundaries (hard/soft deadlines,
4//! release times), violation tracking, PERT three-point estimation,
5//! and probabilistic duration distributions.
6//!
7//! # Concepts
8//!
9//! - [`ActivityTimeConstraint`]: Scheduling-level time boundary (different
10//!   from calendar [`TimeWindow`](super::TimeWindow) which models availability)
11//! - [`TimeWindowViolation`]: Result of checking an activity against its constraint
12//! - [`PertEstimate`]: PERT three-point duration estimation (O, M, P)
13//! - [`DurationDistribution`]: Probabilistic duration model
14//!
15//! # References
16//!
17//! - Malcolm et al. (1959), "Application of a technique for R&D program evaluation" (PERT)
18//! - Pinedo (2016), "Scheduling: Theory, Algorithms, and Systems"
19
20use serde::{Deserialize, Serialize};
21
22// ================================
23// Time Constraint (Hard/Soft)
24// ================================
25
26/// Time constraint type.
27#[derive(Debug, Clone, Copy, Default, Serialize, Deserialize, PartialEq, Eq)]
28pub enum ConstraintType {
29    /// Must be satisfied (schedule invalid if violated).
30    Hard,
31    /// Should be satisfied (penalty if violated).
32    #[default]
33    Soft,
34}
35
36/// Time constraint for an activity.
37///
38/// Unlike calendar [`TimeWindow`](super::TimeWindow) (which models resource
39/// availability), this struct represents scheduling-level boundaries:
40/// earliest/latest start and end times, optionally with penalties.
41///
42/// # Examples
43///
44/// ```
45/// use u_schedule::models::time_constraints::{ActivityTimeConstraint, ConstraintType};
46///
47/// // Hard deadline: must finish by 5000 ms
48/// let c = ActivityTimeConstraint::deadline(5000);
49/// assert!(c.check_violation(0, 4000).is_none());
50/// assert!(c.check_violation(0, 6000).is_some());
51/// ```
52#[derive(Debug, Clone, Serialize, Deserialize)]
53pub struct ActivityTimeConstraint {
54    /// Earliest allowed start time (ms).
55    pub earliest_start_ms: Option<i64>,
56    /// Latest allowed start time (ms).
57    pub latest_start_ms: Option<i64>,
58    /// Earliest allowed end time (ms).
59    pub earliest_end_ms: Option<i64>,
60    /// Latest allowed end time (ms) — due date.
61    pub latest_end_ms: Option<i64>,
62    /// Hard or soft constraint.
63    pub constraint_type: ConstraintType,
64    /// Penalty per millisecond of violation (for soft constraints).
65    pub penalty_per_ms: f64,
66}
67
68impl ActivityTimeConstraint {
69    /// Creates an empty (unconstrained) time constraint.
70    pub fn new() -> Self {
71        Self {
72            earliest_start_ms: None,
73            latest_start_ms: None,
74            earliest_end_ms: None,
75            latest_end_ms: None,
76            constraint_type: ConstraintType::Soft,
77            penalty_per_ms: 1.0,
78        }
79    }
80
81    /// Creates a constraint with start/end boundaries.
82    pub fn bounded(start_ms: i64, end_ms: i64) -> Self {
83        Self {
84            earliest_start_ms: Some(start_ms),
85            latest_end_ms: Some(end_ms),
86            ..Self::new()
87        }
88    }
89
90    /// Creates a hard deadline (must complete by).
91    pub fn deadline(deadline_ms: i64) -> Self {
92        Self {
93            latest_end_ms: Some(deadline_ms),
94            constraint_type: ConstraintType::Hard,
95            penalty_per_ms: 0.0,
96            ..Self::new()
97        }
98    }
99
100    /// Creates a release time (cannot start before).
101    pub fn release(release_ms: i64) -> Self {
102        Self {
103            earliest_start_ms: Some(release_ms),
104            constraint_type: ConstraintType::Hard,
105            penalty_per_ms: 0.0,
106            ..Self::new()
107        }
108    }
109
110    /// Sets as hard constraint.
111    pub fn hard(mut self) -> Self {
112        self.constraint_type = ConstraintType::Hard;
113        self.penalty_per_ms = 0.0;
114        self
115    }
116
117    /// Sets as soft constraint with penalty.
118    pub fn soft(mut self, penalty_per_ms: f64) -> Self {
119        self.constraint_type = ConstraintType::Soft;
120        self.penalty_per_ms = penalty_per_ms;
121        self
122    }
123
124    /// Sets earliest start.
125    pub fn with_earliest_start(mut self, ms: i64) -> Self {
126        self.earliest_start_ms = Some(ms);
127        self
128    }
129
130    /// Sets latest start.
131    pub fn with_latest_start(mut self, ms: i64) -> Self {
132        self.latest_start_ms = Some(ms);
133        self
134    }
135
136    /// Sets latest end (due date).
137    pub fn with_due_date(mut self, ms: i64) -> Self {
138        self.latest_end_ms = Some(ms);
139        self
140    }
141
142    /// Checks if a scheduled time violates the constraint.
143    ///
144    /// Returns `None` if no violation, or a [`TimeWindowViolation`] with details.
145    pub fn check_violation(&self, start_ms: i64, end_ms: i64) -> Option<TimeWindowViolation> {
146        let mut total_early_ms = 0i64;
147        let mut total_late_ms = 0i64;
148
149        if let Some(earliest) = self.earliest_start_ms {
150            if start_ms < earliest {
151                total_early_ms += earliest - start_ms;
152            }
153        }
154        if let Some(latest) = self.latest_start_ms {
155            if start_ms > latest {
156                total_late_ms += start_ms - latest;
157            }
158        }
159        if let Some(earliest) = self.earliest_end_ms {
160            if end_ms < earliest {
161                total_early_ms += earliest - end_ms;
162            }
163        }
164        if let Some(latest) = self.latest_end_ms {
165            if end_ms > latest {
166                total_late_ms += end_ms - latest;
167            }
168        }
169
170        if total_early_ms == 0 && total_late_ms == 0 {
171            return None;
172        }
173
174        Some(TimeWindowViolation {
175            early_ms: total_early_ms,
176            late_ms: total_late_ms,
177            severity: if self.constraint_type == ConstraintType::Hard {
178                ViolationSeverity::Critical
179            } else {
180                ViolationSeverity::Minor
181            },
182            penalty: (total_early_ms + total_late_ms) as f64 * self.penalty_per_ms,
183        })
184    }
185}
186
187impl Default for ActivityTimeConstraint {
188    fn default() -> Self {
189        Self::new()
190    }
191}
192
193// ================================
194// Violation Model
195// ================================
196
197/// Severity of a constraint violation.
198#[derive(Debug, Clone, Copy, Serialize, Deserialize, PartialEq, Eq, PartialOrd, Ord)]
199pub enum ViolationSeverity {
200    /// Informational — no impact.
201    Info,
202    /// Minor — small penalty.
203    Minor,
204    /// Major — significant penalty.
205    Major,
206    /// Critical — schedule may be invalid.
207    Critical,
208}
209
210/// Time constraint violation details.
211#[derive(Debug, Clone, Serialize, Deserialize)]
212pub struct TimeWindowViolation {
213    /// Amount of time too early (ms).
214    pub early_ms: i64,
215    /// Amount of time too late (ms).
216    pub late_ms: i64,
217    /// Severity level.
218    pub severity: ViolationSeverity,
219    /// Calculated penalty value.
220    pub penalty: f64,
221}
222
223impl TimeWindowViolation {
224    /// Total violation time (absolute).
225    pub fn total_violation_ms(&self) -> i64 {
226        self.early_ms.abs() + self.late_ms.abs()
227    }
228
229    /// Whether this is a tardiness (late) violation.
230    pub fn is_tardy(&self) -> bool {
231        self.late_ms > 0
232    }
233
234    /// Whether this is an early start violation.
235    pub fn is_early(&self) -> bool {
236        self.early_ms > 0
237    }
238}
239
240/// General constraint violation.
241#[derive(Debug, Clone, Serialize, Deserialize)]
242pub struct ConstraintViolation {
243    /// Type of violation.
244    pub violation_type: ConstraintViolationType,
245    /// Related entity IDs.
246    pub related_ids: Vec<String>,
247    /// Severity level.
248    pub severity: ViolationSeverity,
249    /// Violation message.
250    pub message: String,
251    /// Penalty value.
252    pub penalty: f64,
253}
254
255/// Types of constraint violations.
256#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
257pub enum ConstraintViolationType {
258    /// Time constraint violated.
259    TimeWindow,
260    /// Resource capacity exceeded.
261    CapacityExceeded,
262    /// Precedence constraint violated.
263    PrecedenceViolated,
264    /// Resource unavailable.
265    ResourceUnavailable,
266    /// Skill requirement not met.
267    SkillMismatch,
268    /// Other custom violation.
269    Custom(String),
270}
271
272impl ConstraintViolation {
273    /// Creates a time constraint violation.
274    pub fn time_window(
275        activity_id: &str,
276        tardiness_ms: i64,
277        severity: ViolationSeverity,
278        penalty: f64,
279    ) -> Self {
280        Self {
281            violation_type: ConstraintViolationType::TimeWindow,
282            related_ids: vec![activity_id.to_string()],
283            severity,
284            message: format!("Activity {} is {} ms late", activity_id, tardiness_ms),
285            penalty,
286        }
287    }
288
289    /// Creates a capacity violation.
290    pub fn capacity_exceeded(resource_id: &str, exceeded_by: i32) -> Self {
291        Self {
292            violation_type: ConstraintViolationType::CapacityExceeded,
293            related_ids: vec![resource_id.to_string()],
294            severity: ViolationSeverity::Critical,
295            message: format!(
296                "Resource {} capacity exceeded by {}",
297                resource_id, exceeded_by
298            ),
299            penalty: exceeded_by as f64 * 1000.0,
300        }
301    }
302
303    /// Creates a precedence violation.
304    pub fn precedence_violated(before_id: &str, after_id: &str, overlap_ms: i64) -> Self {
305        Self {
306            violation_type: ConstraintViolationType::PrecedenceViolated,
307            related_ids: vec![before_id.to_string(), after_id.to_string()],
308            severity: ViolationSeverity::Critical,
309            message: format!(
310                "Activity {} must complete before {} (overlap: {} ms)",
311                before_id, after_id, overlap_ms
312            ),
313            penalty: overlap_ms as f64 * 10.0,
314        }
315    }
316}
317
318// ================================
319// PERT 3-Point Estimation
320// ================================
321
322/// PERT (Program Evaluation and Review Technique) duration estimation.
323///
324/// Uses three-point estimation:
325/// - Optimistic (O): Best-case scenario
326/// - Most Likely (M): Normal conditions
327/// - Pessimistic (P): Worst-case scenario
328///
329/// Mean = (O + 4M + P) / 6, StdDev = (P - O) / 6
330///
331/// # References
332///
333/// Malcolm et al. (1959), Clark (1962)
334#[derive(Debug, Clone, Default, Serialize, Deserialize)]
335pub struct PertEstimate {
336    /// Optimistic duration (ms).
337    pub optimistic_ms: i64,
338    /// Most likely duration (ms).
339    pub most_likely_ms: i64,
340    /// Pessimistic duration (ms).
341    pub pessimistic_ms: i64,
342}
343
344impl PertEstimate {
345    /// Creates a new PERT estimate.
346    pub fn new(optimistic_ms: i64, most_likely_ms: i64, pessimistic_ms: i64) -> Self {
347        Self {
348            optimistic_ms,
349            most_likely_ms,
350            pessimistic_ms,
351        }
352    }
353
354    /// Creates from percentage variance.
355    ///
356    /// E.g., `from_variance(1000, 0.2)` creates O=800, M=1000, P=1200.
357    pub fn from_variance(base_ms: i64, variance_ratio: f64) -> Self {
358        let variance = (base_ms as f64 * variance_ratio) as i64;
359        Self {
360            optimistic_ms: base_ms - variance,
361            most_likely_ms: base_ms,
362            pessimistic_ms: base_ms + variance,
363        }
364    }
365
366    /// Creates symmetric estimate.
367    pub fn symmetric(most_likely_ms: i64, spread_ms: i64) -> Self {
368        Self {
369            optimistic_ms: most_likely_ms - spread_ms,
370            most_likely_ms,
371            pessimistic_ms: most_likely_ms + spread_ms,
372        }
373    }
374
375    /// PERT mean (expected duration): `(O + 4M + P) / 6`.
376    pub fn mean_ms(&self) -> f64 {
377        (self.optimistic_ms as f64 + 4.0 * self.most_likely_ms as f64 + self.pessimistic_ms as f64)
378            / 6.0
379    }
380
381    /// PERT standard deviation: `(P - O) / 6`.
382    pub fn std_dev_ms(&self) -> f64 {
383        (self.pessimistic_ms - self.optimistic_ms) as f64 / 6.0
384    }
385
386    /// Variance.
387    pub fn variance_ms(&self) -> f64 {
388        let sd = self.std_dev_ms();
389        sd * sd
390    }
391
392    /// Duration at specified confidence level.
393    ///
394    /// Uses normal approximation via `u_numflow::special::inverse_normal_cdf`.
395    pub fn duration_at_confidence(&self, confidence: f64) -> i64 {
396        let z = u_numflow::special::inverse_normal_cdf(confidence);
397        (self.mean_ms() + z * self.std_dev_ms()) as i64
398    }
399
400    /// Probability of completing within given duration.
401    ///
402    /// Uses `u_numflow::special::standard_normal_cdf`.
403    pub fn probability_of_completion(&self, duration_ms: i64) -> f64 {
404        let z = (duration_ms as f64 - self.mean_ms()) / self.std_dev_ms();
405        u_numflow::special::standard_normal_cdf(z)
406    }
407
408    /// 50th percentile (median) duration.
409    pub fn p50(&self) -> i64 {
410        self.mean_ms() as i64
411    }
412
413    /// 85th percentile duration.
414    pub fn p85(&self) -> i64 {
415        self.duration_at_confidence(0.85)
416    }
417
418    /// 95th percentile duration.
419    pub fn p95(&self) -> i64 {
420        self.duration_at_confidence(0.95)
421    }
422}
423
424// ================================
425// Duration Distribution
426// ================================
427
428/// Duration distribution for probabilistic scheduling.
429#[derive(Debug, Clone, Serialize, Deserialize)]
430pub enum DurationDistribution {
431    /// Fixed duration (deterministic).
432    Fixed(i64),
433    /// PERT-based distribution.
434    Pert(PertEstimate),
435    /// Uniform distribution between min and max.
436    Uniform { min_ms: i64, max_ms: i64 },
437    /// Triangular distribution.
438    Triangular {
439        min_ms: i64,
440        mode_ms: i64,
441        max_ms: i64,
442    },
443    /// Log-normal (common for task durations).
444    LogNormal { mu: f64, sigma: f64 },
445}
446
447impl DurationDistribution {
448    /// Expected (mean) duration.
449    pub fn expected_duration_ms(&self) -> f64 {
450        match self {
451            Self::Fixed(d) => *d as f64,
452            Self::Pert(p) => p.mean_ms(),
453            Self::Uniform { min_ms, max_ms } => (*min_ms + *max_ms) as f64 / 2.0,
454            Self::Triangular {
455                min_ms,
456                mode_ms,
457                max_ms,
458            } => (*min_ms + *mode_ms + *max_ms) as f64 / 3.0,
459            Self::LogNormal { mu, sigma } => (mu + sigma.powi(2) / 2.0).exp(),
460        }
461    }
462
463    /// Duration at confidence level.
464    pub fn duration_at_confidence(&self, confidence: f64) -> i64 {
465        match self {
466            Self::Fixed(d) => *d,
467            Self::Pert(p) => p.duration_at_confidence(confidence),
468            Self::Uniform { min_ms, max_ms } => {
469                let range = max_ms - min_ms;
470                min_ms + (range as f64 * confidence) as i64
471            }
472            Self::Triangular {
473                min_ms,
474                mode_ms,
475                max_ms,
476            } => {
477                let fc = (*mode_ms - *min_ms) as f64 / (*max_ms - *min_ms) as f64;
478                if confidence < fc {
479                    *min_ms
480                        + ((*max_ms - *min_ms) as f64 * (*mode_ms - *min_ms) as f64 * confidence)
481                            .sqrt() as i64
482                } else {
483                    *max_ms
484                        - ((*max_ms - *min_ms) as f64
485                            * (*max_ms - *mode_ms) as f64
486                            * (1.0 - confidence))
487                            .sqrt() as i64
488                }
489            }
490            Self::LogNormal { mu, sigma } => {
491                let z = u_numflow::special::inverse_normal_cdf(confidence);
492                (mu + z * sigma).exp() as i64
493            }
494        }
495    }
496
497    /// Creates from PERT estimates.
498    pub fn from_pert(optimistic: i64, most_likely: i64, pessimistic: i64) -> Self {
499        Self::Pert(PertEstimate::new(optimistic, most_likely, pessimistic))
500    }
501}
502
503impl Default for DurationDistribution {
504    fn default() -> Self {
505        Self::Fixed(0)
506    }
507}
508
509#[cfg(test)]
510mod tests {
511    use super::*;
512
513    #[test]
514    fn test_time_constraint_basic() {
515        let c = ActivityTimeConstraint::bounded(1000, 5000);
516
517        // Within bounds — no violation
518        assert!(c.check_violation(1000, 4000).is_none());
519
520        // Starts too early
521        let v = c.check_violation(500, 4000).unwrap();
522        assert_eq!(v.early_ms, 500);
523        assert!(v.is_early());
524
525        // Ends too late
526        let v = c.check_violation(2000, 6000).unwrap();
527        assert_eq!(v.late_ms, 1000);
528        assert!(v.is_tardy());
529    }
530
531    #[test]
532    fn test_time_constraint_hard_vs_soft() {
533        let hard = ActivityTimeConstraint::deadline(5000).hard();
534        let soft = ActivityTimeConstraint::deadline(5000).soft(2.0);
535
536        let vh = hard.check_violation(0, 6000).unwrap();
537        let vs = soft.check_violation(0, 6000).unwrap();
538
539        assert_eq!(vh.severity, ViolationSeverity::Critical);
540        assert_eq!(vs.severity, ViolationSeverity::Minor);
541        assert!((vs.penalty - 2000.0).abs() < 0.01); // 1000ms * 2.0
542    }
543
544    #[test]
545    fn test_pert_calculation() {
546        let pert = PertEstimate::new(4000, 6000, 14000);
547
548        // Mean = (4 + 4*6 + 14) / 6 = 42/6 = 7
549        assert!((pert.mean_ms() - 7000.0).abs() < 0.01);
550
551        // StdDev = (14 - 4) / 6 = 10/6 ≈ 1.667
552        assert!((pert.std_dev_ms() - 1666.67).abs() < 1.0);
553    }
554
555    #[test]
556    fn test_pert_from_variance() {
557        let pert = PertEstimate::from_variance(10000, 0.2);
558        assert_eq!(pert.optimistic_ms, 8000);
559        assert_eq!(pert.most_likely_ms, 10000);
560        assert_eq!(pert.pessimistic_ms, 12000);
561    }
562
563    #[test]
564    fn test_pert_confidence_levels() {
565        let pert = PertEstimate::new(6000, 10000, 14000);
566
567        // P95 > P85 > P50
568        assert!(pert.p95() > pert.p85());
569        assert!(pert.p85() > pert.p50());
570    }
571
572    #[test]
573    fn test_duration_distribution_expected() {
574        let fixed = DurationDistribution::Fixed(5000);
575        assert!((fixed.expected_duration_ms() - 5000.0).abs() < 0.01);
576
577        let uniform = DurationDistribution::Uniform {
578            min_ms: 4000,
579            max_ms: 6000,
580        };
581        assert!((uniform.expected_duration_ms() - 5000.0).abs() < 0.01);
582
583        let tri = DurationDistribution::Triangular {
584            min_ms: 3000,
585            mode_ms: 5000,
586            max_ms: 7000,
587        };
588        assert!((tri.expected_duration_ms() - 5000.0).abs() < 0.01);
589    }
590
591    #[test]
592    fn test_constraint_violation_creation() {
593        let tw_v =
594            ConstraintViolation::time_window("OP-001", 5000, ViolationSeverity::Minor, 500.0);
595        assert_eq!(tw_v.violation_type, ConstraintViolationType::TimeWindow);
596        assert!(tw_v.message.contains("OP-001"));
597
598        let cap_v = ConstraintViolation::capacity_exceeded("M-001", 3);
599        assert_eq!(
600            cap_v.violation_type,
601            ConstraintViolationType::CapacityExceeded
602        );
603        assert_eq!(cap_v.severity, ViolationSeverity::Critical);
604    }
605
606    #[test]
607    fn test_violation_severity_ordering() {
608        assert!(ViolationSeverity::Critical > ViolationSeverity::Major);
609        assert!(ViolationSeverity::Major > ViolationSeverity::Minor);
610        assert!(ViolationSeverity::Minor > ViolationSeverity::Info);
611    }
612}
u_schedule/models/time_constraints.rs

u_schedule/models/
time_constraints.rs
