problemreductions/rules/
partition_sequencingtominimizetardytaskweight.rs

1//! Reduction from Partition to Sequencing to Minimize Tardy Task Weight.
2
3use crate::models::misc::{Partition, SequencingToMinimizeTardyTaskWeight};
4use crate::reduction;
5use crate::rules::traits::{ReduceTo, ReductionResult};
6
7/// Result of reducing Partition to SequencingToMinimizeTardyTaskWeight.
8#[derive(Debug, Clone)]
9pub struct ReductionPartitionToSequencingToMinimizeTardyTaskWeight {
10    target: SequencingToMinimizeTardyTaskWeight,
11}
12
13impl ReductionResult for ReductionPartitionToSequencingToMinimizeTardyTaskWeight {
14    type Source = Partition;
15    type Target = SequencingToMinimizeTardyTaskWeight;
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 mut source_config = vec![true; self.target.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.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.deadlines()[task] {
46                    source_config[task] = false;
47                }
48            }
49
50            source_config
51        })
52    }
53}
54
55impl crate::rules::AggregateReductionResult
56    for ReductionPartitionToSequencingToMinimizeTardyTaskWeight
57{
58    type Source = Partition;
59    type Target = SequencingToMinimizeTardyTaskWeight;
60
61    fn target_problem(&self) -> &Self::Target {
62        &self.target
63    }
64
65    fn extract_value(&self, value: crate::types::Min<i64>) -> crate::types::Or {
66        // The source is nonempty, so the common deadline always exists.
67        crate::types::Or(value.0 == Some(self.target.deadlines()[0]))
68    }
69}
70
71#[reduction(
72    aggregate = custom,
73    transform = exact {
74        num_tasks = "num_elements",
75    })]
76impl ReduceTo<SequencingToMinimizeTardyTaskWeight> for Partition {
77    type Result = ReductionPartitionToSequencingToMinimizeTardyTaskWeight;
78
79    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
80        let common_deadline = self.total_sum() / 2;
81        let lengths = self.sizes().to_vec();
82        let weights = self.sizes().to_vec();
83        let deadlines = vec![common_deadline; self.num_elements()];
84
85        Ok(ReductionPartitionToSequencingToMinimizeTardyTaskWeight {
86            target: SequencingToMinimizeTardyTaskWeight::new(lengths, weights, deadlines),
87        })
88    }
89}
90
91#[cfg(feature = "example-db")]
92pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
93    use crate::export::SolutionPair;
94
95    vec![crate::example_db::specs::RuleExampleSpec {
96        id: "partition_to_sequencing_to_minimize_tardy_task_weight",
97        build: || {
98            crate::example_db::specs::rule_example_with_witness::<
99                _,
100                SequencingToMinimizeTardyTaskWeight,
101            >(
102                Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap(),
103                SolutionPair {
104                    source_config: serde_json::json!(vec![true, false, false, true, false, false]),
105                    target_config: serde_json::json!(vec![1, 2, 4, 5, 0, 3]),
106                },
107            )
108        },
109    }]
110}
111
112#[cfg(test)]
113#[path = "../unit_tests/rules/partition_sequencingtominimizetardytaskweight.rs"]
114mod tests;
problemreductions/rules/partition_sequencingtominimizetardytaskweight.rs

problemreductions/rules/
partition_sequencingtominimizetardytaskweight.rs
