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    /// Returns the number of tasks.
115    pub fn num_tasks(&self) -> usize {
116        self.lengths.len()
117    }
118
119    /// Returns the number of distinct compilers (= `setup_times.len()`).
120    pub fn num_compilers(&self) -> usize {
121        self.setup_times.len()
122    }
123
124    /// Returns the processing times.
125    pub fn lengths(&self) -> &[i64] {
126        &self.lengths
127    }
128
129    /// Returns the task deadlines.
130    pub fn deadlines(&self) -> &[i64] {
131        &self.deadlines
132    }
133
134    /// Returns the compiler index for each task.
135    pub fn compilers(&self) -> &[usize] {
136        &self.compilers
137    }
138
139    /// Returns the per-compiler setup times.
140    pub fn setup_times(&self) -> &[i64] {
141        &self.setup_times
142    }
143
144    /// Check whether a schedule meets all deadlines.
145    ///
146    /// Returns `true` iff every task in the schedule completes by its deadline.
147    fn all_deadlines_met(
148        &self,
149        schedule: &[usize],
150    ) -> Result<bool, crate::traits::EvaluationError> {
151        let mut elapsed: i64 = 0;
152        let mut prev_compiler: Option<usize> = None;
153        for &task in schedule {
154            // Add setup time if the compiler switches.
155            if let Some(prev) = prev_compiler {
156                if prev != self.compilers[task] {
157                    elapsed = elapsed
158                        .checked_add(self.setup_times[self.compilers[task]])
159                        .ok_or_else(|| {
160                            crate::traits::EvaluationError::IntegerOverflow(
161                                "adding sequencing setup time".to_string(),
162                            )
163                        })?;
164                }
165            }
166            elapsed = elapsed.checked_add(self.lengths[task]).ok_or_else(|| {
167                crate::traits::EvaluationError::IntegerOverflow(
168                    "adding sequencing task length".to_string(),
169                )
170            })?;
171            if elapsed > self.deadlines[task] {
172                return Ok(false);
173            }
174            prev_compiler = Some(self.compilers[task]);
175        }
176        Ok(true)
177    }
178}
179
180impl TryFrom<SequencingWithDeadlinesAndSetUpTimesSerde> for SequencingWithDeadlinesAndSetUpTimes {
181    type Error = crate::registry::ConstructionError;
182
183    fn try_from(value: SequencingWithDeadlinesAndSetUpTimesSerde) -> Result<Self, Self::Error> {
184        Self::validate(
185            &value.lengths,
186            &value.deadlines,
187            &value.compilers,
188            &value.setup_times,
189        )?;
190        Ok(Self {
191            lengths: value.lengths,
192            deadlines: value.deadlines,
193            compilers: value.compilers,
194            setup_times: value.setup_times,
195        })
196    }
197}
198
199impl<'de> Deserialize<'de> for SequencingWithDeadlinesAndSetUpTimes {
200    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
201    where
202        D: serde::Deserializer<'de>,
203    {
204        let value = SequencingWithDeadlinesAndSetUpTimesSerde::deserialize(deserializer)?;
205        Self::try_from(value).map_err(serde::de::Error::custom)
206    }
207}
208
209impl Problem for SequencingWithDeadlinesAndSetUpTimes {
210    const NAME: &'static str = "SequencingWithDeadlinesAndSetUpTimes";
211    type Solution = Vec<usize>;
212    type Value = Or;
213
214    crate::problem_parameters![("num_tasks", num_tasks),];
215
216    fn variant() -> Vec<(&'static str, &'static str)> {
217        crate::variant_params![]
218    }
219
220    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
221        let n = self.num_tasks();
222        if config.len() != n {
223            return Err(crate::traits::EvaluationError::InvalidConfiguration(
224                "schedule length does not match the tasks".into(),
225            ));
226        }
227        if config.iter().any(|&task| task >= n) {
228            return Err(crate::traits::EvaluationError::InvalidConfiguration(
229                "schedule contains an out-of-range task".into(),
230            ));
231        }
232        Ok({
233            let Some(schedule) = super::decode_permutation(config, n) else {
234                return Ok(Or(false));
235            };
236            Or(self.all_deadlines_met(&schedule)?)
237        })
238    }
239}
240
241impl crate::solvers::BruteForceProblem for SequencingWithDeadlinesAndSetUpTimes {
242    fn dimensions(&self) -> Vec<usize> {
243        let n = self.num_tasks();
244        vec![n; n]
245    }
246}
247
248crate::declare_variants! {
249    default SequencingWithDeadlinesAndSetUpTimes => "factorial(num_tasks)",
250}
251
252crate::register_brute_force! {
253    SequencingWithDeadlinesAndSetUpTimes,
254}
255
256#[cfg(feature = "example-db")]
257pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
258    vec![crate::example_db::specs::ModelExampleSpec {
259        id: "sequencing_with_deadlines_and_set_up_times",
260        // 5 tasks, lengths [2,3,1,2,2], deadlines [4,11,3,16,7], compilers [0,1,0,1,0],
261        // setup_times [1,2].
262        // Optimal config: [2,0,4,1,3] (tasks t3,t1,t5,t2,t4 in 1-indexed)
263        // Position 0: task 2 (compiler 0), no prev  → elapsed = 0+1 = 1  ≤ d[2]=3 ✓
264        // Position 1: task 0 (compiler 0), same     → elapsed = 1+2 = 3  ≤ d[0]=4 ✓
265        // Position 2: task 4 (compiler 0), same     → elapsed = 3+2 = 5  ≤ d[4]=7 ✓
266        // Position 3: task 1 (compiler 1), switch+s[1]=2 → elapsed = 5+2+3 = 10 ≤ d[1]=11 ✓
267        // Position 4: task 3 (compiler 1), same     → elapsed = 10+2 = 12 ≤ d[3]=16 ✓
268        instance: Box::new(SequencingWithDeadlinesAndSetUpTimes::new(
269            vec![2, 3, 1, 2, 2],
270            vec![4, 11, 3, 16, 7],
271            vec![0, 1, 0, 1, 0],
272            vec![1, 2],
273        )),
274        optimal_config: serde_json::json!(vec![2, 0, 4, 1, 3]),
275        optimal_value: serde_json::json!(true),
276    }]
277}
278
279#[cfg(test)]
280#[path = "../../unit_tests/models/misc/sequencing_with_deadlines_and_set_up_times.rs"]
281mod tests;
problemreductions/models/misc/sequencing_with_deadlines_and_set_up_times.rs

problemreductions/models/misc/
sequencing_with_deadlines_and_set_up_times.rs
