problemreductions/models/misc/
scheduling_with_individual_deadlines.rs

1//! Scheduling With Individual Deadlines problem implementation.
2//!
3//! Given unit-length tasks with precedence constraints and per-task deadlines,
4//! determine whether they can be scheduled on `m` identical processors so that
5//! every task finishes by its own deadline.
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10use std::collections::BTreeMap;
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "SchedulingWithIndividualDeadlines",
15        display_name: "Scheduling With Individual Deadlines",
16        aliases: &[],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Determine whether unit-length tasks can be scheduled on m processors while meeting individual deadlines",
21        fields: SchedulingWithIndividualDeadlinesCreateSpec::FIELDS,
22    }
23}
24
25/// Scheduling With Individual Deadlines.
26///
27/// A configuration assigns each task `t` a start slot `sigma(t)` with domain
28/// `0..d(t)`. The schedule is feasible if every precedence pair `(u, v)`
29/// satisfies `sigma(u) + 1 <= sigma(v)` and no time slot hosts more than
30/// `num_processors` tasks.
31#[derive(Debug, Clone, Serialize, Deserialize)]
32#[serde(try_from = "SchedulingWithIndividualDeadlinesData")]
33pub struct SchedulingWithIndividualDeadlines {
34    num_tasks: usize,
35    num_processors: usize,
36    deadlines: Vec<i64>,
37    precedences: Vec<(usize, usize)>,
38}
39
40#[derive(Deserialize)]
41struct SchedulingWithIndividualDeadlinesData {
42    num_tasks: usize,
43    num_processors: usize,
44    deadlines: Vec<i64>,
45    precedences: Vec<(usize, usize)>,
46}
47
48impl TryFrom<SchedulingWithIndividualDeadlinesData> for SchedulingWithIndividualDeadlines {
49    type Error = crate::registry::ConstructionError;
50    fn try_from(data: SchedulingWithIndividualDeadlinesData) -> Result<Self, Self::Error> {
51        Self::try_new(
52            data.num_tasks,
53            data.num_processors,
54            data.deadlines,
55            data.precedences,
56        )
57    }
58}
59
60#[derive(Debug, Deserialize, crate::CreateSpec)]
61struct SchedulingWithIndividualDeadlinesCreateSpec {
62    /// Number of tasks.
63    num_tasks: usize,
64    /// Number of identical processors.
65    num_processors: usize,
66    /// Deadline for each task.
67    deadlines: Vec<i64>,
68    /// Precedence pairs.
69    precedences: Option<Vec<(usize, usize)>>,
70}
71impl TryFrom<SchedulingWithIndividualDeadlinesCreateSpec> for SchedulingWithIndividualDeadlines {
72    type Error = crate::registry::ConstructionError;
73    fn try_from(spec: SchedulingWithIndividualDeadlinesCreateSpec) -> Result<Self, Self::Error> {
74        Self::try_new(
75            spec.num_tasks,
76            spec.num_processors,
77            spec.deadlines,
78            spec.precedences.unwrap_or_default(),
79        )
80    }
81}
82
83impl SchedulingWithIndividualDeadlines {
84    pub fn new(
85        num_tasks: usize,
86        num_processors: usize,
87        deadlines: Vec<i64>,
88        precedences: Vec<(usize, usize)>,
89    ) -> Self {
90        Self::try_new(num_tasks, num_processors, deadlines, precedences)
91            .unwrap_or_else(|error| panic!("{error}"))
92    }
93
94    fn try_new(
95        num_tasks: usize,
96        num_processors: usize,
97        deadlines: Vec<i64>,
98        precedences: Vec<(usize, usize)>,
99    ) -> Result<Self, crate::registry::ConstructionError> {
100        if deadlines.len() != num_tasks {
101            return Err("deadlines length must equal num_tasks".into());
102        }
103        if deadlines.iter().any(|&deadline| deadline < 0) {
104            return Err("deadlines must be nonnegative".into());
105        }
106        if deadlines
107            .iter()
108            .any(|&deadline| usize::try_from(deadline).is_err())
109        {
110            return Err("deadlines must fit usize to define schedule slots".into());
111        }
112        for &(pred, succ) in &precedences {
113            if pred >= num_tasks {
114                return Err(format!(
115                    "predecessor index {} out of range (num_tasks = {})",
116                    pred, num_tasks
117                )
118                .into());
119            }
120            if succ >= num_tasks {
121                return Err(format!(
122                    "successor index {} out of range (num_tasks = {})",
123                    succ, num_tasks
124                )
125                .into());
126            }
127        }
128
129        Ok(Self {
130            num_tasks,
131            num_processors,
132            deadlines,
133            precedences,
134        })
135    }
136
137    pub fn num_tasks(&self) -> usize {
138        self.num_tasks
139    }
140
141    pub fn num_processors(&self) -> usize {
142        self.num_processors
143    }
144
145    pub fn deadlines(&self) -> &[i64] {
146        &self.deadlines
147    }
148
149    pub fn precedences(&self) -> &[(usize, usize)] {
150        &self.precedences
151    }
152
153    pub fn num_precedences(&self) -> usize {
154        self.precedences.len()
155    }
156
157    pub fn max_deadline(&self) -> i64 {
158        self.deadlines.iter().copied().max().unwrap_or(0)
159    }
160}
161
162impl Problem for SchedulingWithIndividualDeadlines {
163    const NAME: &'static str = "SchedulingWithIndividualDeadlines";
164    type Solution = Vec<usize>;
165    type Value = crate::types::Or;
166
167    crate::problem_parameters![
168        ("max_deadline", max_deadline),
169        ("num_precedences", num_precedences),
170        ("num_tasks", num_tasks),
171    ];
172
173    fn variant() -> Vec<(&'static str, &'static str)> {
174        crate::variant_params![]
175    }
176
177    fn evaluate(
178        &self,
179        config: &Self::Solution,
180    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
181        Ok({
182            crate::types::Or({
183                if config.len() != self.num_tasks {
184                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
185                        "schedule length does not match the tasks".into(),
186                    ));
187                }
188
189                for (&start, &deadline) in config.iter().zip(&self.deadlines) {
190                    let deadline =
191                        usize::try_from(deadline).expect("validated deadline must fit usize");
192                    if start >= deadline {
193                        return Ok(crate::types::Or(false));
194                    }
195                }
196
197                for &(pred, succ) in &self.precedences {
198                    if config[pred] + 1 > config[succ] {
199                        return Ok(crate::types::Or(false));
200                    }
201                }
202
203                let mut slot_loads = BTreeMap::new();
204                for &start in config {
205                    let load = slot_loads.entry(start).or_insert(0usize);
206                    *load += 1;
207                    if *load > self.num_processors {
208                        return Ok(crate::types::Or(false));
209                    }
210                }
211
212                true
213            })
214        })
215    }
216}
217
218impl crate::solvers::BruteForceProblem for SchedulingWithIndividualDeadlines {
219    fn dimensions(&self) -> Vec<usize> {
220        self.deadlines
221            .iter()
222            .map(|&deadline| usize::try_from(deadline).expect("validated deadline must fit usize"))
223            .collect()
224    }
225}
226
227crate::declare_variants! {
228    default SchedulingWithIndividualDeadlines => "max_deadline^num_tasks" create SchedulingWithIndividualDeadlinesCreateSpec,
229}
230
231crate::register_brute_force! {
232    SchedulingWithIndividualDeadlines,
233}
234
235#[cfg(feature = "example-db")]
236pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
237    vec![crate::example_db::specs::ModelExampleSpec {
238        id: "scheduling_with_individual_deadlines",
239        instance: Box::new(SchedulingWithIndividualDeadlines::new(
240            7,
241            3,
242            vec![2, 1, 2, 2, 3, 3, 2],
243            vec![(0, 3), (1, 3), (1, 4), (2, 4), (2, 5)],
244        )),
245        optimal_config: serde_json::json!(vec![0, 0, 0, 1, 2, 1, 1]),
246        optimal_value: serde_json::json!(true),
247    }]
248}
249
250#[cfg(test)]
251#[path = "../../unit_tests/models/misc/scheduling_with_individual_deadlines.rs"]
252mod tests;
problemreductions/models/misc/scheduling_with_individual_deadlines.rs

problemreductions/models/misc/
scheduling_with_individual_deadlines.rs
