problemreductions/rules/
partition_multiprocessorscheduling.rs

1//! Reduction from Partition to MultiprocessorScheduling.
2//!
3//! Given a Partition instance with sizes A = {a_1, ..., a_n}, construct a
4//! MultiprocessorScheduling instance with:
5//! - Tasks: one per element, with length equal to the element's size
6//! - m = 2 processors
7//! - Deadline D = floor(total_sum / 2)
8//!
9//! A valid partition (two subsets of equal sum) exists iff the tasks can be
10//! scheduled on 2 processors with makespan at most D.
11//!
12//! Solution extraction is the identity: the binary subset assignment in Partition
13//! directly corresponds to the processor assignment in MultiprocessorScheduling.
14
15use crate::models::misc::{MultiprocessorScheduling, Partition};
16use crate::reduction;
17use crate::rules::traits::{ReduceTo, ReductionResult};
18
19/// Result of reducing Partition to MultiprocessorScheduling.
20#[derive(Debug, Clone)]
21pub struct ReductionPartitionToMPS {
22    target: MultiprocessorScheduling,
23}
24
25impl ReductionResult for ReductionPartitionToMPS {
26    type Source = Partition;
27    type Target = MultiprocessorScheduling;
28
29    fn target_problem(&self) -> &Self::Target {
30        &self.target
31    }
32
33    /// Solution extraction: identity mapping.
34    /// Partition config (0/1 for subset) maps directly to processor assignment (0/1).
35    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
36        target_solution.to_vec()
37    }
38}
39
40#[reduction(overhead = {
41    num_tasks = "num_elements",
42})]
43impl ReduceTo<MultiprocessorScheduling> for Partition {
44    type Result = ReductionPartitionToMPS;
45
46    fn reduce_to(&self) -> Self::Result {
47        let lengths: Vec<u64> = self.sizes().to_vec();
48        let deadline = self.total_sum() / 2;
49
50        ReductionPartitionToMPS {
51            target: MultiprocessorScheduling::new(lengths, 2, deadline),
52        }
53    }
54}
55
56#[cfg(feature = "example-db")]
57pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
58    use crate::export::SolutionPair;
59
60    vec![crate::example_db::specs::RuleExampleSpec {
61        id: "partition_to_multiprocessorscheduling",
62        build: || {
63            // sizes [1, 2, 3, 4], sum=10, target=5
64            // partition: {1,4} on proc 0 and {2,3} on proc 1
65            crate::example_db::specs::rule_example_with_witness::<_, MultiprocessorScheduling>(
66                Partition::new(vec![1, 2, 3, 4]),
67                SolutionPair {
68                    source_config: vec![0, 1, 1, 0],
69                    target_config: vec![0, 1, 1, 0],
70                },
71            )
72        },
73    }]
74}
75
76#[cfg(test)]
77#[path = "../unit_tests/rules/partition_multiprocessorscheduling.rs"]
78mod tests;
problemreductions/rules/partition_multiprocessorscheduling.rs

problemreductions/rules/
partition_multiprocessorscheduling.rs
