problemreductions/models/misc/
sequencing_with_deadlines_and_set_up_times.rs

1//! Sequencing with Deadlines and Set-Up Times problem implementation.
2//!
3//! A classical NP-hard single-machine scheduling feasibility problem (SS14
4//! from Garey & Johnson, 1979) where tasks use one of several compilers and
5//! a setup time is charged whenever consecutive tasks switch compilers.
6//! The question is whether all deadlines can be met.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use crate::types::Or;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "SequencingWithDeadlinesAndSetUpTimes",
16        display_name: "Sequencing with Deadlines and Set-Up Times",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Misc,
20        module_path: module_path!(),
21        description: "Determine whether all tasks can be scheduled on a single machine by their deadlines given compiler-switch setup penalties",
22        fields: &[
23            FieldInfo { name: "lengths", type_name: "Vec<i64>", description: "Processing time for each task" },
24            FieldInfo { name: "deadlines", type_name: "Vec<i64>", description: "Deadline d(t) for each task" },
25            FieldInfo { name: "compilers", type_name: "Vec<usize>", description: "Compiler index k(t) for each task" },
26            FieldInfo { name: "setup_times", type_name: "Vec<i64>", description: "Setup time s(c) charged when switching to compiler c" },
27        ],
28    }
29}
30
31/// Sequencing with Deadlines and Set-Up Times problem.
32///
33/// Given tasks with processing times `l(t)`, deadlines `d(t)`, compiler
34/// assignments `k(t)`, and per-compiler setup times `s(c)`, find a
35/// single-machine schedule in which all tasks meet their deadlines, where a
36/// setup penalty `s(k(t'))` is added before any task `t` that uses a
37/// different compiler than the immediately preceding task `t'`.
38///
39/// This is problem SS14 in Garey & Johnson (1979), written
40/// $1 | s_{ij} | \text{feasibility}$.
41///
42/// Configurations are direct permutation encodings with `dims() = [n; n]`:
43/// each position holds the index of the task scheduled at that position.
44/// A configuration is valid iff it is a permutation of `0..n`.
45#[derive(Debug, Clone, Serialize)]
46pub struct SequencingWithDeadlinesAndSetUpTimes {
47    lengths: Vec<i64>,
48    deadlines: Vec<i64>,
49    compilers: Vec<usize>,
50    setup_times: Vec<i64>,
51}
52
53#[derive(Deserialize)]
54struct SequencingWithDeadlinesAndSetUpTimesSerde {
55    lengths: Vec<i64>,
56    deadlines: Vec<i64>,
57    compilers: Vec<usize>,
58    setup_times: Vec<i64>,
59}
60
61impl SequencingWithDeadlinesAndSetUpTimes {
62    fn validate(
63        lengths: &[i64],
64        deadlines: &[i64],
65        compilers: &[usize],
66        setup_times: &[i64],
67    ) -> Result<(), crate::registry::ConstructionError> {
68        if lengths.len() != deadlines.len() {
69            return Err("lengths length must equal deadlines length"
70                .to_string()
71                .into());
72        }
73        if lengths.len() != compilers.len() {
74            return Err("lengths length must equal compilers length"
75                .to_string()
76                .into());
77        }
78        if lengths.contains(&0) {
79            return Err("task lengths must be positive".to_string().into());
80        }
81        let num_compilers = setup_times.len();
82        for &c in compilers {
83            if c >= num_compilers {
84                return Err(format!(
85                    "compiler index {c} is out of range for setup_times of length {num_compilers}"
86                )
87                .into());
88            }
89        }
90        Ok(())
91    }
92
93    /// Create a new sequencing instance.
94    ///
95    /// # Panics
96    ///
97    /// Panics if the input vectors are inconsistent or contain invalid values.
98    pub fn new(
99        lengths: Vec<i64>,
100        deadlines: Vec<i64>,
101        compilers: Vec<usize>,
102        setup_times: Vec<i64>,
103    ) -> Self {
104        Self::validate(&lengths, &deadlines, &compilers, &setup_times)
105            .unwrap_or_else(|err| panic!("{err}"));
106        Self {
107            lengths,
108            deadlines,
109            compilers,
110            setup_times,
111        }
112    }
113
114    /// Smallest h >= 1 bounding lengths, deadlines, and setup times in magnitude by 2^h.
115    pub fn max_time_bits(&self) -> u64 {
116        crate::types::max_numeric_magnitude_bits(
117            self.lengths
118                .iter()
119                .chain(&self.deadlines)
120                .chain(&self.setup_times)
121                .copied(),
122        )
123    }
124
125    /// Returns the number of tasks.
126    pub fn num_tasks(&self) -> usize {
127        self.lengths.len()
128    }
129
130    /// Returns the number of distinct compilers (= `setup_times.len()`).
131    pub fn num_compilers(&self) -> usize {
132        self.setup_times.len()
133    }
134
135    /// Returns the processing times.
136    pub fn lengths(&self) -> &[i64] {
137        &self.lengths
138    }
139
140    /// Returns the task deadlines.
141    pub fn deadlines(&self) -> &[i64] {
142        &self.deadlines
143    }
144
145    /// Returns the compiler index for each task.
146    pub fn compilers(&self) -> &[usize] {
147        &self.compilers
148    }
149
150    /// Returns the per-compiler setup times.
151    pub fn setup_times(&self) -> &[i64] {
152        &self.setup_times
153    }
154
155    /// Check whether a schedule meets all deadlines.
156    ///
157    /// Returns `true` iff every task in the schedule completes by its deadline.
158    fn all_deadlines_met(
159        &self,
160        schedule: &[usize],
161    ) -> Result<bool, crate::traits::EvaluationError> {
162        let mut elapsed: i64 = 0;
163        let mut prev_compiler: Option<usize> = None;
164        for &task in schedule {
165            // Add setup time if the compiler switches.
166            if let Some(prev) = prev_compiler {
167                if prev != self.compilers[task] {
168                    elapsed = elapsed
169                        .checked_add(self.setup_times[self.compilers[task]])
170                        .ok_or_else(|| {
171                            crate::traits::EvaluationError::IntegerOverflow(
172                                "adding sequencing setup time".to_string(),
173                            )
174                        })?;
175                }
176            }
177            elapsed = elapsed.checked_add(self.lengths[task]).ok_or_else(|| {
178                crate::traits::EvaluationError::IntegerOverflow(
179                    "adding sequencing task length".to_string(),
180                )
181            })?;
182            if elapsed > self.deadlines[task] {
183                return Ok(false);
184            }
185            prev_compiler = Some(self.compilers[task]);
186        }
187        Ok(true)
188    }
189}
190
191impl TryFrom<SequencingWithDeadlinesAndSetUpTimesSerde> for SequencingWithDeadlinesAndSetUpTimes {
192    type Error = crate::registry::ConstructionError;
193
194    fn try_from(value: SequencingWithDeadlinesAndSetUpTimesSerde) -> Result<Self, Self::Error> {
195        Self::validate(
196            &value.lengths,
197            &value.deadlines,
198            &value.compilers,
199            &value.setup_times,
200        )?;
201        Ok(Self {
202            lengths: value.lengths,
203            deadlines: value.deadlines,
204            compilers: value.compilers,
205            setup_times: value.setup_times,
206        })
207    }
208}
209
210impl<'de> Deserialize<'de> for SequencingWithDeadlinesAndSetUpTimes {
211    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
212    where
213        D: serde::Deserializer<'de>,
214    {
215        let value = SequencingWithDeadlinesAndSetUpTimesSerde::deserialize(deserializer)?;
216        Self::try_from(value).map_err(serde::de::Error::custom)
217    }
218}
219
220impl Problem for SequencingWithDeadlinesAndSetUpTimes {
221    const NAME: &'static str = "SequencingWithDeadlinesAndSetUpTimes";
222    type Solution = Vec<usize>;
223    type Value = Or;
224
225    crate::problem_parameters![("max_time_bits", max_time_bits), ("num_tasks", num_tasks),];
226
227    fn variant() -> Vec<(&'static str, &'static str)> {
228        crate::variant_params![]
229    }
230
231    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
232        let n = self.num_tasks();
233        if config.len() != n {
234            return Err(crate::traits::EvaluationError::InvalidConfiguration(
235                "schedule length does not match the tasks".into(),
236            ));
237        }
238        if config.iter().any(|&task| task >= n) {
239            return Err(crate::traits::EvaluationError::InvalidConfiguration(
240                "schedule contains an out-of-range task".into(),
241            ));
242        }
243        Ok({
244            let Some(schedule) = super::decode_permutation(config, n) else {
245                return Ok(Or(false));
246            };
247            Or(self.all_deadlines_met(&schedule)?)
248        })
249    }
250}
251
252impl crate::solvers::BruteForceProblem for SequencingWithDeadlinesAndSetUpTimes {
253    fn dimensions(&self) -> Vec<usize> {
254        let n = self.num_tasks();
255        vec![n; n]
256    }
257}
258
259crate::declare_variants! {
260    default SequencingWithDeadlinesAndSetUpTimes => "factorial(num_tasks)",
261}
262
263crate::register_brute_force! {
264    SequencingWithDeadlinesAndSetUpTimes,
265}
266
267#[cfg(feature = "example-db")]
268pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
269    vec![crate::example_db::specs::ModelExampleSpec {
270        id: "sequencing_with_deadlines_and_set_up_times",
271        // 5 tasks, lengths [2,3,1,2,2], deadlines [4,11,3,16,7], compilers [0,1,0,1,0],
272        // setup_times [1,2].
273        // Optimal config: [2,0,4,1,3] (tasks t3,t1,t5,t2,t4 in 1-indexed)
274        // Position 0: task 2 (compiler 0), no prev  → elapsed = 0+1 = 1  ≤ d[2]=3 ✓
275        // Position 1: task 0 (compiler 0), same     → elapsed = 1+2 = 3  ≤ d[0]=4 ✓
276        // Position 2: task 4 (compiler 0), same     → elapsed = 3+2 = 5  ≤ d[4]=7 ✓
277        // Position 3: task 1 (compiler 1), switch+s[1]=2 → elapsed = 5+2+3 = 10 ≤ d[1]=11 ✓
278        // Position 4: task 3 (compiler 1), same     → elapsed = 10+2 = 12 ≤ d[3]=16 ✓
279        instance: Box::new(SequencingWithDeadlinesAndSetUpTimes::new(
280            vec![2, 3, 1, 2, 2],
281            vec![4, 11, 3, 16, 7],
282            vec![0, 1, 0, 1, 0],
283            vec![1, 2],
284        )),
285        optimal_config: serde_json::json!(vec![2, 0, 4, 1, 3]),
286        optimal_value: serde_json::json!(true),
287    }]
288}
289
290#[cfg(test)]
291#[path = "../../unit_tests/models/misc/sequencing_with_deadlines_and_set_up_times.rs"]
292mod tests;
problemreductions/models/misc/sequencing_with_deadlines_and_set_up_times.rs

problemreductions/models/misc/
sequencing_with_deadlines_and_set_up_times.rs
