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 ReductionResult for ReductionSWRTDToILP {
24    type Source = SequencingWithReleaseTimesAndDeadlines;
25    type Target = ILP<bool>;
26
27    fn target_problem(&self) -> &ILP<bool> {
28        &self.target
29    }
30
31    /// Extract by reading each task's start time and sorting tasks by start time.
32    fn extract_solution(
33        &self,
34        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
35    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
36        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
37
38        Ok({
39            let n = self.num_tasks;
40            let horizon = self.time_horizon;
41            // For each task, find the start time
42            let starts =
43                crate::rules::ilp_helpers::one_hot_decode_rows(target_solution, n, horizon, 0)?;
44            let mut start_times: Vec<_> = starts.into_iter().enumerate().collect();
45            // Sort by start time (break ties by task index)
46            start_times.sort_by_key(|&(j, t)| (t, j));
47            let schedule: Vec<usize> = start_times.iter().map(|&(j, _)| j).collect();
48            schedule
49        })
50    }
51}
52
53#[reduction(transform = upper_bound {
54    num_vars = "num_tasks * time_horizon",
55    num_constraints = "num_tasks * time_horizon + num_tasks + time_horizon",
56},
57    unavailable = {
58        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
59    }
60)]
61impl ReduceTo<ILP<bool>> for SequencingWithReleaseTimesAndDeadlines {
62    type Result = ReductionSWRTDToILP;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let n = self.num_tasks();
66        let horizon = self.time_horizon() as usize;
67        let num_vars = n * horizon;
68
69        let var = |j: usize, t: usize| -> usize { j * horizon + t };
70
71        let lengths = self.lengths();
72        let release_times = self.release_times();
73        let deadlines = self.deadlines();
74
75        let mut constraints = Vec::new();
76
77        // 1. Each task starts exactly once within its admissible window:
78        // Σ_{t=r_j}^{d_j-p_j} x_{j,t} = 1 for all j.
79        // Also, x_{j,t} = 0 for t outside the window (handled implicitly
80        // by not including them; add explicit zero constraints for safety).
81        for j in 0..n {
82            let r = release_times[j] as usize;
83            let last_start = deadlines[j]
84                .checked_sub(lengths[j])
85                .and_then(|time| usize::try_from(time).ok());
86            let terms: Vec<(usize, i64)> = last_start
87                .filter(|&last| r <= last)
88                .into_iter()
89                .flat_map(|last| r..=last)
90                .filter(|&t| t < horizon)
91                .map(|t| (var(j, t), 1))
92                .collect();
93            constraints.push(LinearConstraint::eq(terms, 1));
94
95            // Zero-fix variables outside the admissible window
96            for t in 0..horizon {
97                if t < r || last_start.is_none_or(|last| t > last) {
98                    constraints.push(LinearConstraint::eq(vec![(var(j, t), 1)], 0));
99                }
100            }
101        }
102
103        // 2. No overlap: for each time instant tau in 0..horizon,
104        // Σ_{j,t : t <= tau < t + p_j} x_{j,t} <= 1
105        for tau in 0..horizon {
106            let mut terms: Vec<(usize, i64)> = Vec::new();
107            for (j, &len_j) in lengths.iter().enumerate() {
108                let p = len_j as usize;
109                // Task j started at time t overlaps tau iff t <= tau < t + p_j
110                // i.e., tau - p_j + 1 <= t <= tau, where t >= 0
111                let t_min = (tau + 1).saturating_sub(p);
112                let t_max = tau;
113                for t in t_min..=t_max {
114                    if t < horizon {
115                        terms.push((var(j, t), 1));
116                    }
117                }
118            }
119            constraints.push(LinearConstraint::le(terms, 1));
120        }
121
122        Ok(ReductionSWRTDToILP {
123            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
124                .map_err(Self::target_construction)?,
125            num_tasks: n,
126            time_horizon: horizon,
127        })
128    }
129}
130
131#[cfg(feature = "example-db")]
132pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
133    vec![crate::example_db::specs::RuleExampleSpec {
134        id: "sequencingwithreleasetimesanddeadlines_to_ilp",
135        build: || {
136            let source = SequencingWithReleaseTimesAndDeadlines::new(
137                vec![1, 2, 1],
138                vec![0, 0, 2],
139                vec![3, 3, 4],
140            );
141            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
142        },
143    }]
144}
145
146#[cfg(test)]
147#[path = "../unit_tests/rules/sequencingwithreleasetimesanddeadlines_ilp.rs"]
148mod tests;
problemreductions/rules/sequencingwithreleasetimesanddeadlines_ilp.rs

problemreductions/rules/
sequencingwithreleasetimesanddeadlines_ilp.rs
