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_solution(self.target_problem(), target_solution)?;
55
56        Ok({
57            // Simulate the schedule to find start times
58            let mut current_time: i64 = 0;
59            let mut slot_assignment = vec![0usize; self.num_element_tasks];
60            let slot_width = self.bound.checked_add(1).ok_or_else(|| {
61                crate::rules::ExtractionError::invalid("slot width overflows i64")
62            })?; // B + 1 (slot width including the filler gap)
63
64            for &task in target_solution {
65                let start = current_time.max(self.target.release_times()[task]);
66                let finish = start
67                    .checked_add(self.target.lengths()[task])
68                    .ok_or_else(|| {
69                        crate::rules::ExtractionError::invalid("task finish time overflows i64")
70                    })?;
71                current_time = finish;
72
73                // Only element tasks (indices 0..3m) contribute to the partition
74                if task < self.num_element_tasks {
75                    let slot = usize::try_from(start / slot_width).map_err(|_| {
76                        crate::rules::ExtractionError::invalid(
77                            "decoded task slot cannot be represented as usize",
78                        )
79                    })?;
80                    slot_assignment[task] = slot;
81                }
82            }
83
84            slot_assignment
85        })
86    }
87}
88
89#[reduction(
90    transform = exact {
91        num_tasks = "num_elements + num_groups - 1",
92    },
93    unavailable = {
94        time_horizon = "the exact target parameter is not represented by this reduction's symbolic transform",
95    }
96)]
97impl ReduceTo<SequencingWithReleaseTimesAndDeadlines> for ThreePartition {
98    type Result = ReductionThreePartitionToSRTD;
99
100    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
101        let n_elem = num_element_tasks(self);
102        let n_fill = num_filler_tasks(self);
103        let m = self.num_groups();
104        let b = self.bound();
105        let overflow = |operation| {
106            crate::rules::ReductionError::integer_overflow::<
107                Self,
108                SequencingWithReleaseTimesAndDeadlines,
109            >(operation)
110        };
111        let total_tasks = n_elem
112            .checked_add(n_fill)
113            .ok_or_else(|| overflow("computing the target task count"))?;
114
115        // Time horizon: m*B + (m-1) = m*(B+1) - 1
116        let group_count =
117            i64::try_from(m).map_err(|_| overflow("converting the group count to i64"))?;
118        let slot_width = b
119            .checked_add(1)
120            .ok_or_else(|| overflow("computing the slot width"))?;
121        let horizon = group_count
122            .checked_mul(slot_width)
123            .and_then(|value| value.checked_sub(1))
124            .ok_or_else(|| overflow("computing the scheduling horizon"))?;
125
126        let mut lengths = Vec::with_capacity(total_tasks);
127        let mut release_times = Vec::with_capacity(total_tasks);
128        let mut deadlines = Vec::with_capacity(total_tasks);
129
130        // Element tasks (indices 0..3m)
131        for &size in self.sizes() {
132            lengths.push(size);
133            release_times.push(0);
134            deadlines.push(horizon);
135        }
136
137        // Filler tasks (indices 3m..4m-1)
138        for j in 0..n_fill {
139            // Filler j separates slot j from slot j+1
140            // Release = (j+1)*B + j, Deadline = (j+1)*B + j + 1
141            let separator =
142                i64::try_from(j).map_err(|_| overflow("converting a filler-task index to i64"))?;
143            let next_separator = separator
144                .checked_add(1)
145                .ok_or_else(|| overflow("computing a filler-task index"))?;
146            let release = next_separator
147                .checked_mul(b)
148                .and_then(|value| value.checked_add(separator))
149                .ok_or_else(|| overflow("computing a filler-task release time"))?;
150            lengths.push(1);
151            release_times.push(release);
152            deadlines.push(
153                release
154                    .checked_add(1)
155                    .ok_or_else(|| overflow("computing a filler-task deadline"))?,
156            );
157        }
158
159        Ok(ReductionThreePartitionToSRTD {
160            target: SequencingWithReleaseTimesAndDeadlines::new(lengths, release_times, deadlines),
161            num_element_tasks: n_elem,
162            bound: b,
163        })
164    }
165}
166
167#[cfg(feature = "example-db")]
168pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
169    use crate::export::SolutionPair;
170
171    vec![crate::example_db::specs::RuleExampleSpec {
172        id: "threepartition_to_sequencingwithreleasetimesanddeadlines",
173        build: || {
174            // ThreePartition: sizes=[4,5,6,4,6,5], bound=15, m=2
175            // Groups: {4,5,6}=15, {4,6,5}=15
176            // Source config: [0,0,0,1,1,1] (elements 0,1,2 in group 0; 3,4,5 in group 1)
177            //
178            // Target: 6 element tasks + 1 filler = 7 tasks
179            // Schedule for source config [0,0,0,1,1,1]:
180            //   Slot 0 [0,15): tasks 0(len=4), 1(len=5), 2(len=6) -> times [0,4), [4,9), [9,15)
181            //   Filler [15,16): task 6(len=1)
182            //   Slot 1 [16,31): tasks 3(len=4), 4(len=6), 5(len=5) -> times [16,20), [20,26), [26,31)
183            // Permutation: [0,1,2,6,3,4,5]
184            // Lehmer code: [0,0,0,3,0,0,0]
185            //   remaining=[0,1,2,3,4,5,6], pick 0 -> 0, remaining=[1,2,3,4,5,6]
186            //   remaining=[1,2,3,4,5,6], pick 0 -> 1, remaining=[2,3,4,5,6]
187            //   remaining=[2,3,4,5,6], pick 0 -> 2, remaining=[3,4,5,6]
188            //   remaining=[3,4,5,6], pick 3 -> 6, remaining=[3,4,5]
189            //   remaining=[3,4,5], pick 0 -> 3, remaining=[4,5]
190            //   remaining=[4,5], pick 0 -> 4, remaining=[5]
191            //   remaining=[5], pick 0 -> 5
192            crate::example_db::specs::rule_example_with_witness::<
193                _,
194                SequencingWithReleaseTimesAndDeadlines,
195            >(
196                ThreePartition::new(vec![4, 5, 6, 4, 6, 5], 15),
197                SolutionPair {
198                    source_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
199                    target_config: serde_json::json!(vec![0, 1, 2, 6, 3, 4, 5]),
200                },
201            )
202        },
203    }]
204}
205
206#[cfg(test)]
207#[path = "../unit_tests/rules/threepartition_sequencingwithreleasetimesanddeadlines.rs"]
208mod tests;
problemreductions/rules/threepartition_sequencingwithreleasetimesanddeadlines.rs

problemreductions/rules/
threepartition_sequencingwithreleasetimesanddeadlines.rs
