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 ReductionPartitionToSequencingToMinimizeTardyTaskWeight {
14    fn decode_schedule(&self, target_solution: &[usize]) -> Vec<usize> {
15        let n = self.target.num_tasks();
16        assert_eq!(
17            target_solution.len(),
18            n,
19            "target solution length must equal target num_tasks"
20        );
21
22        // The target model uses direct permutation encoding (dims = [n; n]).
23        // Each position is a task index; the solver returns a valid permutation.
24        target_solution.to_vec()
25    }
26}
27
28impl ReductionResult for ReductionPartitionToSequencingToMinimizeTardyTaskWeight {
29    type Source = Partition;
30    type Target = SequencingToMinimizeTardyTaskWeight;
31
32    fn target_problem(&self) -> &Self::Target {
33        &self.target
34    }
35
36    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
37        let schedule = self.decode_schedule(target_solution);
38        let mut source_config = vec![1; self.target.num_tasks()];
39        let mut completion_time = 0u64;
40
41        for task in schedule {
42            completion_time = completion_time
43                .checked_add(self.target.lengths()[task])
44                .expect("completion time overflowed u64");
45            if completion_time <= self.target.deadlines()[task] {
46                source_config[task] = 0;
47            }
48        }
49
50        source_config
51    }
52}
53
54#[reduction(overhead = {
55    num_tasks = "num_elements",
56})]
57impl ReduceTo<SequencingToMinimizeTardyTaskWeight> for Partition {
58    type Result = ReductionPartitionToSequencingToMinimizeTardyTaskWeight;
59
60    fn reduce_to(&self) -> Self::Result {
61        let common_deadline = self.total_sum() / 2;
62        let lengths = self.sizes().to_vec();
63        let weights = self.sizes().to_vec();
64        let deadlines = vec![common_deadline; self.num_elements()];
65
66        ReductionPartitionToSequencingToMinimizeTardyTaskWeight {
67            target: SequencingToMinimizeTardyTaskWeight::new(lengths, weights, deadlines),
68        }
69    }
70}
71
72#[cfg(feature = "example-db")]
73pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
74    use crate::export::SolutionPair;
75
76    vec![crate::example_db::specs::RuleExampleSpec {
77        id: "partition_to_sequencing_to_minimize_tardy_task_weight",
78        build: || {
79            crate::example_db::specs::rule_example_with_witness::<
80                _,
81                SequencingToMinimizeTardyTaskWeight,
82            >(
83                Partition::new(vec![3, 1, 1, 2, 2, 1]),
84                SolutionPair {
85                    source_config: vec![1, 0, 0, 1, 0, 0],
86                    target_config: vec![1, 2, 4, 5, 0, 3],
87                },
88            )
89        },
90    }]
91}
92
93#[cfg(test)]
94#[path = "../unit_tests/rules/partition_sequencingtominimizetardytaskweight.rs"]
95mod tests;
problemreductions/rules/partition_sequencingtominimizetardytaskweight.rs

problemreductions/rules/
partition_sequencingtominimizetardytaskweight.rs
