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::{FieldInfo, 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        module_path: module_path!(),
19        description: "Determine whether unit-length tasks can be scheduled on m processors while meeting individual deadlines",
20        fields: &[
21            FieldInfo { name: "num_tasks", type_name: "usize", description: "Number of tasks |T|" },
22            FieldInfo { name: "num_processors", type_name: "usize", description: "Number of identical processors m" },
23            FieldInfo { name: "deadlines", type_name: "Vec<usize>", description: "Deadline d(t) for each task" },
24            FieldInfo { name: "precedences", type_name: "Vec<(usize, usize)>", description: "Precedence pairs (predecessor, successor)" },
25        ],
26    }
27}
28
29/// Scheduling With Individual Deadlines.
30///
31/// A configuration assigns each task `t` a start slot `sigma(t)` with domain
32/// `0..d(t)`. The schedule is feasible if every precedence pair `(u, v)`
33/// satisfies `sigma(u) + 1 <= sigma(v)` and no time slot hosts more than
34/// `num_processors` tasks.
35#[derive(Debug, Clone, Serialize, Deserialize)]
36pub struct SchedulingWithIndividualDeadlines {
37    num_tasks: usize,
38    num_processors: usize,
39    deadlines: Vec<usize>,
40    precedences: Vec<(usize, usize)>,
41}
42
43impl SchedulingWithIndividualDeadlines {
44    pub fn new(
45        num_tasks: usize,
46        num_processors: usize,
47        deadlines: Vec<usize>,
48        precedences: Vec<(usize, usize)>,
49    ) -> Self {
50        assert_eq!(
51            deadlines.len(),
52            num_tasks,
53            "deadlines length must equal num_tasks"
54        );
55        for &(pred, succ) in &precedences {
56            assert!(
57                pred < num_tasks,
58                "predecessor index {} out of range (num_tasks = {})",
59                pred,
60                num_tasks
61            );
62            assert!(
63                succ < num_tasks,
64                "successor index {} out of range (num_tasks = {})",
65                succ,
66                num_tasks
67            );
68        }
69
70        Self {
71            num_tasks,
72            num_processors,
73            deadlines,
74            precedences,
75        }
76    }
77
78    pub fn num_tasks(&self) -> usize {
79        self.num_tasks
80    }
81
82    pub fn num_processors(&self) -> usize {
83        self.num_processors
84    }
85
86    pub fn deadlines(&self) -> &[usize] {
87        &self.deadlines
88    }
89
90    pub fn precedences(&self) -> &[(usize, usize)] {
91        &self.precedences
92    }
93
94    pub fn num_precedences(&self) -> usize {
95        self.precedences.len()
96    }
97
98    pub fn max_deadline(&self) -> usize {
99        self.deadlines.iter().copied().max().unwrap_or(0)
100    }
101}
102
103impl Problem for SchedulingWithIndividualDeadlines {
104    const NAME: &'static str = "SchedulingWithIndividualDeadlines";
105    type Value = crate::types::Or;
106
107    fn variant() -> Vec<(&'static str, &'static str)> {
108        crate::variant_params![]
109    }
110
111    fn dims(&self) -> Vec<usize> {
112        self.deadlines.clone()
113    }
114
115    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
116        crate::types::Or({
117            if config.len() != self.num_tasks {
118                return crate::types::Or(false);
119            }
120
121            for (&start, &deadline) in config.iter().zip(&self.deadlines) {
122                if start >= deadline {
123                    return crate::types::Or(false);
124                }
125            }
126
127            for &(pred, succ) in &self.precedences {
128                if config[pred] + 1 > config[succ] {
129                    return crate::types::Or(false);
130                }
131            }
132
133            let mut slot_loads = BTreeMap::new();
134            for &start in config {
135                let load = slot_loads.entry(start).or_insert(0usize);
136                *load += 1;
137                if *load > self.num_processors {
138                    return crate::types::Or(false);
139                }
140            }
141
142            true
143        })
144    }
145}
146
147crate::declare_variants! {
148    default SchedulingWithIndividualDeadlines => "max_deadline^num_tasks",
149}
150
151#[cfg(feature = "example-db")]
152pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
153    vec![crate::example_db::specs::ModelExampleSpec {
154        id: "scheduling_with_individual_deadlines",
155        instance: Box::new(SchedulingWithIndividualDeadlines::new(
156            7,
157            3,
158            vec![2, 1, 2, 2, 3, 3, 2],
159            vec![(0, 3), (1, 3), (1, 4), (2, 4), (2, 5)],
160        )),
161        optimal_config: vec![0, 0, 0, 1, 2, 1, 1],
162        optimal_value: serde_json::json!(true),
163    }]
164}
165
166#[cfg(test)]
167#[path = "../../unit_tests/models/misc/scheduling_with_individual_deadlines.rs"]
168mod tests;
problemreductions/models/misc/scheduling_with_individual_deadlines.rs

problemreductions/models/misc/
scheduling_with_individual_deadlines.rs
