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(
36        &self,
37        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
38    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
39        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
40
41        Ok(target_solution
42            .iter()
43            .map(|&processor| processor == 1)
44            .collect())
45    }
46}
47
48#[reduction(
49    transform = exact {
50        num_tasks = "num_elements",
51    },
52    unavailable = {
53        num_processors = "the exact target parameter is not represented by this reduction's symbolic transform",
54    }
55)]
56impl ReduceTo<MultiprocessorScheduling> for Partition {
57    type Result = ReductionPartitionToMPS;
58
59    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
60        let lengths: Vec<i64> = self.sizes().to_vec();
61        let deadline = self.total_sum() / 2;
62
63        Ok(ReductionPartitionToMPS {
64            target: MultiprocessorScheduling::new(lengths, 2, deadline),
65        })
66    }
67}
68
69#[cfg(feature = "example-db")]
70pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
71    use crate::export::SolutionPair;
72
73    vec![crate::example_db::specs::RuleExampleSpec {
74        id: "partition_to_multiprocessorscheduling",
75        build: || {
76            // sizes [1, 2, 3, 4], sum=10, target=5
77            // partition: {1,4} on proc 0 and {2,3} on proc 1
78            crate::example_db::specs::rule_example_with_witness::<_, MultiprocessorScheduling>(
79                Partition::new(vec![1, 2, 3, 4]).unwrap(),
80                SolutionPair {
81                    source_config: serde_json::json!(vec![false, true, true, false]),
82                    target_config: serde_json::json!(vec![0, 1, 1, 0]),
83                },
84            )
85        },
86    }]
87}
88
89#[cfg(test)]
90#[path = "../unit_tests/rules/partition_multiprocessorscheduling.rs"]
91mod tests;
problemreductions/rules/partition_multiprocessorscheduling.rs

problemreductions/rules/
partition_multiprocessorscheduling.rs
