problemreductions/rules/
partition_openshopscheduling.rs

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

problemreductions/rules/
partition_openshopscheduling.rs
