problemreductions/rules/
flowshopscheduling_ilp.rs

1//! Reduction from FlowShopScheduling to `ILP<i64, i64, Bounded>`.
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::{Bounded, IntegerVariable, 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, i64, Bounded>`.
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, i64, Bounded>,
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, i64, Bounded>;
32
33    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
34        &self.target
35    }
36
37    /// Sort by the sum of completion times across all machines. A predecessor
38    /// cannot have a larger sum; ties can reverse only zero-duration jobs,
39    /// which do not delay the remaining schedule.
40    fn extract_solution(
41        &self,
42        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
43    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
44        crate::rules::traits::validate_target_witness(
45            self.target_problem(),
46            target_solution,
47            |value| value.value.is_some(),
48            "target ILP assignment is infeasible",
49        )?;
50
51        Ok({
52            let n = self.num_jobs;
53            let m = self.num_machines;
54            let c_offset = self.num_order_vars;
55            let mut jobs: Vec<usize> = (0..n).collect();
56            jobs.sort_by_key(|&j| {
57                let start = c_offset + j * m;
58                (
59                    target_solution[start..start + m]
60                        .iter()
61                        .map(|&time| i128::from(time))
62                        .sum::<i128>(),
63                    j,
64                )
65            });
66            jobs
67        })
68    }
69}
70
71#[crate::aggregate_reduction(ilp_feasibility)]
72impl crate::rules::AggregateReductionResult for ReductionFSSToILP {}
73
74#[reduction(
75    transform = upper_bound {
76        max_constraint_magnitude_bits = "max_time_bits + 1",
77        num_vars = "num_jobs * (num_jobs - 1) / 2 + num_jobs * num_processors",
78        num_constraints = "num_jobs * (num_jobs - 1) + num_jobs + num_jobs * (num_processors - 1) + num_jobs * (num_jobs - 1) * num_processors + num_jobs",
79        num_nonzeros = "(num_jobs * (num_jobs - 1) / 2 + num_jobs * num_processors) * (num_jobs * (num_jobs - 1) + num_jobs + num_jobs * (num_processors - 1) + num_jobs * (num_jobs - 1) * num_processors + num_jobs)",
80    },
81)]
82impl ReduceTo<ILP<i64, i64, Bounded>> for FlowShopScheduling {
83    type Result = ReductionFSSToILP;
84
85    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
86        let n = self.num_jobs();
87        let m = self.num_processors();
88
89        let num_order_vars = n * n.saturating_sub(1) / 2;
90        let num_completion_vars = n * m;
91        let num_vars = num_order_vars + num_completion_vars;
92
93        // Order variable index for pair (i, j) with i < j
94        let order_var = |i: usize, j: usize| -> usize {
95            debug_assert!(i < j);
96            i * (2 * n - i - 1) / 2 + (j - i - 1)
97        };
98        // Completion time variable index for job j, machine q
99        let c_var = |j: usize, q: usize| -> usize { num_order_vars + j * m + q };
100
101        let p = self.task_lengths();
102        let d = self.deadline();
103        let deadline = d;
104
105        // Big-M: D + max processing time
106        let max_p = p
107            .iter()
108            .flat_map(|row| row.iter())
109            .copied()
110            .max()
111            .unwrap_or(0);
112        let big_m = d.checked_add(max_p).ok_or_else(|| {
113            crate::rules::ReductionError::integer_overflow::<
114                FlowShopScheduling,
115                ILP<i64, i64, Bounded>,
116            >("computing the flow-shop big-M bound")
117        })?;
118        let mut constraints = Vec::new();
119
120        // 1. Symmetry: y_{i,j} + y_{j,i} = 1 for all i != j
121        // Since we only store y_{i,j} for i < j, we enforce y_{i,j} in {0,1}
122        // via 0 <= y_{i,j} <= 1.
123        for i in 0..n {
124            for j in (i + 1)..n {
125                constraints.push(LinearConstraint::le(vec![(order_var(i, j), 1)], 1));
126                constraints.push(LinearConstraint::ge(vec![(order_var(i, j), 1)], 0));
127            }
128        }
129
130        // 2. C_{j,0} >= p_{j,0} for all j
131        for (j, p_j) in p.iter().enumerate() {
132            if let Some(&length) = p_j.first() {
133                constraints.push(LinearConstraint::ge(vec![(c_var(j, 0), 1)], length));
134            }
135        }
136
137        // 3. Machine chain: C_{j,q+1} >= C_{j,q} + p_{j,q+1} for all j, q in 0..m-1
138        for (j, p_j) in p.iter().enumerate() {
139            for q in 0..(m.saturating_sub(1)) {
140                // C_{j,q+1} - C_{j,q} >= p_{j,q+1}
141                constraints.push(LinearConstraint::ge(
142                    vec![(c_var(j, q + 1), 1), (c_var(j, q), -1)],
143                    p_j[q + 1],
144                ));
145            }
146        }
147
148        // 4. Disjunctive: C_{j,q} >= C_{i,q} + p_{j,q} - M*(1 - y_{i,j}) for i != j, all q
149        // For i < j: y_{i,j} is the variable.
150        //   = C_{j,q} - C_{i,q} - M*y_{i,j} >= p_{j,q} - M
151        for i in 0..n {
152            for (j, p_j) in p.iter().enumerate() {
153                if i == j {
154                    continue;
155                }
156                for (q, &p_jq) in p_j.iter().enumerate() {
157                    if i < j {
158                        // y_{i,j} is the variable. When y_{i,j} = 1, i precedes j,
159                        // so C_{j,q} >= C_{i,q} + p_{j,q}.
160                        // C_{j,q} - C_{i,q} - M*y_{i,j} >= p_{j,q} - M
161                        constraints.push(LinearConstraint::ge(
162                            vec![
163                                (c_var(j, q), 1),
164                                (c_var(i, q), -1),
165                                (order_var(i, j), -big_m),
166                            ],
167                            p_jq - big_m,
168                        ));
169                    } else {
170                        // i > j: y_{j,i} is stored. y_{i,j} = 1 - y_{j,i}.
171                        // C_{j,q} >= C_{i,q} + p_{j,q} - M*(1 - (1 - y_{j,i}))
172                        // C_{j,q} >= C_{i,q} + p_{j,q} - M*y_{j,i}
173                        // C_{j,q} - C_{i,q} + M*y_{j,i} >= p_{j,q}
174                        constraints.push(LinearConstraint::ge(
175                            vec![
176                                (c_var(j, q), 1),
177                                (c_var(i, q), -1),
178                                (order_var(j, i), big_m),
179                            ],
180                            p_jq,
181                        ));
182                    }
183                }
184            }
185        }
186
187        // 5. Deadline: C_{j,m-1} <= D for all j
188        if m > 0 {
189            for j in 0..n {
190                constraints.push(LinearConstraint::le(vec![(c_var(j, m - 1), 1)], deadline));
191            }
192        }
193
194        let mut variables = vec![IntegerVariable::binary(); num_vars];
195        variables[num_order_vars..].fill(
196            IntegerVariable::new(Some(0), Some(deadline)).map_err(Self::target_construction)?,
197        );
198
199        Ok(ReductionFSSToILP {
200            target: ILP::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
201                .map_err(Self::target_construction)?,
202            num_jobs: n,
203            num_machines: m,
204            num_order_vars,
205        })
206    }
207}
208
209#[cfg(feature = "example-db")]
210pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
211    vec![crate::example_db::specs::RuleExampleSpec {
212        id: "flowshopscheduling_to_ilp",
213        build: || {
214            // 2 machines, 3 jobs, deadline 10
215            let source = FlowShopScheduling::new(2, vec![vec![2, 3], vec![3, 2], vec![1, 4]], 10);
216            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
217        },
218    }]
219}
220
221#[cfg(test)]
222#[path = "../unit_tests/rules/flowshopscheduling_ilp.rs"]
223mod tests;
problemreductions/rules/flowshopscheduling_ilp.rs

problemreductions/rules/
flowshopscheduling_ilp.rs
