problemreductions/rules/
threepartition_sequencingwithreleasetimesanddeadlines.rs

1//! Reduction from ThreePartition to SequencingWithReleaseTimesAndDeadlines.
2//!
3//! Given a 3-Partition instance with 3m elements of sizes s(a_i) and bound B,
4//! construct a single-machine scheduling instance with:
5//! - 3m element tasks: length = s(a_i), release = 0, deadline = m*B + (m-1)
6//! - (m-1) filler tasks: length = 1, release = (j+1)*B + j, deadline = (j+1)*B + j + 1
7//!
8//! The filler tasks partition the timeline into m slots of width B each. Since
9//! B/4 < s(a_i) < B/2, exactly 3 element tasks must fit in each slot, yielding
10//! a valid 3-partition iff the schedule is feasible.
11//!
12//! Reference: Garey & Johnson, *Computers and Intractability*, Section 4.2.
13
14use crate::models::misc::{SequencingWithReleaseTimesAndDeadlines, ThreePartition};
15use crate::reduction;
16use crate::rules::traits::{ReduceTo, ReductionResult};
17
18/// Number of element tasks (= source.num_elements() = 3m).
19fn num_element_tasks(source: &ThreePartition) -> usize {
20    source.num_elements()
21}
22
23/// Number of filler tasks (= m - 1).
24fn num_filler_tasks(source: &ThreePartition) -> usize {
25    source.num_groups() - 1
26}
27
28/// Result of reducing ThreePartition to SequencingWithReleaseTimesAndDeadlines.
29#[derive(Debug, Clone)]
30pub struct ReductionThreePartitionToSRTD {
31    target: SequencingWithReleaseTimesAndDeadlines,
32    /// Number of element tasks (3m) — first 3m tasks in the target are element tasks.
33    num_element_tasks: usize,
34    /// The bound B from the source.
35    bound: i64,
36}
37
38impl ReductionResult for ReductionThreePartitionToSRTD {
39    type Source = ThreePartition;
40    type Target = SequencingWithReleaseTimesAndDeadlines;
41
42    fn target_problem(&self) -> &Self::Target {
43        &self.target
44    }
45
46    /// Extract a ThreePartition config from a target schedule config.
47    ///
48    /// Simulate the task permutation to find each task's start time, then assign each element task to its slot
49    /// based on start_time / (B + 1).
50    fn extract_solution(
51        &self,
52        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
53    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
54        crate::rules::traits::validate_target_witness(
55            self.target_problem(),
56            target_solution,
57            |value| value.0,
58            "target witness does not satisfy the target problem",
59        )?;
60
61        Ok({
62            // Simulate the schedule to find start times
63            let mut current_time: i64 = 0;
64            let mut slot_assignment = vec![0usize; self.num_element_tasks];
65            let slot_width = self.bound.checked_add(1).ok_or_else(|| {
66                crate::rules::ExtractionError::invalid("slot width overflows i64")
67            })?; // B + 1 (slot width including the filler gap)
68
69            for &task in target_solution {
70                let start = current_time.max(self.target.release_times()[task]);
71                let finish = start
72                    .checked_add(self.target.lengths()[task])
73                    .ok_or_else(|| {
74                        crate::rules::ExtractionError::invalid("task finish time overflows i64")
75                    })?;
76                current_time = finish;
77
78                // Only element tasks (indices 0..3m) contribute to the partition
79                if task < self.num_element_tasks {
80                    let slot = usize::try_from(start / slot_width).map_err(|_| {
81                        crate::rules::ExtractionError::invalid(
82                            "decoded task slot cannot be represented as usize",
83                        )
84                    })?;
85                    slot_assignment[task] = slot;
86                }
87            }
88
89            slot_assignment
90        })
91    }
92}
93
94#[crate::aggregate_reduction(identity)]
95impl crate::rules::AggregateReductionResult for ReductionThreePartitionToSRTD {}
96
97#[reduction(
98    transform = {
99        // Validated ThreePartition inputs have at least one group.
100        exact {
101            num_tasks = "num_elements + num_groups - 1",
102            time_horizon = "num_groups * (bound + 1) - 1",
103        },
104        upper_bound { time_horizon_bits = "max_numeric_magnitude_bits + num_groups + 1", },
105    },
106)]
107impl ReduceTo<SequencingWithReleaseTimesAndDeadlines> for ThreePartition {
108    type Result = ReductionThreePartitionToSRTD;
109
110    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
111        let n_elem = num_element_tasks(self);
112        let n_fill = num_filler_tasks(self);
113        let m = self.num_groups();
114        let b = self.bound();
115        let overflow = |operation| {
116            crate::rules::ReductionError::integer_overflow::<
117                Self,
118                SequencingWithReleaseTimesAndDeadlines,
119            >(operation)
120        };
121        let total_tasks = n_elem
122            .checked_add(n_fill)
123            .ok_or_else(|| overflow("computing the target task count"))?;
124
125        // Time horizon: m*B + (m-1) = m*(B+1) - 1
126        let group_count =
127            i64::try_from(m).map_err(|_| overflow("converting the group count to i64"))?;
128        let slot_width = b
129            .checked_add(1)
130            .ok_or_else(|| overflow("computing the slot width"))?;
131        let horizon = group_count
132            .checked_mul(slot_width)
133            .and_then(|value| value.checked_sub(1))
134            .ok_or_else(|| overflow("computing the scheduling horizon"))?;
135
136        let mut lengths = Vec::with_capacity(total_tasks);
137        let mut release_times = Vec::with_capacity(total_tasks);
138        let mut deadlines = Vec::with_capacity(total_tasks);
139
140        // Element tasks (indices 0..3m)
141        for &size in self.sizes() {
142            lengths.push(size);
143            release_times.push(0);
144            deadlines.push(horizon);
145        }
146
147        // Filler tasks (indices 3m..4m-1)
148        for j in 0..n_fill {
149            // Filler j separates slot j from slot j+1
150            // Release = (j+1)*B + j, Deadline = (j+1)*B + j + 1
151            let separator =
152                i64::try_from(j).map_err(|_| overflow("converting a filler-task index to i64"))?;
153            let next_separator = separator
154                .checked_add(1)
155                .ok_or_else(|| overflow("computing a filler-task index"))?;
156            let release = next_separator
157                .checked_mul(b)
158                .and_then(|value| value.checked_add(separator))
159                .ok_or_else(|| overflow("computing a filler-task release time"))?;
160            lengths.push(1);
161            release_times.push(release);
162            deadlines.push(
163                release
164                    .checked_add(1)
165                    .ok_or_else(|| overflow("computing a filler-task deadline"))?,
166            );
167        }
168
169        Ok(ReductionThreePartitionToSRTD {
170            target: SequencingWithReleaseTimesAndDeadlines::new(lengths, release_times, deadlines),
171            num_element_tasks: n_elem,
172            bound: b,
173        })
174    }
175}
176
177#[cfg(feature = "example-db")]
178pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
179    use crate::export::SolutionPair;
180
181    vec![crate::example_db::specs::RuleExampleSpec {
182        id: "threepartition_to_sequencingwithreleasetimesanddeadlines",
183        build: || {
184            // ThreePartition: sizes=[4,5,6,4,6,5], bound=15, m=2
185            // Groups: {4,5,6}=15, {4,6,5}=15
186            // Source config: [0,0,0,1,1,1] (elements 0,1,2 in group 0; 3,4,5 in group 1)
187            //
188            // Target: 6 element tasks + 1 filler = 7 tasks
189            // Schedule for source config [0,0,0,1,1,1]:
190            //   Slot 0 [0,15): tasks 0(len=4), 1(len=5), 2(len=6) -> times [0,4), [4,9), [9,15)
191            //   Filler [15,16): task 6(len=1)
192            //   Slot 1 [16,31): tasks 3(len=4), 4(len=6), 5(len=5) -> times [16,20), [20,26), [26,31)
193            // Permutation: [0,1,2,6,3,4,5]
194            // Lehmer code: [0,0,0,3,0,0,0]
195            //   remaining=[0,1,2,3,4,5,6], pick 0 -> 0, remaining=[1,2,3,4,5,6]
196            //   remaining=[1,2,3,4,5,6], pick 0 -> 1, remaining=[2,3,4,5,6]
197            //   remaining=[2,3,4,5,6], pick 0 -> 2, remaining=[3,4,5,6]
198            //   remaining=[3,4,5,6], pick 3 -> 6, remaining=[3,4,5]
199            //   remaining=[3,4,5], pick 0 -> 3, remaining=[4,5]
200            //   remaining=[4,5], pick 0 -> 4, remaining=[5]
201            //   remaining=[5], pick 0 -> 5
202            crate::example_db::specs::rule_example_with_witness::<
203                _,
204                SequencingWithReleaseTimesAndDeadlines,
205            >(
206                ThreePartition::new(vec![4, 5, 6, 4, 6, 5], 15),
207                SolutionPair {
208                    source_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
209                    target_config: serde_json::json!(vec![0, 1, 2, 6, 3, 4, 5]),
210                },
211            )
212        },
213    }]
214}
215
216#[cfg(test)]
217#[path = "../unit_tests/rules/threepartition_sequencingwithreleasetimesanddeadlines.rs"]
218mod tests;
problemreductions/rules/threepartition_sequencingwithreleasetimesanddeadlines.rs

problemreductions/rules/
threepartition_sequencingwithreleasetimesanddeadlines.rs
