problemreductions/rules/
resourceconstrainedscheduling_ilp.rs

1//! Reduction from ResourceConstrainedScheduling to ILP<bool>.
2//!
3//! Time-indexed binary formulation: x_{j,t} = 1 iff task j runs in slot t.
4//! Each task in exactly one slot; processor capacity and resource bounds
5//! enforced per time slot.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::misc::ResourceConstrainedScheduling;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12/// Result of reducing ResourceConstrainedScheduling to ILP<bool>.
13///
14/// Variable layout: x_{j,t} at index `j * D + t`
15/// for j in 0..n, t in 0..D.
16#[derive(Debug, Clone)]
17pub struct ReductionRCSToILP {
18    target: ILP<bool>,
19    num_tasks: usize,
20    deadline: usize,
21}
22
23impl ReductionResult for ReductionRCSToILP {
24    type Source = ResourceConstrainedScheduling;
25    type Target = ILP<bool>;
26
27    fn target_problem(&self) -> &ILP<bool> {
28        &self.target
29    }
30
31    /// Extract: for each task j, find the unique slot t with x_{j,t} = 1.
32    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
33        let d = self.deadline;
34        (0..self.num_tasks)
35            .map(|j| {
36                (0..d)
37                    .find(|&t| target_solution.get(j * d + t).copied().unwrap_or(0) == 1)
38                    .unwrap_or(0)
39            })
40            .collect()
41    }
42}
43
44#[reduction(overhead = {
45    num_vars = "num_tasks * deadline",
46    num_constraints = "num_tasks + deadline + num_resources * deadline",
47})]
48impl ReduceTo<ILP<bool>> for ResourceConstrainedScheduling {
49    type Result = ReductionRCSToILP;
50
51    fn reduce_to(&self) -> Self::Result {
52        let n = self.num_tasks();
53        let d = self.deadline() as usize;
54        let r = self.num_resources();
55        let m = self.num_processors();
56        let num_vars = n * d;
57
58        let var = |j: usize, t: usize| -> usize { j * d + t };
59
60        let mut constraints = Vec::new();
61
62        // 1. Each task in exactly one slot: Σ_t x_{j,t} = 1 for all j
63        for j in 0..n {
64            let terms: Vec<(usize, f64)> = (0..d).map(|t| (var(j, t), 1.0)).collect();
65            constraints.push(LinearConstraint::eq(terms, 1.0));
66        }
67
68        // 2. Processor capacity: Σ_j x_{j,t} <= m for each time slot t
69        for t in 0..d {
70            let terms: Vec<(usize, f64)> = (0..n).map(|j| (var(j, t), 1.0)).collect();
71            constraints.push(LinearConstraint::le(terms, m as f64));
72        }
73
74        // 3. Resource bounds: Σ_j r_{j,q} * x_{j,t} <= B_q for all q, t
75        for q in 0..r {
76            for t in 0..d {
77                let terms: Vec<(usize, f64)> = (0..n)
78                    .map(|j| (var(j, t), self.resource_requirements()[j][q] as f64))
79                    .collect();
80                constraints.push(LinearConstraint::le(
81                    terms,
82                    self.resource_bounds()[q] as f64,
83                ));
84            }
85        }
86
87        ReductionRCSToILP {
88            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
89            num_tasks: n,
90            deadline: d,
91        }
92    }
93}
94
95#[cfg(feature = "example-db")]
96pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
97    vec![crate::example_db::specs::RuleExampleSpec {
98        id: "resourceconstrainedscheduling_to_ilp",
99        build: || {
100            // 6 tasks, 3 processors, 1 resource with bound 20, deadline 2
101            let source = ResourceConstrainedScheduling::new(
102                3,
103                vec![20],
104                vec![vec![6], vec![7], vec![7], vec![6], vec![8], vec![6]],
105                2,
106            );
107            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
108        },
109    }]
110}
111
112#[cfg(test)]
113#[path = "../unit_tests/rules/resourceconstrainedscheduling_ilp.rs"]
114mod tests;
problemreductions/rules/resourceconstrainedscheduling_ilp.rs

problemreductions/rules/
resourceconstrainedscheduling_ilp.rs
