problemreductions/rules/
sequencingwithreleasetimesanddeadlines_ilp.rs

1//! Reduction from SequencingWithReleaseTimesAndDeadlines to ILP<bool>.
2//!
3//! Time-indexed formulation: binary x_{j,t} = 1 iff task j starts at time t.
4//! Each task starts within its admissible window [r_j, d_j - p_j].
5//! No two tasks may overlap on the single machine.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::misc::SequencingWithReleaseTimesAndDeadlines;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12/// Result of reducing SequencingWithReleaseTimesAndDeadlines to ILP<bool>.
13///
14/// Variable layout: x_{j,t} at index `j * T + t` for j in 0..n, t in 0..T,
15/// where T = time_horizon (max deadline).
16#[derive(Debug, Clone)]
17pub struct ReductionSWRTDToILP {
18    target: ILP<bool>,
19    num_tasks: usize,
20    time_horizon: usize,
21}
22
23impl ReductionSWRTDToILP {
24    fn encode_schedule_as_lehmer(schedule: &[usize]) -> Vec<usize> {
25        let mut available: Vec<usize> = (0..schedule.len()).collect();
26        let mut config = Vec::with_capacity(schedule.len());
27        for &task in schedule {
28            let digit = available
29                .iter()
30                .position(|&c| c == task)
31                .expect("schedule must be a permutation");
32            config.push(digit);
33            available.remove(digit);
34        }
35        config
36    }
37}
38
39impl ReductionResult for ReductionSWRTDToILP {
40    type Source = SequencingWithReleaseTimesAndDeadlines;
41    type Target = ILP<bool>;
42
43    fn target_problem(&self) -> &ILP<bool> {
44        &self.target
45    }
46
47    /// Extract: read each task's start time, sort tasks by start time,
48    /// encode as Lehmer code.
49    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
50        let n = self.num_tasks;
51        let horizon = self.time_horizon;
52        // For each task, find the start time
53        let mut start_times: Vec<(usize, usize)> = (0..n)
54            .map(|j| {
55                let start = (0..horizon)
56                    .find(|&t| target_solution.get(j * horizon + t).copied().unwrap_or(0) == 1)
57                    .unwrap_or(0);
58                (j, start)
59            })
60            .collect();
61        // Sort by start time (break ties by task index)
62        start_times.sort_by_key(|&(j, t)| (t, j));
63        let schedule: Vec<usize> = start_times.iter().map(|&(j, _)| j).collect();
64        Self::encode_schedule_as_lehmer(&schedule)
65    }
66}
67
68#[reduction(overhead = {
69    num_vars = "num_tasks * time_horizon",
70    num_constraints = "num_tasks + time_horizon",
71})]
72impl ReduceTo<ILP<bool>> for SequencingWithReleaseTimesAndDeadlines {
73    type Result = ReductionSWRTDToILP;
74
75    fn reduce_to(&self) -> Self::Result {
76        let n = self.num_tasks();
77        let horizon = self.time_horizon() as usize;
78        let num_vars = n * horizon;
79
80        let var = |j: usize, t: usize| -> usize { j * horizon + t };
81
82        let lengths = self.lengths();
83        let release_times = self.release_times();
84        let deadlines = self.deadlines();
85
86        let mut constraints = Vec::new();
87
88        // 1. Each task starts exactly once within its admissible window:
89        // Σ_{t=r_j}^{d_j-p_j} x_{j,t} = 1 for all j.
90        // Also, x_{j,t} = 0 for t outside the window (handled implicitly
91        // by not including them; add explicit zero constraints for safety).
92        for j in 0..n {
93            let r = release_times[j] as usize;
94            let last_start = if deadlines[j] >= lengths[j] {
95                (deadlines[j] - lengths[j]) as usize
96            } else {
97                0
98            };
99            let terms: Vec<(usize, f64)> = (r..=last_start)
100                .filter(|&t| t < horizon)
101                .map(|t| (var(j, t), 1.0))
102                .collect();
103            constraints.push(LinearConstraint::eq(terms, 1.0));
104
105            // Zero-fix variables outside the admissible window
106            for t in 0..horizon {
107                if t < r || t > last_start {
108                    constraints.push(LinearConstraint::eq(vec![(var(j, t), 1.0)], 0.0));
109                }
110            }
111        }
112
113        // 2. No overlap: for each time instant tau in 0..horizon,
114        // Σ_{j,t : t <= tau < t + p_j} x_{j,t} <= 1
115        for tau in 0..horizon {
116            let mut terms: Vec<(usize, f64)> = Vec::new();
117            for (j, &len_j) in lengths.iter().enumerate() {
118                let p = len_j as usize;
119                // Task j started at time t overlaps tau iff t <= tau < t + p_j
120                // i.e., tau - p_j + 1 <= t <= tau, where t >= 0
121                let t_min = (tau + 1).saturating_sub(p);
122                let t_max = tau;
123                for t in t_min..=t_max {
124                    if t < horizon {
125                        terms.push((var(j, t), 1.0));
126                    }
127                }
128            }
129            constraints.push(LinearConstraint::le(terms, 1.0));
130        }
131
132        ReductionSWRTDToILP {
133            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
134            num_tasks: n,
135            time_horizon: horizon,
136        }
137    }
138}
139
140#[cfg(feature = "example-db")]
141pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
142    vec![crate::example_db::specs::RuleExampleSpec {
143        id: "sequencingwithreleasetimesanddeadlines_to_ilp",
144        build: || {
145            let source = SequencingWithReleaseTimesAndDeadlines::new(
146                vec![1, 2, 1],
147                vec![0, 0, 2],
148                vec![3, 3, 4],
149            );
150            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
151        },
152    }]
153}
154
155#[cfg(test)]
156#[path = "../unit_tests/rules/sequencingwithreleasetimesanddeadlines_ilp.rs"]
157mod tests;
problemreductions/rules/sequencingwithreleasetimesanddeadlines_ilp.rs

problemreductions/rules/
sequencingwithreleasetimesanddeadlines_ilp.rs
