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        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Single-machine scheduling feasibility: can all tasks be scheduled within their release-deadline windows without overlap?",
21        fields: &[
22            FieldInfo { name: "lengths", type_name: "Vec<i64>", description: "Processing time l(t) for each task (positive)" },
23            FieldInfo { name: "release_times", type_name: "Vec<i64>", description: "Release time r(t) for each task (non-negative)" },
24            FieldInfo { name: "deadlines", type_name: "Vec<i64>", description: "Deadline d(t) for each task (positive)" },
25        ],
26    }
27}
28
29/// Sequencing with Release Times and Deadlines.
30///
31/// Given a set of `n` tasks, each with a processing time `l(t)`, release time
32/// `r(t)`, and deadline `d(t)`, determine whether there exists a one-processor
33/// schedule where each task starts no earlier than its release time and finishes
34/// by its deadline, with no two tasks overlapping.
35///
36/// # Representation
37///
38/// Uses a permutation encoding (Lehmer code), where `config[i]` selects which
39/// remaining task to schedule next from the pool of unscheduled tasks.
40/// `dims() = [n, n-1, ..., 2, 1]`. Tasks are scheduled left-to-right: each
41/// task starts at `max(release_time, current_time)`. The schedule is feasible
42/// iff every task finishes by its deadline.
43///
44/// # Example
45///
46/// ```
47/// use problemreductions::models::misc::SequencingWithReleaseTimesAndDeadlines;
48/// use problemreductions::{Problem, BruteForce};
49///
50/// let problem = SequencingWithReleaseTimesAndDeadlines::new(
51///     vec![1, 2, 1],
52///     vec![0, 0, 2],
53///     vec![3, 3, 4],
54/// );
55/// let solver = BruteForce::new();
56/// let solution = solver.solve(&problem).unwrap();
57/// assert!(solution.is_some());
58/// ```
59#[derive(Debug, Clone, Serialize, Deserialize)]
60#[serde(try_from = "SequencingWithReleaseTimesAndDeadlinesData")]
61pub struct SequencingWithReleaseTimesAndDeadlines {
62    lengths: Vec<i64>,
63    release_times: Vec<i64>,
64    deadlines: Vec<i64>,
65}
66
67#[derive(Deserialize)]
68struct SequencingWithReleaseTimesAndDeadlinesData {
69    lengths: Vec<i64>,
70    release_times: Vec<i64>,
71    deadlines: Vec<i64>,
72}
73
74impl TryFrom<SequencingWithReleaseTimesAndDeadlinesData>
75    for SequencingWithReleaseTimesAndDeadlines
76{
77    type Error = crate::registry::ConstructionError;
78    fn try_from(data: SequencingWithReleaseTimesAndDeadlinesData) -> Result<Self, Self::Error> {
79        Self::try_new(data.lengths, data.release_times, data.deadlines)
80    }
81}
82
83impl SequencingWithReleaseTimesAndDeadlines {
84    /// Create a new instance.
85    ///
86    /// # Panics
87    ///
88    /// Panics if the three vectors have different lengths.
89    pub fn new(lengths: Vec<i64>, release_times: Vec<i64>, deadlines: Vec<i64>) -> Self {
90        Self::try_new(lengths, release_times, deadlines).unwrap_or_else(|error| panic!("{error}"))
91    }
92
93    fn try_new(
94        lengths: Vec<i64>,
95        release_times: Vec<i64>,
96        deadlines: Vec<i64>,
97    ) -> Result<Self, crate::registry::ConstructionError> {
98        if lengths.len() != release_times.len() {
99            return Err("lengths and release_times must have the same length".into());
100        }
101        if lengths.len() != deadlines.len() {
102            return Err("lengths and deadlines must have the same length".into());
103        }
104        if lengths.iter().any(|&length| length < 0) {
105            return Err("task lengths must be nonnegative".into());
106        }
107        if release_times.iter().any(|&release| release < 0) {
108            return Err("release times must be nonnegative".into());
109        }
110        if deadlines.iter().any(|&deadline| deadline < 0) {
111            return Err("deadlines must be nonnegative".into());
112        }
113        Ok(Self {
114            lengths,
115            release_times,
116            deadlines,
117        })
118    }
119
120    /// Returns the processing times.
121    pub fn lengths(&self) -> &[i64] {
122        &self.lengths
123    }
124
125    /// Returns the release times.
126    pub fn release_times(&self) -> &[i64] {
127        &self.release_times
128    }
129
130    /// Returns the deadlines.
131    pub fn deadlines(&self) -> &[i64] {
132        &self.deadlines
133    }
134
135    /// Returns the number of tasks.
136    pub fn num_tasks(&self) -> usize {
137        self.lengths.len()
138    }
139
140    /// Returns the time horizon (maximum deadline).
141    pub fn time_horizon(&self) -> i64 {
142        self.deadlines.iter().copied().max().unwrap_or(0)
143    }
144
145    /// Magnitude bits of the maximum deadline, with at least one bit.
146    pub fn time_horizon_bits(&self) -> u64 {
147        crate::types::max_numeric_magnitude_bits([self.time_horizon()])
148    }
149}
150
151impl Problem for SequencingWithReleaseTimesAndDeadlines {
152    const NAME: &'static str = "SequencingWithReleaseTimesAndDeadlines";
153    type Solution = Vec<usize>;
154    type Value = crate::types::Or;
155
156    crate::problem_parameters![
157        ("num_tasks", num_tasks),
158        ("time_horizon", time_horizon),
159        ("time_horizon_bits", time_horizon_bits),
160    ];
161
162    fn variant() -> Vec<(&'static str, &'static str)> {
163        crate::variant_params![]
164    }
165
166    fn evaluate(
167        &self,
168        config: &Self::Solution,
169    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
170        let n = self.num_tasks();
171        if config.len() != n {
172            return Err(crate::traits::EvaluationError::InvalidConfiguration(
173                "schedule length does not match the tasks".into(),
174            ));
175        }
176        if config.iter().any(|&task| task >= n) {
177            return Err(crate::traits::EvaluationError::InvalidConfiguration(
178                "schedule contains an out-of-range task".into(),
179            ));
180        }
181        Ok({
182            crate::types::Or({
183                let Some(schedule) = super::decode_permutation(config, self.num_tasks()) else {
184                    return Ok(crate::types::Or(false));
185                };
186
187                // Schedule tasks left-to-right: each task starts at max(release_time, current_time).
188                let mut current_time: i64 = 0;
189                for &task in &schedule {
190                    let start = current_time.max(self.release_times[task]);
191                    let finish = start + self.lengths[task];
192                    if finish > self.deadlines[task] {
193                        return Ok(crate::types::Or(false));
194                    }
195                    current_time = finish;
196                }
197
198                true
199            })
200        })
201    }
202}
203
204impl crate::solvers::BruteForceProblem for SequencingWithReleaseTimesAndDeadlines {
205    fn dimensions(&self) -> Vec<usize> {
206        super::lehmer_dims(self.num_tasks())
207    }
208}
209
210crate::declare_variants! {
211    default SequencingWithReleaseTimesAndDeadlines => "2^num_tasks * num_tasks",
212}
213
214crate::register_brute_force! {
215    SequencingWithReleaseTimesAndDeadlines decode |problem: &SequencingWithReleaseTimesAndDeadlines, indices: Vec<usize>| super::decode_lehmer(&indices, problem.num_tasks()).expect("enumerated Lehmer digits are valid"),
216}
217
218#[cfg(feature = "example-db")]
219pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
220    vec![crate::example_db::specs::ModelExampleSpec {
221        id: "sequencing_with_release_times_and_deadlines",
222        // 5 tasks from issue example.
223        // Feasible schedule order: t3, t0, t1, t2, t4
224        // Lehmer code [3,0,0,0,0] = permutation [3,0,1,2,4]
225        instance: Box::new(SequencingWithReleaseTimesAndDeadlines::new(
226            vec![3, 2, 4, 1, 2],
227            vec![0, 1, 5, 0, 8],
228            vec![5, 6, 10, 3, 12],
229        )),
230        optimal_config: serde_json::json!(vec![3, 0, 1, 2, 4]),
231        optimal_value: serde_json::json!(true),
232    }]
233}
234
235#[cfg(test)]
236#[path = "../../unit_tests/models/misc/sequencing_with_release_times_and_deadlines.rs"]
237mod tests;
problemreductions/models/misc/sequencing_with_release_times_and_deadlines.rs

problemreductions/models/misc/
sequencing_with_release_times_and_deadlines.rs
