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)]
60pub struct SequencingWithReleaseTimesAndDeadlines {
61    lengths: Vec<i64>,
62    release_times: Vec<i64>,
63    deadlines: Vec<i64>,
64}
65
66impl SequencingWithReleaseTimesAndDeadlines {
67    /// Create a new instance.
68    ///
69    /// # Panics
70    ///
71    /// Panics if the three vectors have different lengths.
72    pub fn new(lengths: Vec<i64>, release_times: Vec<i64>, deadlines: Vec<i64>) -> Self {
73        assert_eq!(lengths.len(), release_times.len());
74        assert_eq!(lengths.len(), deadlines.len());
75        assert!(
76            lengths.iter().all(|&length| length >= 0),
77            "task lengths must be nonnegative"
78        );
79        assert!(
80            release_times.iter().all(|&release| release >= 0),
81            "release times must be nonnegative"
82        );
83        assert!(
84            deadlines.iter().all(|&deadline| deadline >= 0),
85            "deadlines must be nonnegative"
86        );
87        Self {
88            lengths,
89            release_times,
90            deadlines,
91        }
92    }
93
94    /// Returns the processing times.
95    pub fn lengths(&self) -> &[i64] {
96        &self.lengths
97    }
98
99    /// Returns the release times.
100    pub fn release_times(&self) -> &[i64] {
101        &self.release_times
102    }
103
104    /// Returns the deadlines.
105    pub fn deadlines(&self) -> &[i64] {
106        &self.deadlines
107    }
108
109    /// Returns the number of tasks.
110    pub fn num_tasks(&self) -> usize {
111        self.lengths.len()
112    }
113
114    /// Returns the time horizon (maximum deadline).
115    pub fn time_horizon(&self) -> i64 {
116        self.deadlines.iter().copied().max().unwrap_or(0)
117    }
118}
119
120impl Problem for SequencingWithReleaseTimesAndDeadlines {
121    const NAME: &'static str = "SequencingWithReleaseTimesAndDeadlines";
122    type Solution = Vec<usize>;
123    type Value = crate::types::Or;
124
125    crate::problem_parameters![("num_tasks", num_tasks), ("time_horizon", time_horizon),];
126
127    fn variant() -> Vec<(&'static str, &'static str)> {
128        crate::variant_params![]
129    }
130
131    fn evaluate(
132        &self,
133        config: &Self::Solution,
134    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
135        let n = self.num_tasks();
136        if config.len() != n {
137            return Err(crate::traits::EvaluationError::InvalidConfiguration(
138                "schedule length does not match the tasks".into(),
139            ));
140        }
141        if config.iter().any(|&task| task >= n) {
142            return Err(crate::traits::EvaluationError::InvalidConfiguration(
143                "schedule contains an out-of-range task".into(),
144            ));
145        }
146        Ok({
147            crate::types::Or({
148                let Some(schedule) = super::decode_permutation(config, self.num_tasks()) else {
149                    return Ok(crate::types::Or(false));
150                };
151
152                // Schedule tasks left-to-right: each task starts at max(release_time, current_time).
153                let mut current_time: i64 = 0;
154                for &task in &schedule {
155                    let start = current_time.max(self.release_times[task]);
156                    let finish = start + self.lengths[task];
157                    if finish > self.deadlines[task] {
158                        return Ok(crate::types::Or(false));
159                    }
160                    current_time = finish;
161                }
162
163                true
164            })
165        })
166    }
167}
168
169impl crate::solvers::BruteForceProblem for SequencingWithReleaseTimesAndDeadlines {
170    fn dimensions(&self) -> Vec<usize> {
171        super::lehmer_dims(self.num_tasks())
172    }
173}
174
175crate::declare_variants! {
176    default SequencingWithReleaseTimesAndDeadlines => "2^num_tasks * num_tasks",
177}
178
179crate::register_brute_force! {
180    SequencingWithReleaseTimesAndDeadlines decode |problem: &SequencingWithReleaseTimesAndDeadlines, indices: Vec<usize>| super::decode_lehmer(&indices, problem.num_tasks()).expect("enumerated Lehmer digits are valid"),
181}
182
183#[cfg(feature = "example-db")]
184pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
185    vec![crate::example_db::specs::ModelExampleSpec {
186        id: "sequencing_with_release_times_and_deadlines",
187        // 5 tasks from issue example.
188        // Feasible schedule order: t3, t0, t1, t2, t4
189        // Lehmer code [3,0,0,0,0] = permutation [3,0,1,2,4]
190        instance: Box::new(SequencingWithReleaseTimesAndDeadlines::new(
191            vec![3, 2, 4, 1, 2],
192            vec![0, 1, 5, 0, 8],
193            vec![5, 6, 10, 3, 12],
194        )),
195        optimal_config: serde_json::json!(vec![3, 0, 1, 2, 4]),
196        optimal_value: serde_json::json!(true),
197    }]
198}
199
200#[cfg(test)]
201#[path = "../../unit_tests/models/misc/sequencing_with_release_times_and_deadlines.rs"]
202mod tests;
problemreductions/models/misc/sequencing_with_release_times_and_deadlines.rs

problemreductions/models/misc/
sequencing_with_release_times_and_deadlines.rs
