problemreductions/rules/
schedulingtominimizeweightedcompletiontime_ilp.rs

1//! Reduction from SchedulingToMinimizeWeightedCompletionTime to ILP.
2//!
3//! The reduction uses binary assignment variables `x_{t,p}` (task t on
4//! processor p), integer completion-time variables `C_t`, and binary
5//! ordering variables `y_{i,j}` for each task pair. Big-M constraints
6//! enforce that tasks sharing a processor do not overlap.
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::misc::SchedulingToMinimizeWeightedCompletionTime;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13/// Result of reducing SchedulingToMinimizeWeightedCompletionTime to ILP.
14///
15/// Variable layout:
16/// - `x_{t,p}` at index `t * m + p` for t in 0..n, p in 0..m
17/// - `C_t` at index `n * m + t` for t in 0..n (completion times)
18/// - `y_{i,j}` at index `n * m + n + pair_index(i,j)` for i < j
19///   (1 if task i is before task j on their shared processor)
20///
21/// Total variables: n*m + n + n*(n-1)/2
22#[derive(Debug, Clone)]
23pub struct ReductionSMWCTToILP {
24    target: ILP<i32>,
25    num_tasks: usize,
26    num_processors: usize,
27}
28
29impl ReductionSMWCTToILP {
30    fn x_var(&self, task: usize, processor: usize) -> usize {
31        task * self.num_processors + processor
32    }
33
34    fn c_var(&self, task: usize) -> usize {
35        self.num_tasks * self.num_processors + task
36    }
37
38    fn y_var(&self, i: usize, j: usize) -> usize {
39        debug_assert!(i < j);
40        let base = self.num_tasks * self.num_processors + self.num_tasks;
41        base + i * (2 * self.num_tasks - i - 1) / 2 + (j - i - 1)
42    }
43}
44
45impl ReductionResult for ReductionSMWCTToILP {
46    type Source = SchedulingToMinimizeWeightedCompletionTime;
47    type Target = ILP<i32>;
48
49    fn target_problem(&self) -> &ILP<i32> {
50        &self.target
51    }
52
53    /// Extract solution: for each task, find the processor with x_{t,p} = 1.
54    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
55        (0..self.num_tasks)
56            .map(|t| {
57                (0..self.num_processors)
58                    .find(|&p| target_solution[self.x_var(t, p)] == 1)
59                    .unwrap_or(0)
60            })
61            .collect()
62    }
63}
64
65#[reduction(
66    overhead = {
67        num_vars = "num_tasks * num_processors + num_tasks + num_tasks * (num_tasks - 1) / 2",
68        num_constraints = "num_tasks + num_tasks * num_processors + 2 * num_tasks + 2 * num_tasks * (num_tasks - 1) / 2 * num_processors + num_tasks * (num_tasks - 1) / 2",
69    }
70)]
71impl ReduceTo<ILP<i32>> for SchedulingToMinimizeWeightedCompletionTime {
72    type Result = ReductionSMWCTToILP;
73
74    fn reduce_to(&self) -> Self::Result {
75        let n = self.num_tasks();
76        let m = self.num_processors();
77
78        let total_processing_time: u64 = self.lengths().iter().sum();
79        let big_m = total_processing_time as f64;
80
81        let num_pairs = n * n.saturating_sub(1) / 2;
82        let num_vars = n * m + n + num_pairs;
83
84        let result = ReductionSMWCTToILP {
85            target: ILP::new(0, vec![], vec![], ObjectiveSense::Minimize),
86            num_tasks: n,
87            num_processors: m,
88        };
89
90        let mut constraints = Vec::new();
91
92        // 1. Assignment constraints: each task assigned to exactly one processor
93        // sum_p x_{t,p} = 1 for each t
94        for t in 0..n {
95            let terms: Vec<(usize, f64)> = (0..m).map(|p| (result.x_var(t, p), 1.0)).collect();
96            constraints.push(LinearConstraint::eq(terms, 1.0));
97        }
98
99        // 2. Binary bounds on x_{t,p}: 0 <= x_{t,p} <= 1
100        for t in 0..n {
101            for p in 0..m {
102                constraints.push(LinearConstraint::le(vec![(result.x_var(t, p), 1.0)], 1.0));
103            }
104        }
105
106        // 3. Completion time bounds: l_t <= C_t <= M
107        for t in 0..n {
108            constraints.push(LinearConstraint::ge(
109                vec![(result.c_var(t), 1.0)],
110                self.lengths()[t] as f64,
111            ));
112            constraints.push(LinearConstraint::le(vec![(result.c_var(t), 1.0)], big_m));
113        }
114
115        // 4. Disjunctive constraints: for each pair (i,j) with i < j, on each processor p:
116        //    If both tasks are on processor p and y_{i,j}=1 (i before j):
117        //      C_j >= C_i + l_j - M*(2 - x_{i,p} - x_{j,p}) - M*(1 - y_{i,j})
118        //    If both on p and y_{i,j}=0 (j before i):
119        //      C_i >= C_j + l_i - M*(2 - x_{i,p} - x_{j,p}) - M*y_{i,j}
120        //
121        // Rearranged:
122        //   C_j - C_i + M*x_{i,p} + M*x_{j,p} + M*y_{i,j} >= l_j - 3M + M
123        //     => C_j - C_i + M*x_{i,p} + M*x_{j,p} + M*y_{i,j} >= l_j - 2M
124        //   C_i - C_j + M*x_{i,p} + M*x_{j,p} - M*y_{i,j} >= l_i - 2M - M + M
125        //     => C_i - C_j + M*x_{i,p} + M*x_{j,p} - M*y_{i,j} >= l_i - 3M
126
127        for i in 0..n {
128            for j in (i + 1)..n {
129                let y = result.y_var(i, j);
130                let ci = result.c_var(i);
131                let cj = result.c_var(j);
132                let li = self.lengths()[i] as f64;
133                let lj = self.lengths()[j] as f64;
134
135                for p in 0..m {
136                    let xip = result.x_var(i, p);
137                    let xjp = result.x_var(j, p);
138
139                    // If i before j on processor p: C_j >= C_i + l_j
140                    // C_j - C_i + M*(1-y) + M*(1-x_{i,p}) + M*(1-x_{j,p}) >= l_j
141                    // C_j - C_i - M*y - M*x_{i,p} - M*x_{j,p} >= l_j - 3M
142                    constraints.push(LinearConstraint::ge(
143                        vec![
144                            (cj, 1.0),
145                            (ci, -1.0),
146                            (y, -big_m),
147                            (xip, -big_m),
148                            (xjp, -big_m),
149                        ],
150                        lj - 3.0 * big_m,
151                    ));
152
153                    // If j before i on processor p: C_i >= C_j + l_i
154                    // C_i - C_j + M*y + M*(1-x_{i,p}) + M*(1-x_{j,p}) >= l_i
155                    // C_i - C_j + M*y - M*x_{i,p} - M*x_{j,p} >= l_i - 2M
156                    constraints.push(LinearConstraint::ge(
157                        vec![
158                            (ci, 1.0),
159                            (cj, -1.0),
160                            (y, big_m),
161                            (xip, -big_m),
162                            (xjp, -big_m),
163                        ],
164                        li - 2.0 * big_m,
165                    ));
166                }
167
168                // Binary bound on y_{i,j}: 0 <= y <= 1
169                constraints.push(LinearConstraint::le(vec![(y, 1.0)], 1.0));
170            }
171        }
172
173        // Objective: minimize sum_t w_t * C_t
174        let objective: Vec<(usize, f64)> = (0..n)
175            .map(|t| (result.c_var(t), self.weights()[t] as f64))
176            .collect();
177
178        ReductionSMWCTToILP {
179            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize),
180            num_tasks: n,
181            num_processors: m,
182        }
183    }
184}
185
186#[cfg(feature = "example-db")]
187pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
188    vec![crate::example_db::specs::RuleExampleSpec {
189        id: "schedulingtominimizeweightedcompletiontime_to_ilp",
190        build: || {
191            // 3 tasks, 2 processors: simple instance for canonical example
192            let source =
193                SchedulingToMinimizeWeightedCompletionTime::new(vec![1, 2, 3], vec![4, 2, 1], 2);
194            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
195        },
196    }]
197}
198
199#[cfg(test)]
200#[path = "../unit_tests/rules/schedulingtominimizeweightedcompletiontime_ilp.rs"]
201mod tests;
problemreductions/rules/schedulingtominimizeweightedcompletiontime_ilp.rs

problemreductions/rules/
schedulingtominimizeweightedcompletiontime_ilp.rs
