problemreductions/rules/
partition_openshopscheduling.rs

1//! Reduction from Partition to Open Shop Scheduling.
2
3use crate::models::decision::Decision;
4use crate::models::misc::{OpenShopScheduling, Partition};
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7
8#[derive(Debug, Clone)]
9pub struct ReductionPartitionToOpenShopScheduling {
10    target: Decision<OpenShopScheduling>,
11}
12
13impl ReductionResult for ReductionPartitionToOpenShopScheduling {
14    type Source = Partition;
15    type Target = Decision<OpenShopScheduling>;
16
17    fn target_problem(&self) -> &Self::Target {
18        &self.target
19    }
20
21    fn extract_solution(
22        &self,
23        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
24    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
25        crate::rules::traits::validate_target_witness(
26            self.target_problem(),
27            target_solution,
28            |value| value.0,
29            "target schedule does not certify a balanced partition",
30        )?;
31
32        Ok({
33            let num_elements = self.target.inner().num_jobs() - 1;
34            let mut source_config = vec![false; num_elements];
35            let m = self.target.inner().num_machines();
36            let start_times = target_solution
37                .chunks_exact(m)
38                .map(|times| {
39                    times
40                        .iter()
41                        .map(|&time| {
42                            i64::try_from(time).map_err(|_| {
43                                crate::rules::ExtractionError::invalid(
44                                    "target schedule time does not fit i64",
45                                )
46                            })
47                        })
48                        .collect::<Result<Vec<_>, _>>()
49                })
50                .collect::<Result<Vec<_>, _>>()?;
51            let special_job = num_elements;
52            let half_sum = self.target.inner().processing_times()[special_job][0];
53
54            // Find the middle machine where the special job starts at half_sum
55            let middle_machine = (0..m)
56                .find(|&machine| start_times[special_job][machine] == half_sum)
57                .ok_or_else(|| {
58                    crate::rules::ExtractionError::invalid(
59                        "target schedule has no machine at the partition boundary",
60                    )
61                })?;
62            let pivot = start_times[special_job][middle_machine];
63
64            for (job, slot) in source_config.iter_mut().enumerate() {
65                let completion = start_times[job][middle_machine]
66                    .checked_add(self.target.inner().processing_times()[job][middle_machine])
67                    .ok_or_else(|| {
68                        crate::rules::ExtractionError::invalid("target schedule time overflows i64")
69                    })?;
70                if completion <= pivot {
71                    *slot = true;
72                }
73            }
74
75            source_config
76        })
77    }
78}
79
80#[crate::aggregate_reduction(identity)]
81impl crate::rules::AggregateReductionResult for ReductionPartitionToOpenShopScheduling {}
82
83#[reduction(
84    transform = {
85        exact {
86            num_jobs = "num_elements + 1",
87            num_machines = "3",
88        },
89        upper_bound {
90            // Three copies of each size and three floor(S/2) operations.
91            schedule_horizon = "9 * total_sum / 2",
92            schedule_horizon_bits = "max_numeric_magnitude_bits + num_elements + 3",
93        },
94    },
95)]
96impl ReduceTo<Decision<OpenShopScheduling>> for Partition {
97    type Result = ReductionPartitionToOpenShopScheduling;
98
99    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
100        let half_sum = self.total_sum() / 2;
101        let mut processing_times: Vec<Vec<i64>> =
102            self.sizes().iter().map(|&size| vec![size; 3]).collect();
103        processing_times.push(vec![half_sum; 3]);
104
105        let target = OpenShopScheduling::try_new(3, processing_times)
106            .map_err(<Self as ReduceTo<Decision<OpenShopScheduling>>>::target_construction)?;
107        // The validated nonnegative schedule horizon includes these three terms.
108        let feasible_makespan = 3 * half_sum;
109        Ok(ReductionPartitionToOpenShopScheduling {
110            target: Decision::new(target, feasible_makespan),
111        })
112    }
113}
114
115#[cfg(feature = "example-db")]
116pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
117    use crate::export::SolutionPair;
118
119    vec![crate::example_db::specs::RuleExampleSpec {
120        id: "partition_to_open_shop_scheduling",
121        build: || {
122            crate::example_db::specs::rule_example_with_witness::<_, Decision<OpenShopScheduling>>(
123                Partition::new(vec![1, 2, 3]).unwrap(),
124                SolutionPair {
125                    source_config: serde_json::json!(vec![true, true, false]),
126                    target_config: serde_json::json!(vec![0, 5, 6, 1, 3, 7, 6, 0, 3, 3, 6, 0]),
127                },
128            )
129        },
130    }]
131}
132
133#[cfg(test)]
134#[path = "../unit_tests/rules/partition_openshopscheduling.rs"]
135mod tests;
problemreductions/rules/partition_openshopscheduling.rs

problemreductions/rules/
partition_openshopscheduling.rs
