problemreductions/rules/
flowshopscheduling_ilp.rs

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

problemreductions/rules/
flowshopscheduling_ilp.rs
