problemreductions/rules/
preemptivescheduling_ilp.rs

1//! Time-indexed preemptive scheduling with bounded start and completion variables.
2//!
3//! Binary x(t,u) records task activity. Start S(t) is no later than any active
4//! slot; completion C(t) is later than every active slot. Each precedence
5//! (a,b) requires C(a) <= S(b), so interrupted tasks still finish before their
6//! successors start. Minimize M with M >= C(t) for every task.
7//!
8//! Using task endpoints avoids repeating all earlier time slots for every
9//! precedence edge: the matrix has 6*A + 2*p + 2*n nonzeros for A admissible
10//! activity slots, p precedence edges, and n tasks.
11
12use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
13use crate::models::misc::PreemptiveScheduling;
14use crate::reduction;
15use crate::rules::traits::{ReduceTo, ReductionResult};
16
17/// Result of reducing PreemptiveScheduling to `ILP<i64, i64, Bounded>`.
18#[derive(Debug, Clone)]
19pub struct ReductionPSToILP {
20    target: ILP<i64, i64, Bounded>,
21    num_tasks: usize,
22    d_max: usize,
23    slots: Vec<(usize, usize)>,
24}
25
26impl ReductionResult for ReductionPSToILP {
27    type Source = PreemptiveScheduling;
28    type Target = ILP<i64, i64, Bounded>;
29
30    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
31        &self.target
32    }
33
34    /// Extract schedule from ILP solution.
35    ///
36    /// Returns the task-by-time activity matrix, restoring omitted slots to false.
37    fn extract_solution(
38        &self,
39        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
40    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
41        crate::rules::traits::validate_target_witness(
42            self.target_problem(),
43            target_solution,
44            |value| value.value.is_some(),
45            "target ILP assignment is infeasible",
46        )?;
47
48        let mut schedule = vec![vec![false; self.d_max]; self.num_tasks];
49        for (variable, &(task, time)) in self.slots.iter().enumerate() {
50            schedule[task][time] = target_solution[variable] == 1;
51        }
52        Ok(schedule)
53    }
54}
55
56#[reduction(transform = upper_bound {
57    num_vars = "num_tasks * d_max + 2 * num_tasks + 1",
58    num_constraints = "2 * num_tasks + d_max + 2 * num_tasks * d_max + num_precedences",
59    num_nonzeros = "6 * num_tasks * d_max + 2 * num_precedences + 2 * num_tasks",
60    max_constraint_magnitude_bits = "max_schedule_magnitude_bits",
61})]
62impl ReduceTo<ILP<i64, i64, Bounded>> for PreemptiveScheduling {
63    type Result = ReductionPSToILP;
64
65    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
66        let n = self.num_tasks();
67        let (d, windows) = self.scheduling_windows();
68        let num_task_vars: usize = windows.iter().map(|window| window.len()).sum();
69        let m_var = num_task_vars; // index of the makespan variable M
70        let num_vars = n
71            .checked_mul(2)
72            .and_then(|endpoints| num_task_vars.checked_add(endpoints))
73            .and_then(|total| total.checked_add(1))
74            .ok_or_else(|| {
75                crate::rules::ReductionError::integer_overflow::<Self, ILP<i64, i64, Bounded>>(
76                    "counting scheduling variables",
77                )
78            })?;
79        let horizon = Self::exact_i64(d, "bounding the scheduling horizon")?;
80        let lengths = self.lengths();
81        let processor_count = Self::exact_i64(
82            self.num_processors().min(n),
83            "encoding the processor capacity",
84        )?;
85
86        // Check endpoint arithmetic before allocating the time-indexed matrix.
87        horizon.checked_mul(2).ok_or_else(|| {
88            crate::rules::ReductionError::integer_overflow::<Self, ILP<i64, i64, Bounded>>(
89                "bounding endpoint constraint evaluation",
90            )
91        })?;
92        let slots: Vec<_> = windows
93            .into_iter()
94            .enumerate()
95            .flat_map(|(task, window)| window.map(move |time| (task, time)))
96            .collect();
97        let mut task_terms = vec![Vec::new(); n];
98        let mut time_terms = vec![Vec::new(); d];
99        for (variable, &(task, time)) in slots.iter().enumerate() {
100            task_terms[task].push((variable, 1));
101            time_terms[time].push((variable, 1));
102        }
103        let start = |t: usize| num_task_vars + 1 + t;
104        let completion = |t: usize| num_task_vars + 1 + n + t;
105
106        let mut constraints = Vec::new();
107
108        for (terms, &length) in task_terms.into_iter().zip(lengths) {
109            constraints.push(LinearConstraint::eq(terms, length));
110        }
111        for terms in time_terms {
112            constraints.push(LinearConstraint::le(terms, processor_count));
113        }
114        for (variable, &(t, u)) in slots.iter().enumerate() {
115            constraints.push(LinearConstraint::le(
116                vec![
117                    (start(t), 1),
118                    (variable, Self::exact_i64(d - u, "encoding a start bound")?),
119                ],
120                horizon,
121            ));
122            constraints.push(LinearConstraint::ge(
123                vec![
124                    (completion(t), 1),
125                    (
126                        variable,
127                        -Self::exact_i64(u + 1, "encoding a completion bound")?,
128                    ),
129                ],
130                0,
131            ));
132        }
133        for &(pred, succ) in self.precedences() {
134            constraints.push(LinearConstraint::le(
135                vec![(completion(pred), 1), (start(succ), -1)],
136                0,
137            ));
138        }
139        for t in 0..n {
140            constraints.push(LinearConstraint::le(
141                vec![(completion(t), 1), (m_var, -1)],
142                0,
143            ));
144        }
145
146        // Objective: minimize M
147        let objective = vec![(m_var, 1)];
148
149        // Slot domains enforce binary values without redundant bound rows.
150        let mut variables = vec![IntegerVariable::binary(); num_vars];
151        variables[num_task_vars..]
152            .fill(IntegerVariable::new(Some(0), Some(horizon)).map_err(Self::target_construction)?);
153
154        let target =
155            ILP::with_variables(variables, constraints, objective, ObjectiveSense::Minimize)
156                .map_err(Self::target_construction)?;
157        crate::rules::ilp_helpers::validate_bounded_constraint_arithmetic::<Self>(&target)?;
158        Ok(ReductionPSToILP {
159            target,
160            num_tasks: n,
161            d_max: self.d_max(),
162            slots,
163        })
164    }
165}
166
167#[cfg(feature = "example-db")]
168pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
169    vec![crate::example_db::specs::RuleExampleSpec {
170        id: "preemptivescheduling_to_ilp",
171        build: || {
172            // 3 tasks, lengths [2,1,2], 2 processors, precedence (0,2)
173            let source = PreemptiveScheduling::new(vec![2, 1, 2], 2, vec![(0, 2)]).unwrap();
174            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
175        },
176    }]
177}
178
179#[cfg(test)]
180#[path = "../unit_tests/rules/preemptivescheduling_ilp.rs"]
181mod tests;
problemreductions/rules/preemptivescheduling_ilp.rs

problemreductions/rules/
preemptivescheduling_ilp.rs
