problemreductions/rules/
flowshopscheduling_ilp.rs

1//! Reduction from FlowShopScheduling to ILP<i32>.
2//!
3//! Binary order variables y_{i,j} with y_{i,j}=1 iff job i precedes job j,
4//! integer completion-time variables C_{j,q} for each job j and machine q.
5//! Machine-chain and big-M disjunctive constraints enforce a valid flow-shop
6//! schedule; the deadline becomes a makespan bound.
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::misc::FlowShopScheduling;
10use crate::reduction;
11use crate::rules::ilp_helpers::permutation_to_lehmer;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13
14/// Result of reducing FlowShopScheduling to ILP<i32>.
15///
16/// Variable layout:
17/// - `y_{i,j}` for each ordered pair (i,j) with i<j: index `i*n + j - (i+1)*(i+2)/2`
18///   (upper triangle, n*(n-1)/2 variables)
19/// - `C_{j,q}` for j in 0..n, q in 0..m: index `num_order_vars + j*m + q`
20///
21/// Total: n*(n-1)/2 + n*m variables.
22#[derive(Debug, Clone)]
23pub struct ReductionFSSToILP {
24    target: ILP<i32>,
25    num_jobs: usize,
26    num_machines: usize,
27    num_order_vars: usize,
28}
29
30impl ReductionFSSToILP {
31    fn encode_schedule_as_lehmer(schedule: &[usize]) -> Vec<usize> {
32        let mut available: Vec<usize> = (0..schedule.len()).collect();
33        let mut config = Vec::with_capacity(schedule.len());
34        for &task in schedule {
35            let digit = available
36                .iter()
37                .position(|&c| c == task)
38                .expect("schedule must be a permutation");
39            config.push(digit);
40            available.remove(digit);
41        }
42        config
43    }
44}
45
46impl ReductionResult for ReductionFSSToILP {
47    type Source = FlowShopScheduling;
48    type Target = ILP<i32>;
49
50    fn target_problem(&self) -> &ILP<i32> {
51        &self.target
52    }
53
54    /// Extract solution: sort jobs by final-machine completion time C_{j,m-1},
55    /// then convert permutation to Lehmer code.
56    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
57        let n = self.num_jobs;
58        let m = self.num_machines;
59        let c_offset = self.num_order_vars;
60        let mut jobs: Vec<usize> = (0..n).collect();
61        jobs.sort_by_key(|&j| {
62            let idx = c_offset + j * m + (m - 1);
63            (target_solution.get(idx).copied().unwrap_or(0), j)
64        });
65        let perm = permutation_to_lehmer(&jobs);
66        Self::encode_schedule_as_lehmer(&jobs)
67            .into_iter()
68            .zip(perm)
69            .map(|(lehmer, _)| lehmer)
70            .collect()
71    }
72}
73
74#[reduction(overhead = {
75    num_vars = "num_jobs * (num_jobs - 1) / 2 + num_jobs * num_processors",
76    num_constraints = "num_jobs * (num_jobs - 1) / 2 + num_jobs + num_jobs * (num_processors - 1) + num_jobs * (num_jobs - 1) * num_processors + num_jobs",
77})]
78impl ReduceTo<ILP<i32>> for FlowShopScheduling {
79    type Result = ReductionFSSToILP;
80
81    fn reduce_to(&self) -> Self::Result {
82        let n = self.num_jobs();
83        let m = self.num_processors();
84
85        let num_order_vars = n * n.saturating_sub(1) / 2;
86        let num_completion_vars = n * m;
87        let num_vars = num_order_vars + num_completion_vars;
88
89        // Order variable index for pair (i, j) with i < j
90        let order_var = |i: usize, j: usize| -> usize {
91            debug_assert!(i < j);
92            i * (2 * n - i - 1) / 2 + (j - i - 1)
93        };
94        // Completion time variable index for job j, machine q
95        let c_var = |j: usize, q: usize| -> usize { num_order_vars + j * m + q };
96
97        let p = self.task_lengths();
98        let d = self.deadline();
99
100        // Big-M: D + max processing time
101        let max_p = p
102            .iter()
103            .flat_map(|row| row.iter())
104            .copied()
105            .max()
106            .unwrap_or(0);
107        let big_m = (d + max_p) as f64;
108
109        let mut constraints = Vec::new();
110
111        // 1. Symmetry: y_{i,j} + y_{j,i} = 1 for all i != j
112        // Since we only store y_{i,j} for i < j, we enforce y_{i,j} in {0,1}
113        // via 0 <= y_{i,j} <= 1.
114        for i in 0..n {
115            for j in (i + 1)..n {
116                constraints.push(LinearConstraint::le(vec![(order_var(i, j), 1.0)], 1.0));
117                constraints.push(LinearConstraint::ge(vec![(order_var(i, j), 1.0)], 0.0));
118            }
119        }
120
121        // 2. C_{j,0} >= p_{j,0} for all j
122        for (j, p_j) in p.iter().enumerate() {
123            constraints.push(LinearConstraint::ge(
124                vec![(c_var(j, 0), 1.0)],
125                p_j[0] as f64,
126            ));
127        }
128
129        // 3. Machine chain: C_{j,q+1} >= C_{j,q} + p_{j,q+1} for all j, q in 0..m-1
130        for (j, p_j) in p.iter().enumerate() {
131            for q in 0..(m.saturating_sub(1)) {
132                // C_{j,q+1} - C_{j,q} >= p_{j,q+1}
133                constraints.push(LinearConstraint::ge(
134                    vec![(c_var(j, q + 1), 1.0), (c_var(j, q), -1.0)],
135                    p_j[q + 1] as f64,
136                ));
137            }
138        }
139
140        // 4. Disjunctive: C_{j,q} >= C_{i,q} + p_{j,q} - M*(1 - y_{i,j}) for i != j, all q
141        // For i < j: y_{i,j} is the variable.
142        //   C_{j,q} - C_{i,q} + M*y_{i,j} >= p_{j,q} + M  ... wrong
143        //   Actually: C_{j,q} >= C_{i,q} + p_{j,q} - M*(1 - y_{i,j})
144        //   => C_{j,q} - C_{i,q} + M*y_{i,j} >= p_{j,q}   ... when y_{i,j}=0 (i NOT before j): inactive
145        //                                                        when y_{i,j}=1 (i before j): C_{j,q} >= C_{i,q} + p_{j,q}
146        //   Wait, this needs reconsideration. The paper says:
147        //   C_{j,q} >= C_{i,q} + p_{j,q} - M*(1 - y_{i,j})
148        //   => C_{j,q} - C_{i,q} - M*y_{i,j} >= p_{j,q} - M
149        //   No let me expand directly:
150        //   C_{j,q} - C_{i,q} + M*y_{i,j} >= p_{j,q} + M*(0)... hmm
151        //
152        // Let me re-derive: C_{j,q} >= C_{i,q} + p_{j,q} - M*(1 - y_{i,j})
153        //   = C_{j,q} - C_{i,q} + M*(1 - y_{i,j}) >= p_{j,q}
154        //   = C_{j,q} - C_{i,q} + M - M*y_{i,j} >= p_{j,q}
155        //   = C_{j,q} - C_{i,q} - M*y_{i,j} >= p_{j,q} - M
156        for i in 0..n {
157            for (j, p_j) in p.iter().enumerate() {
158                if i == j {
159                    continue;
160                }
161                for (q, &p_jq) in p_j.iter().enumerate() {
162                    if i < j {
163                        // y_{i,j} is the variable. When y_{i,j} = 1, i precedes j,
164                        // so C_{j,q} >= C_{i,q} + p_{j,q}.
165                        // C_{j,q} - C_{i,q} - M*y_{i,j} >= p_{j,q} - M
166                        constraints.push(LinearConstraint::ge(
167                            vec![
168                                (c_var(j, q), 1.0),
169                                (c_var(i, q), -1.0),
170                                (order_var(i, j), -big_m),
171                            ],
172                            p_jq as f64 - big_m,
173                        ));
174                    } else {
175                        // i > j: y_{j,i} is stored. y_{i,j} = 1 - y_{j,i}.
176                        // C_{j,q} >= C_{i,q} + p_{j,q} - M*(1 - (1 - y_{j,i}))
177                        // C_{j,q} >= C_{i,q} + p_{j,q} - M*y_{j,i}
178                        // C_{j,q} - C_{i,q} + M*y_{j,i} >= p_{j,q}
179                        constraints.push(LinearConstraint::ge(
180                            vec![
181                                (c_var(j, q), 1.0),
182                                (c_var(i, q), -1.0),
183                                (order_var(j, i), big_m),
184                            ],
185                            p_jq as f64,
186                        ));
187                    }
188                }
189            }
190        }
191
192        // 5. Deadline: C_{j,m-1} <= D for all j
193        if m > 0 {
194            for j in 0..n {
195                constraints.push(LinearConstraint::le(vec![(c_var(j, m - 1), 1.0)], d as f64));
196            }
197        }
198
199        ReductionFSSToILP {
200            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
201            num_jobs: n,
202            num_machines: m,
203            num_order_vars,
204        }
205    }
206}
207
208#[cfg(feature = "example-db")]
209pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
210    vec![crate::example_db::specs::RuleExampleSpec {
211        id: "flowshopscheduling_to_ilp",
212        build: || {
213            // 2 machines, 3 jobs, deadline 10
214            let source = FlowShopScheduling::new(2, vec![vec![2, 3], vec![3, 2], vec![1, 4]], 10);
215            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
216        },
217    }]
218}
219
220#[cfg(test)]
221#[path = "../unit_tests/rules/flowshopscheduling_ilp.rs"]
222mod tests;
problemreductions/rules/flowshopscheduling_ilp.rs

problemreductions/rules/
flowshopscheduling_ilp.rs
