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}
11
12impl ReductionResult for ReductionPartitionToOpenShopScheduling {
13    type Source = Partition;
14    type Target = OpenShopScheduling;
15
16    fn target_problem(&self) -> &Self::Target {
17        &self.target
18    }
19
20    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
21        let num_elements = self.target.num_jobs().saturating_sub(1);
22        let mut source_config = vec![0; num_elements];
23        let Some(orders) = self.target.decode_orders(target_solution) else {
24            return source_config;
25        };
26        if num_elements == 0 {
27            return source_config;
28        }
29
30        let special_job = num_elements;
31        let half_sum = self.target.processing_times()[special_job][0];
32
33        // Find the middle machine and compute start times
34        let makespan_orders = &orders;
35        let n = self.target.num_jobs();
36        let m = self.target.num_machines();
37
38        // Simulate to get start times
39        let mut machine_avail = vec![0usize; m];
40        let mut job_avail = vec![0usize; n];
41        let mut start_times = vec![vec![0usize; m]; n];
42
43        // Schedule by processing the orders
44        let mut cursor = vec![0usize; m];
45        let total_ops = n * m;
46        for _ in 0..total_ops {
47            let mut best: Option<(usize, usize, usize)> = None; // (start, machine, job)
48            for (mi, order) in makespan_orders.iter().enumerate() {
49                if cursor[mi] < order.len() {
50                    let job = order[cursor[mi]];
51                    let start = machine_avail[mi].max(job_avail[job]);
52                    if best.is_none_or(|(bs, _, _)| start < bs) {
53                        best = Some((start, mi, job));
54                    }
55                }
56            }
57            let (start, mi, job) = best.expect("schedule incomplete");
58            start_times[job][mi] = start;
59            let end = start + self.target.processing_times()[job][mi];
60            machine_avail[mi] = end;
61            job_avail[job] = end;
62            cursor[mi] += 1;
63        }
64
65        // Find the middle machine where the special job starts at half_sum
66        let middle_machine = (0..m)
67            .find(|&machine| start_times[special_job][machine] == half_sum)
68            .unwrap_or_else(|| {
69                let mut machines: Vec<usize> = (0..m).collect();
70                machines.sort_by_key(|&machine| (start_times[special_job][machine], machine));
71                machines[m / 2]
72            });
73        let pivot = start_times[special_job][middle_machine];
74
75        for (job, slot) in source_config.iter_mut().enumerate() {
76            let completion = start_times[job][middle_machine]
77                + self.target.processing_times()[job][middle_machine];
78            if completion <= pivot {
79                *slot = 1;
80            }
81        }
82
83        source_config
84    }
85}
86
87#[reduction(overhead = {
88    num_jobs = "num_elements + 1",
89    num_machines = "3",
90})]
91impl ReduceTo<OpenShopScheduling> for Partition {
92    type Result = ReductionPartitionToOpenShopScheduling;
93
94    fn reduce_to(&self) -> Self::Result {
95        let half_sum = self.total_sum() as usize / 2;
96        let mut processing_times: Vec<Vec<usize>> = self
97            .sizes()
98            .iter()
99            .map(|&size| vec![size as usize; 3])
100            .collect();
101        processing_times.push(vec![half_sum; 3]);
102
103        ReductionPartitionToOpenShopScheduling {
104            target: OpenShopScheduling::new(3, processing_times),
105        }
106    }
107}
108
109#[cfg(feature = "example-db")]
110pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
111    use crate::export::SolutionPair;
112
113    vec![crate::example_db::specs::RuleExampleSpec {
114        id: "partition_to_open_shop_scheduling",
115        build: || {
116            crate::example_db::specs::rule_example_with_witness::<_, OpenShopScheduling>(
117                Partition::new(vec![1, 2, 3]),
118                SolutionPair {
119                    source_config: vec![0, 0, 1],
120                    target_config: vec![0, 1, 2, 3, 0, 1, 2, 3, 2, 3, 0, 1],
121                },
122            )
123        },
124    }]
125}
126
127#[cfg(test)]
128#[path = "../unit_tests/rules/partition_openshopscheduling.rs"]
129mod tests;
problemreductions/rules/partition_openshopscheduling.rs

problemreductions/rules/
partition_openshopscheduling.rs
