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)]
32pub struct SchedulingWithIndividualDeadlines {
33    num_tasks: usize,
34    num_processors: usize,
35    deadlines: Vec<i64>,
36    precedences: Vec<(usize, usize)>,
37}
38
39#[derive(Debug, Deserialize, crate::CreateSpec)]
40struct SchedulingWithIndividualDeadlinesCreateSpec {
41    /// Number of tasks.
42    num_tasks: usize,
43    /// Number of identical processors.
44    num_processors: usize,
45    /// Deadline for each task.
46    deadlines: Vec<i64>,
47    /// Precedence pairs.
48    precedences: Option<Vec<(usize, usize)>>,
49}
50impl TryFrom<SchedulingWithIndividualDeadlinesCreateSpec> for SchedulingWithIndividualDeadlines {
51    type Error = crate::registry::ConstructionError;
52    fn try_from(spec: SchedulingWithIndividualDeadlinesCreateSpec) -> Result<Self, Self::Error> {
53        if spec.deadlines.len() != spec.num_tasks {
54            return Err(format!(
55                "deadlines has {} entries, expected {}",
56                spec.deadlines.len(),
57                spec.num_tasks
58            )
59            .into());
60        }
61        if spec.deadlines.iter().any(|&deadline| deadline < 0) {
62            return Err("deadlines must be nonnegative".to_string().into());
63        }
64        if spec
65            .deadlines
66            .iter()
67            .any(|&deadline| usize::try_from(deadline).is_err())
68        {
69            return Err("deadlines must fit usize to define schedule slots"
70                .to_string()
71                .into());
72        }
73        let precedences = spec.precedences.unwrap_or_default();
74        if let Some(&(pred, succ)) = precedences
75            .iter()
76            .find(|&&(p, s)| p >= spec.num_tasks || s >= spec.num_tasks)
77        {
78            return Err(format!(
79                "precedence ({pred}, {succ}) is out of range for {} tasks",
80                spec.num_tasks
81            )
82            .into());
83        }
84        Ok(Self::new(
85            spec.num_tasks,
86            spec.num_processors,
87            spec.deadlines,
88            precedences,
89        ))
90    }
91}
92
93impl SchedulingWithIndividualDeadlines {
94    pub fn new(
95        num_tasks: usize,
96        num_processors: usize,
97        deadlines: Vec<i64>,
98        precedences: Vec<(usize, usize)>,
99    ) -> Self {
100        assert_eq!(
101            deadlines.len(),
102            num_tasks,
103            "deadlines length must equal num_tasks"
104        );
105        assert!(
106            deadlines.iter().all(|&deadline| deadline >= 0),
107            "deadlines must be nonnegative"
108        );
109        assert!(
110            deadlines
111                .iter()
112                .all(|&deadline| usize::try_from(deadline).is_ok()),
113            "deadlines must fit usize to define schedule slots"
114        );
115        for &(pred, succ) in &precedences {
116            assert!(
117                pred < num_tasks,
118                "predecessor index {} out of range (num_tasks = {})",
119                pred,
120                num_tasks
121            );
122            assert!(
123                succ < num_tasks,
124                "successor index {} out of range (num_tasks = {})",
125                succ,
126                num_tasks
127            );
128        }
129
130        Self {
131            num_tasks,
132            num_processors,
133            deadlines,
134            precedences,
135        }
136    }
137
138    pub fn num_tasks(&self) -> usize {
139        self.num_tasks
140    }
141
142    pub fn num_processors(&self) -> usize {
143        self.num_processors
144    }
145
146    pub fn deadlines(&self) -> &[i64] {
147        &self.deadlines
148    }
149
150    pub fn precedences(&self) -> &[(usize, usize)] {
151        &self.precedences
152    }
153
154    pub fn num_precedences(&self) -> usize {
155        self.precedences.len()
156    }
157
158    pub fn max_deadline(&self) -> i64 {
159        self.deadlines.iter().copied().max().unwrap_or(0)
160    }
161}
162
163impl Problem for SchedulingWithIndividualDeadlines {
164    const NAME: &'static str = "SchedulingWithIndividualDeadlines";
165    type Solution = Vec<usize>;
166    type Value = crate::types::Or;
167
168    crate::problem_parameters![
169        ("max_deadline", max_deadline),
170        ("num_precedences", num_precedences),
171        ("num_tasks", num_tasks),
172    ];
173
174    fn variant() -> Vec<(&'static str, &'static str)> {
175        crate::variant_params![]
176    }
177
178    fn evaluate(
179        &self,
180        config: &Self::Solution,
181    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
182        Ok({
183            crate::types::Or({
184                if config.len() != self.num_tasks {
185                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
186                        "schedule length does not match the tasks".into(),
187                    ));
188                }
189
190                for (&start, &deadline) in config.iter().zip(&self.deadlines) {
191                    let deadline =
192                        usize::try_from(deadline).expect("validated deadline must fit usize");
193                    if start >= deadline {
194                        return Ok(crate::types::Or(false));
195                    }
196                }
197
198                for &(pred, succ) in &self.precedences {
199                    if config[pred] + 1 > config[succ] {
200                        return Ok(crate::types::Or(false));
201                    }
202                }
203
204                let mut slot_loads = BTreeMap::new();
205                for &start in config {
206                    let load = slot_loads.entry(start).or_insert(0usize);
207                    *load += 1;
208                    if *load > self.num_processors {
209                        return Ok(crate::types::Or(false));
210                    }
211                }
212
213                true
214            })
215        })
216    }
217}
218
219impl crate::solvers::BruteForceProblem for SchedulingWithIndividualDeadlines {
220    fn dimensions(&self) -> Vec<usize> {
221        self.deadlines
222            .iter()
223            .map(|&deadline| usize::try_from(deadline).expect("validated deadline must fit usize"))
224            .collect()
225    }
226}
227
228crate::declare_variants! {
229    default SchedulingWithIndividualDeadlines => "max_deadline^num_tasks" create SchedulingWithIndividualDeadlinesCreateSpec,
230}
231
232crate::register_brute_force! {
233    SchedulingWithIndividualDeadlines,
234}
235
236#[cfg(feature = "example-db")]
237pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
238    vec![crate::example_db::specs::ModelExampleSpec {
239        id: "scheduling_with_individual_deadlines",
240        instance: Box::new(SchedulingWithIndividualDeadlines::new(
241            7,
242            3,
243            vec![2, 1, 2, 2, 3, 3, 2],
244            vec![(0, 3), (1, 3), (1, 4), (2, 4), (2, 5)],
245        )),
246        optimal_config: serde_json::json!(vec![0, 0, 0, 1, 2, 1, 1]),
247        optimal_value: serde_json::json!(true),
248    }]
249}
250
251#[cfg(test)]
252#[path = "../../unit_tests/models/misc/scheduling_with_individual_deadlines.rs"]
253mod tests;
problemreductions/models/misc/scheduling_with_individual_deadlines.rs

problemreductions/models/misc/
scheduling_with_individual_deadlines.rs
