problemreductions/rules/
partition_sequencingtominimizetardytaskweight.rs

1//! Reduction from Partition to Sequencing to Minimize Tardy Task Weight.
2
3use crate::models::decision::Decision;
4use crate::models::misc::{Partition, SequencingToMinimizeTardyTaskWeight};
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7
8/// Result of reducing Partition to SequencingToMinimizeTardyTaskWeight.
9#[derive(Debug, Clone)]
10pub struct ReductionPartitionToSequencingToMinimizeTardyTaskWeight {
11    target: Decision<SequencingToMinimizeTardyTaskWeight>,
12}
13
14impl ReductionResult for ReductionPartitionToSequencingToMinimizeTardyTaskWeight {
15    type Source = Partition;
16    type Target = Decision<SequencingToMinimizeTardyTaskWeight>;
17
18    fn target_problem(&self) -> &Self::Target {
19        &self.target
20    }
21
22    fn extract_solution(
23        &self,
24        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
25    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
26        crate::rules::traits::validate_target_witness(
27            self.target_problem(),
28            target_solution,
29            |value| value.0,
30            "target schedule does not certify a balanced partition",
31        )?;
32
33        Ok({
34            let mut source_config = vec![true; self.target.inner().num_tasks()];
35            let mut completion_time = 0i64;
36
37            for &task in target_solution {
38                completion_time = completion_time
39                    .checked_add(self.target.inner().lengths()[task])
40                    .ok_or_else(|| {
41                        crate::rules::ExtractionError::invalid(
42                            "target schedule completion time overflows i64",
43                        )
44                    })?;
45                if completion_time <= self.target.inner().deadlines()[task] {
46                    source_config[task] = false;
47                }
48            }
49
50            source_config
51        })
52    }
53}
54
55#[crate::aggregate_reduction(identity)]
56impl crate::rules::AggregateReductionResult
57    for ReductionPartitionToSequencingToMinimizeTardyTaskWeight
58{
59}
60
61#[reduction(
62    transform = exact {
63        max_processing_time_bits = "max_numeric_magnitude_bits",
64        num_tasks = "num_elements",
65    })]
66impl ReduceTo<Decision<SequencingToMinimizeTardyTaskWeight>> for Partition {
67    type Result = ReductionPartitionToSequencingToMinimizeTardyTaskWeight;
68
69    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
70        let common_deadline = self.total_sum() / 2;
71        let lengths = self.sizes().to_vec();
72        let weights = self.sizes().to_vec();
73        let deadlines = vec![common_deadline; self.num_elements()];
74
75        Ok(ReductionPartitionToSequencingToMinimizeTardyTaskWeight {
76            target: Decision::new(
77                SequencingToMinimizeTardyTaskWeight::new(lengths, weights, deadlines),
78                common_deadline,
79            ),
80        })
81    }
82}
83
84#[cfg(feature = "example-db")]
85pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
86    use crate::export::SolutionPair;
87
88    vec![crate::example_db::specs::RuleExampleSpec {
89        id: "partition_to_sequencing_to_minimize_tardy_task_weight",
90        build: || {
91            crate::example_db::specs::rule_example_with_witness::<
92                _,
93                Decision<SequencingToMinimizeTardyTaskWeight>,
94            >(
95                Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap(),
96                SolutionPair {
97                    source_config: serde_json::json!(vec![true, false, false, true, false, false]),
98                    target_config: serde_json::json!(vec![1, 2, 4, 5, 0, 3]),
99                },
100            )
101        },
102    }]
103}
104
105#[cfg(test)]
106#[path = "../unit_tests/rules/partition_sequencingtominimizetardytaskweight.rs"]
107mod tests;
problemreductions/rules/partition_sequencingtominimizetardytaskweight.rs

problemreductions/rules/
partition_sequencingtominimizetardytaskweight.rs
