problemreductions/rules/
precedenceconstrainedscheduling_ilp.rs

1//! Reduction from PrecedenceConstrainedScheduling to ILP<bool>.
2//!
3//! Uses a time-indexed binary formulation:
4//! - Variables: Binary x_{j,t} where x_{j,t} = 1 iff task j is scheduled at time slot t.
5//! - Variable index: j * deadline + t  for j in 0..num_tasks, t in 0..deadline
6//! - Constraints:
7//!   1. One-hot: Σ_t x_{j,t} = 1 for each task j
8//!   2. Capacity: Σ_j x_{j,t} ≤ m for each time slot t
9//!   3. Precedence: Σ_t t·x_{j,t} ≥ Σ_t t·x_{i,t} + 1 for each (i,j) in precedences
10//! - Objective: Minimize 0 (feasibility)
11//! - Extraction: For each task j, find argmax_t x_{j,t}
12
13use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
14use crate::models::misc::PrecedenceConstrainedScheduling;
15use crate::reduction;
16use crate::rules::traits::{ReduceTo, ReductionResult};
17
18/// Result of reducing PrecedenceConstrainedScheduling to ILP<bool>.
19///
20/// Variable layout: x_{j,t} at index j * deadline + t
21/// for j in 0..num_tasks, t in 0..deadline.
22#[derive(Debug, Clone)]
23pub struct ReductionPCSToILP {
24    target: ILP<bool>,
25    num_tasks: usize,
26    deadline: usize,
27}
28
29impl ReductionResult for ReductionPCSToILP {
30    type Source = PrecedenceConstrainedScheduling;
31    type Target = ILP<bool>;
32
33    fn target_problem(&self) -> &ILP<bool> {
34        &self.target
35    }
36
37    /// Extract schedule from ILP solution.
38    ///
39    /// For each task j, find the time slot t where x_{j,t} = 1.
40    /// Returns the time slot for each task (matching the `dims()` encoding of PCS).
41    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
42        let d = self.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 * deadline",
56        num_constraints = "num_tasks + deadline + num_tasks^2",
57    }
58)]
59impl ReduceTo<ILP<bool>> for PrecedenceConstrainedScheduling {
60    type Result = ReductionPCSToILP;
61
62    fn reduce_to(&self) -> Self::Result {
63        let n = self.num_tasks();
64        let m = self.num_processors();
65        let d = self.deadline();
66        let num_vars = n * d;
67
68        // x_{j,t} variable index
69        let var = |j: usize, t: usize| j * d + t;
70
71        let mut constraints = Vec::new();
72
73        // 1. One-hot: Σ_t x_{j,t} = 1 for each task j
74        for j in 0..n {
75            let terms: Vec<(usize, f64)> = (0..d).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..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        // Rearranged: Σ_t t·x_{j,t} - Σ_t t·x_{i,t} ≥ 1
87        for &(i, j) in self.precedences() {
88            let mut terms: Vec<(usize, f64)> = Vec::new();
89            for t in 0..d {
90                terms.push((var(j, t), t as f64));
91                terms.push((var(i, t), -(t as f64)));
92            }
93            constraints.push(LinearConstraint::ge(terms, 1.0));
94        }
95
96        ReductionPCSToILP {
97            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
98            num_tasks: n,
99            deadline: d,
100        }
101    }
102}
103
104#[cfg(feature = "example-db")]
105pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
106    vec![crate::example_db::specs::RuleExampleSpec {
107        id: "precedenceconstrainedscheduling_to_ilp",
108        build: || {
109            // 3 tasks, 2 processors, deadline 2, with task 0 < task 2
110            let source = PrecedenceConstrainedScheduling::new(3, 2, 2, vec![(0, 2)]);
111            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
112        },
113    }]
114}
115
116#[cfg(test)]
117#[path = "../unit_tests/rules/precedenceconstrainedscheduling_ilp.rs"]
118mod tests;
problemreductions/rules/precedenceconstrainedscheduling_ilp.rs

problemreductions/rules/
precedenceconstrainedscheduling_ilp.rs
