problemreductions/rules/
schedulingwithindividualdeadlines_ilp.rs

1//! Reduction from SchedulingWithIndividualDeadlines to ILP<bool>.
2//!
3//! Uses a time-indexed binary formulation with per-task deadline windows:
4//! - Variables: Binary x_{j,t} where x_{j,t} = 1 iff task j is scheduled at time slot t,
5//!   for t in 0..max_deadline (slots beyond each task's deadline are zero-fixed).
6//! - Variable index: j * max_deadline + t  for j in 0..num_tasks, t in 0..max_deadline
7//! - Constraints:
8//!   1. One-hot: Σ_{t<d_j} x_{j,t} = 1 for each task j (using only valid slots)
9//!   2. Zero beyond deadline: x_{j,t} = 0 for t >= d_j
10//!   3. Capacity: Σ_j x_{j,t} ≤ m for each time slot t
11//!   4. Precedence: Σ_t t·x_{j,t} ≥ Σ_t t·x_{i,t} + 1 for each (i,j)
12//! - Objective: Minimize 0 (feasibility)
13
14use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
15use crate::models::misc::SchedulingWithIndividualDeadlines;
16use crate::reduction;
17use crate::rules::traits::{ReduceTo, ReductionResult};
18
19/// Result of reducing SchedulingWithIndividualDeadlines to ILP<bool>.
20///
21/// Variable layout: x_{j,t} at index j * max_deadline + t
22/// for j in 0..num_tasks, t in 0..max_deadline.
23#[derive(Debug, Clone)]
24pub struct ReductionSWIDToILP {
25    target: ILP<bool>,
26    num_tasks: usize,
27    max_deadline: usize,
28}
29
30impl ReductionResult for ReductionSWIDToILP {
31    type Source = SchedulingWithIndividualDeadlines;
32    type Target = ILP<bool>;
33
34    fn target_problem(&self) -> &ILP<bool> {
35        &self.target
36    }
37
38    /// Extract schedule from ILP solution.
39    ///
40    /// For each task j, find the time slot t where x_{j,t} = 1.
41    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
42        let d = self.max_deadline;
43        (0..self.num_tasks)
44            .map(|j| {
45                (0..d)
46                    .find(|&t| target_solution.get(j * d + t).copied().unwrap_or(0) == 1)
47                    .unwrap_or(0)
48            })
49            .collect()
50    }
51}
52
53#[reduction(
54    overhead = {
55        num_vars = "num_tasks * max_deadline",
56        num_constraints = "num_tasks + max_deadline + num_precedences",
57    }
58)]
59impl ReduceTo<ILP<bool>> for SchedulingWithIndividualDeadlines {
60    type Result = ReductionSWIDToILP;
61
62    fn reduce_to(&self) -> Self::Result {
63        let n = self.num_tasks();
64        let m = self.num_processors();
65        let max_d = self.max_deadline();
66        let num_vars = n * max_d;
67
68        let var = |j: usize, t: usize| j * max_d + t;
69
70        let mut constraints = Vec::new();
71
72        // 1. One-hot: for each task j, sum over valid slots 0..d_j equals 1
73        for j in 0..n {
74            let dj = self.deadlines()[j];
75            let terms: Vec<(usize, f64)> = (0..dj).map(|t| (var(j, t), 1.0)).collect();
76            constraints.push(LinearConstraint::eq(terms, 1.0));
77        }
78
79        // 2. Capacity: Σ_j x_{j,t} ≤ m for each time slot t
80        for t in 0..max_d {
81            let terms: Vec<(usize, f64)> = (0..n).map(|j| (var(j, t), 1.0)).collect();
82            constraints.push(LinearConstraint::le(terms, m as f64));
83        }
84
85        // 3. Precedence: Σ_t t·x_{j,t} - Σ_t t·x_{i,t} ≥ 1 for each (i,j)
86        for &(i, j) in self.precedences() {
87            let di = self.deadlines()[i];
88            let dj = self.deadlines()[j];
89            let mut terms: Vec<(usize, f64)> = Vec::new();
90            for t in 0..dj {
91                terms.push((var(j, t), t as f64));
92            }
93            for t in 0..di {
94                terms.push((var(i, t), -(t as f64)));
95            }
96            constraints.push(LinearConstraint::ge(terms, 1.0));
97        }
98
99        ReductionSWIDToILP {
100            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
101            num_tasks: n,
102            max_deadline: max_d,
103        }
104    }
105}
106
107#[cfg(feature = "example-db")]
108pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
109    vec![crate::example_db::specs::RuleExampleSpec {
110        id: "schedulingwithindividualdeadlines_to_ilp",
111        build: || {
112            // 3 tasks, 2 processors, deadlines [2, 2, 3], precedence (0, 2)
113            let source = SchedulingWithIndividualDeadlines::new(3, 2, vec![2, 2, 3], vec![(0, 2)]);
114            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
115        },
116    }]
117}
118
119#[cfg(test)]
120#[path = "../unit_tests/rules/schedulingwithindividualdeadlines_ilp.rs"]
121mod tests;
problemreductions/rules/schedulingwithindividualdeadlines_ilp.rs

problemreductions/rules/
schedulingwithindividualdeadlines_ilp.rs
