problemreductions/models/misc/
sequencing_within_intervals.rs

1//! Sequencing Within Intervals problem implementation.
2//!
3//! Given a set of tasks, each with a release time, deadline, and processing length,
4//! determine whether all tasks can be scheduled non-overlappingly such that each
5//! task runs entirely within its allowed time window.
6
7use crate::registry::{ConstructionError, CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "SequencingWithinIntervals",
14        display_name: "Sequencing Within Intervals",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Misc,
18        module_path: module_path!(),
19        description: "Schedule tasks non-overlappingly within their time windows",
20        fields: SequencingWithinIntervalsCreateSpec::FIELDS,
21    }
22}
23
24/// Sequencing Within Intervals problem.
25///
26/// Given `n` tasks, each with release time `r(t)`, deadline `d(t)`, and processing
27/// length `l(t)`, determine whether there exists a schedule `sigma: T -> Z_>=0`
28/// such that:
29/// - `sigma(t) >= r(t)` (task starts no earlier than its release time)
30/// - `sigma(t) + l(t) <= d(t)` (task finishes by its deadline)
31/// - No two tasks overlap in time
32///
33/// This is problem SS1 from Garey & Johnson (1979), NP-complete via Theorem 3.8.
34///
35/// # Representation
36///
37/// Each task has a variable representing its start time offset from the release time.
38/// Variable `i` takes values in `{0, ..., d(i) - r(i) - l(i)}`, so the actual start
39/// time is `r(i) + config[i]`. If this range is empty, the instance is infeasible.
40///
41/// # Example
42///
43/// ```
44/// use problemreductions::models::misc::SequencingWithinIntervals;
45/// use problemreductions::{Problem, BruteForce};
46///
47/// // 3 tasks: release_times = [0, 2, 4], deadlines = [3, 5, 7], lengths = [2, 2, 2]
48/// let problem = SequencingWithinIntervals::new(vec![0, 2, 4], vec![3, 5, 7], vec![2, 2, 2]).unwrap();
49/// let solver = BruteForce::new();
50/// let solution = solver.solve(&problem).unwrap();
51/// assert!(solution.is_some());
52/// ```
53#[derive(Debug, Clone, Serialize)]
54pub struct SequencingWithinIntervals {
55    /// Release times for each task.
56    release_times: Vec<i64>,
57    /// Deadlines for each task.
58    deadlines: Vec<i64>,
59    /// Processing lengths for each task.
60    lengths: Vec<i64>,
61}
62
63#[derive(Debug, Deserialize, crate::CreateSpec)]
64struct SequencingWithinIntervalsCreateSpec {
65    /// Release times.
66    release_times: Vec<i64>,
67    /// Deadlines.
68    deadlines: Vec<i64>,
69    /// Processing lengths.
70    lengths: Vec<i64>,
71}
72impl TryFrom<SequencingWithinIntervalsCreateSpec> for SequencingWithinIntervals {
73    type Error = ConstructionError;
74    fn try_from(spec: SequencingWithinIntervalsCreateSpec) -> Result<Self, Self::Error> {
75        Self::new(spec.release_times, spec.deadlines, spec.lengths)
76    }
77}
78
79impl SequencingWithinIntervals {
80    /// Create a new SequencingWithinIntervals problem.
81    ///
82    pub fn new(
83        release_times: Vec<i64>,
84        deadlines: Vec<i64>,
85        lengths: Vec<i64>,
86    ) -> Result<Self, ConstructionError> {
87        if release_times.len() != deadlines.len() {
88            return Err(ConstructionError::Conversion(
89                "release_times and deadlines must have the same length".into(),
90            ));
91        }
92        if release_times.len() != lengths.len() {
93            return Err(ConstructionError::Conversion(
94                "release_times and lengths must have the same length".into(),
95            ));
96        }
97        if release_times.iter().any(|&release| release < 0)
98            || deadlines.iter().any(|&deadline| deadline < 0)
99            || lengths.iter().any(|&length| length < 0)
100        {
101            return Err(ConstructionError::Conversion(
102                "release times, deadlines, and lengths must be nonnegative".into(),
103            ));
104        }
105        let mut total_slots = 0usize;
106        for i in 0..release_times.len() {
107            let slots = start_slot_count(release_times[i], deadlines[i], lengths[i])?;
108            total_slots = total_slots.checked_add(slots).ok_or_else(|| {
109                ConstructionError::IntegerOverflow("total start-slot count exceeds usize".into())
110            })?;
111        }
112        Ok(Self {
113            release_times,
114            deadlines,
115            lengths,
116        })
117    }
118
119    /// Returns the release times.
120    pub fn release_times(&self) -> &[i64] {
121        &self.release_times
122    }
123
124    /// Returns the deadlines.
125    pub fn deadlines(&self) -> &[i64] {
126        &self.deadlines
127    }
128
129    /// Returns the processing lengths.
130    pub fn lengths(&self) -> &[i64] {
131        &self.lengths
132    }
133
134    /// Returns the number of tasks.
135    pub fn num_tasks(&self) -> usize {
136        self.release_times.len()
137    }
138
139    /// Return the total number of feasible start slots across all tasks.
140    pub fn num_start_slots(&self) -> usize {
141        self.start_slot_counts().sum()
142    }
143
144    pub(crate) fn start_slot_counts(&self) -> impl Iterator<Item = usize> + '_ {
145        self.release_times
146            .iter()
147            .zip(&self.deadlines)
148            .zip(&self.lengths)
149            .map(|((&release, &deadline), &length)| {
150                start_slot_count(release, deadline, length)
151                    .expect("start-slot count validated at construction")
152            })
153    }
154}
155
156fn start_slot_count(release: i64, deadline: i64, length: i64) -> Result<usize, ConstructionError> {
157    let latest_start = deadline - length;
158    if latest_start < release {
159        return Ok(0);
160    }
161    let count = (latest_start - release).checked_add(1).ok_or_else(|| {
162        ConstructionError::IntegerOverflow("task start-slot count overflows i64".into())
163    })?;
164    usize::try_from(count).map_err(|_| {
165        ConstructionError::IntegerOverflow("task start-slot count does not fit usize".into())
166    })
167}
168
169impl<'de> Deserialize<'de> for SequencingWithinIntervals {
170    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
171    where
172        D: serde::Deserializer<'de>,
173    {
174        #[derive(Deserialize)]
175        struct Raw {
176            release_times: Vec<i64>,
177            deadlines: Vec<i64>,
178            lengths: Vec<i64>,
179        }
180
181        let raw = Raw::deserialize(deserializer)?;
182        Self::new(raw.release_times, raw.deadlines, raw.lengths).map_err(serde::de::Error::custom)
183    }
184}
185
186impl Problem for SequencingWithinIntervals {
187    const NAME: &'static str = "SequencingWithinIntervals";
188    type Solution = Vec<usize>;
189    type Value = crate::types::Or;
190
191    crate::problem_parameters![
192        ("num_start_slots", num_start_slots),
193        ("num_tasks", num_tasks),
194    ];
195
196    fn variant() -> Vec<(&'static str, &'static str)> {
197        crate::variant_params![]
198    }
199
200    fn evaluate(
201        &self,
202        config: &Self::Solution,
203    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
204        Ok({
205            crate::types::Or({
206                let n = self.num_tasks();
207                if config.len() != n {
208                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
209                        "sequence length does not match the tasks".into(),
210                    ));
211                }
212
213                // Check each variable is within range and compute start times
214                let mut starts = Vec::with_capacity(n);
215                for (i, (&c, dim)) in config.iter().zip(self.start_slot_counts()).enumerate() {
216                    if c >= dim {
217                        return Err(crate::traits::EvaluationError::InvalidConfiguration(
218                            "schedule contains an out-of-range start offset".into(),
219                        ));
220                    }
221                    // start = r[i] + c, and c < dim = d[i] - r[i] - l[i] + 1,
222                    // so start + l[i] <= d[i] follows from the offset range check.
223                    let offset = i64::try_from(c).map_err(|_| {
224                        crate::traits::EvaluationError::IntegerOverflow(
225                            "converting a sequencing start offset to i64".into(),
226                        )
227                    })?;
228                    let start = self.release_times[i].checked_add(offset).ok_or_else(|| {
229                        crate::traits::EvaluationError::IntegerOverflow(
230                            "adding a sequencing start offset".into(),
231                        )
232                    })?;
233                    starts.push(start);
234                }
235                let ends = starts
236                    .iter()
237                    .zip(&self.lengths)
238                    .map(|(&start, &length)| {
239                        start.checked_add(length).ok_or_else(|| {
240                            crate::traits::EvaluationError::IntegerOverflow(
241                                "computing a sequencing task end".into(),
242                            )
243                        })
244                    })
245                    .collect::<Result<Vec<_>, _>>()?;
246
247                // Check no two tasks overlap
248                for i in 0..n {
249                    for j in (i + 1)..n {
250                        // Tasks overlap if neither finishes before the other starts
251                        if !(ends[i] <= starts[j] || ends[j] <= starts[i]) {
252                            return Ok(crate::types::Or(false));
253                        }
254                    }
255                }
256
257                true
258            })
259        })
260    }
261}
262
263impl crate::solvers::BruteForceProblem for SequencingWithinIntervals {
264    fn dimensions(&self) -> Vec<usize> {
265        self.start_slot_counts().collect()
266    }
267}
268
269crate::declare_variants! {
270    default SequencingWithinIntervals => "2^num_tasks" create SequencingWithinIntervalsCreateSpec,
271}
272
273crate::register_brute_force! {
274    SequencingWithinIntervals,
275}
276
277#[cfg(feature = "example-db")]
278pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
279    vec![crate::example_db::specs::ModelExampleSpec {
280        id: "sequencing_within_intervals",
281        instance: Box::new(
282            SequencingWithinIntervals::new(
283                vec![0, 1, 3, 6, 0],
284                vec![5, 8, 9, 12, 12],
285                vec![2, 2, 2, 3, 2],
286            )
287            .expect("canonical sequencing-within-intervals instance must be valid"),
288        ),
289        optimal_config: serde_json::json!(vec![0, 1, 1, 0, 9]),
290        optimal_value: serde_json::json!(true),
291    }]
292}
293
294#[cfg(test)]
295#[path = "../../unit_tests/models/misc/sequencing_within_intervals.rs"]
296mod tests;
problemreductions/models/misc/sequencing_within_intervals.rs

problemreductions/models/misc/
sequencing_within_intervals.rs
