problemreductions/models/misc/
sequencing_with_release_times_and_deadlines.rs

1//! Sequencing with Release Times and Deadlines problem implementation.
2//!
3//! Given a set of tasks each with a processing time, release time, and deadline,
4//! determine whether all tasks can be non-preemptively scheduled on one processor
5//! such that each task starts after its release time and finishes by its deadline.
6//! Strongly NP-complete (Garey & Johnson, A5 SS1).
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "SequencingWithReleaseTimesAndDeadlines",
15        display_name: "Sequencing with Release Times and Deadlines",
16        aliases: &[],
17        dimensions: &[],
18        module_path: module_path!(),
19        description: "Single-machine scheduling feasibility: can all tasks be scheduled within their release-deadline windows without overlap?",
20        fields: &[
21            FieldInfo { name: "lengths", type_name: "Vec<u64>", description: "Processing time l(t) for each task (positive)" },
22            FieldInfo { name: "release_times", type_name: "Vec<u64>", description: "Release time r(t) for each task (non-negative)" },
23            FieldInfo { name: "deadlines", type_name: "Vec<u64>", description: "Deadline d(t) for each task (positive)" },
24        ],
25    }
26}
27
28/// Sequencing with Release Times and Deadlines.
29///
30/// Given a set of `n` tasks, each with a processing time `l(t)`, release time
31/// `r(t)`, and deadline `d(t)`, determine whether there exists a one-processor
32/// schedule where each task starts no earlier than its release time and finishes
33/// by its deadline, with no two tasks overlapping.
34///
35/// # Representation
36///
37/// Uses a permutation encoding (Lehmer code), where `config[i]` selects which
38/// remaining task to schedule next from the pool of unscheduled tasks.
39/// `dims() = [n, n-1, ..., 2, 1]`. Tasks are scheduled left-to-right: each
40/// task starts at `max(release_time, current_time)`. The schedule is feasible
41/// iff every task finishes by its deadline.
42///
43/// # Example
44///
45/// ```
46/// use problemreductions::models::misc::SequencingWithReleaseTimesAndDeadlines;
47/// use problemreductions::{Problem, Solver, BruteForce};
48///
49/// let problem = SequencingWithReleaseTimesAndDeadlines::new(
50///     vec![1, 2, 1],
51///     vec![0, 0, 2],
52///     vec![3, 3, 4],
53/// );
54/// let solver = BruteForce::new();
55/// let solution = solver.find_witness(&problem);
56/// assert!(solution.is_some());
57/// ```
58#[derive(Debug, Clone, Serialize, Deserialize)]
59pub struct SequencingWithReleaseTimesAndDeadlines {
60    lengths: Vec<u64>,
61    release_times: Vec<u64>,
62    deadlines: Vec<u64>,
63}
64
65impl SequencingWithReleaseTimesAndDeadlines {
66    /// Create a new instance.
67    ///
68    /// # Panics
69    ///
70    /// Panics if the three vectors have different lengths.
71    pub fn new(lengths: Vec<u64>, release_times: Vec<u64>, deadlines: Vec<u64>) -> Self {
72        assert_eq!(lengths.len(), release_times.len());
73        assert_eq!(lengths.len(), deadlines.len());
74        Self {
75            lengths,
76            release_times,
77            deadlines,
78        }
79    }
80
81    /// Returns the processing times.
82    pub fn lengths(&self) -> &[u64] {
83        &self.lengths
84    }
85
86    /// Returns the release times.
87    pub fn release_times(&self) -> &[u64] {
88        &self.release_times
89    }
90
91    /// Returns the deadlines.
92    pub fn deadlines(&self) -> &[u64] {
93        &self.deadlines
94    }
95
96    /// Returns the number of tasks.
97    pub fn num_tasks(&self) -> usize {
98        self.lengths.len()
99    }
100
101    /// Returns the time horizon (maximum deadline).
102    pub fn time_horizon(&self) -> u64 {
103        self.deadlines.iter().copied().max().unwrap_or(0)
104    }
105}
106
107impl Problem for SequencingWithReleaseTimesAndDeadlines {
108    const NAME: &'static str = "SequencingWithReleaseTimesAndDeadlines";
109    type Value = crate::types::Or;
110
111    fn variant() -> Vec<(&'static str, &'static str)> {
112        crate::variant_params![]
113    }
114
115    fn dims(&self) -> Vec<usize> {
116        super::lehmer_dims(self.num_tasks())
117    }
118
119    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
120        crate::types::Or({
121            let Some(schedule) = super::decode_lehmer(config, self.num_tasks()) else {
122                return crate::types::Or(false);
123            };
124
125            // Schedule tasks left-to-right: each task starts at max(release_time, current_time).
126            let mut current_time: u64 = 0;
127            for &task in &schedule {
128                let start = current_time.max(self.release_times[task]);
129                let finish = start + self.lengths[task];
130                if finish > self.deadlines[task] {
131                    return crate::types::Or(false);
132                }
133                current_time = finish;
134            }
135
136            true
137        })
138    }
139}
140
141crate::declare_variants! {
142    default SequencingWithReleaseTimesAndDeadlines => "2^num_tasks * num_tasks",
143}
144
145#[cfg(feature = "example-db")]
146pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
147    vec![crate::example_db::specs::ModelExampleSpec {
148        id: "sequencing_with_release_times_and_deadlines",
149        // 5 tasks from issue example.
150        // Feasible schedule order: t3, t0, t1, t2, t4
151        // Lehmer code [3,0,0,0,0] = permutation [3,0,1,2,4]
152        instance: Box::new(SequencingWithReleaseTimesAndDeadlines::new(
153            vec![3, 2, 4, 1, 2],
154            vec![0, 1, 5, 0, 8],
155            vec![5, 6, 10, 3, 12],
156        )),
157        optimal_config: vec![3, 0, 0, 0, 0],
158        optimal_value: serde_json::json!(true),
159    }]
160}
161
162#[cfg(test)]
163#[path = "../../unit_tests/models/misc/sequencing_with_release_times_and_deadlines.rs"]
164mod tests;
problemreductions/models/misc/sequencing_with_release_times_and_deadlines.rs

problemreductions/models/misc/
sequencing_with_release_times_and_deadlines.rs
