problemreductions/models/misc/
precedence_constrained_scheduling.rs

1//! Precedence Constrained Scheduling problem implementation.
2//!
3//! Given unit-length tasks with precedence constraints, m processors, and a
4//! deadline D, determine whether all tasks can be scheduled to meet D while
5//! respecting precedences. NP-complete via reduction from 3SAT (Ullman, 1975).
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "PrecedenceConstrainedScheduling",
14        display_name: "Precedence Constrained Scheduling",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Misc,
18        module_path: module_path!(),
19        description: "Schedule unit-length tasks on m processors by deadline D respecting precedence constraints",
20        fields: PrecedenceConstrainedSchedulingCreateSpec::FIELDS,
21    }
22}
23
24/// The Precedence Constrained Scheduling problem.
25///
26/// Given `n` unit-length tasks with precedence constraints (a partial order),
27/// `m` processors, and a deadline `D`, determine whether there exists a schedule
28/// assigning each task to a time slot in `{0, ..., D-1}` such that:
29/// - At most `m` tasks are assigned to any single time slot
30/// - For each precedence `(i, j)`: task `j` starts after task `i` completes,
31///   i.e., `slot(j) >= slot(i) + 1`
32///
33/// # Representation
34///
35/// Each task has a variable in `{0, ..., D-1}` representing its assigned time slot.
36///
37/// # Example
38///
39/// ```
40/// use problemreductions::models::misc::PrecedenceConstrainedScheduling;
41/// use problemreductions::{Problem, BruteForce};
42///
43/// // 4 tasks, 2 processors, deadline 3, with t0 < t2 and t1 < t3
44/// let problem = PrecedenceConstrainedScheduling::new(4, 2, 3, vec![(0, 2), (1, 3)]);
45/// let solver = BruteForce::new();
46/// let solution = solver.solve(&problem).unwrap();
47/// assert!(solution.is_some());
48/// ```
49#[derive(Debug, Clone, Serialize, Deserialize)]
50pub struct PrecedenceConstrainedScheduling {
51    num_tasks: usize,
52    num_processors: usize,
53    deadline: i64,
54    precedences: Vec<(usize, usize)>,
55}
56
57#[derive(Debug, Deserialize, crate::CreateSpec)]
58struct PrecedenceConstrainedSchedulingCreateSpec {
59    num_tasks: usize,
60    num_processors: usize,
61    deadline: i64,
62    precedences: Option<Vec<(usize, usize)>>,
63}
64
65impl TryFrom<PrecedenceConstrainedSchedulingCreateSpec> for PrecedenceConstrainedScheduling {
66    type Error = crate::registry::ConstructionError;
67
68    fn try_from(spec: PrecedenceConstrainedSchedulingCreateSpec) -> Result<Self, Self::Error> {
69        if spec.num_tasks > 0 && spec.num_processors == 0 {
70            return Err("num_processors must be positive when there are tasks"
71                .to_string()
72                .into());
73        }
74        if spec.num_tasks > 0 && spec.deadline == 0 {
75            return Err("deadline must be positive when there are tasks"
76                .to_string()
77                .into());
78        }
79        if spec.deadline < 0 || usize::try_from(spec.deadline).is_err() {
80            return Err("deadline must be nonnegative and fit usize"
81                .to_string()
82                .into());
83        }
84        let precedences = spec.precedences.unwrap_or_default();
85        if let Some(&(pred, succ)) = precedences
86            .iter()
87            .find(|&&(pred, succ)| pred >= spec.num_tasks || succ >= spec.num_tasks)
88        {
89            return Err(format!(
90                "precedence ({pred}, {succ}) is out of range for {} tasks",
91                spec.num_tasks
92            )
93            .into());
94        }
95        Ok(Self::new(
96            spec.num_tasks,
97            spec.num_processors,
98            spec.deadline,
99            precedences,
100        ))
101    }
102}
103
104impl PrecedenceConstrainedScheduling {
105    /// Create a new Precedence Constrained Scheduling instance.
106    ///
107    /// # Panics
108    ///
109    /// Panics if `num_processors` or `deadline` is zero (when `num_tasks > 0`),
110    /// or if any precedence index is out of bounds (>= num_tasks).
111    pub fn new(
112        num_tasks: usize,
113        num_processors: usize,
114        deadline: i64,
115        precedences: Vec<(usize, usize)>,
116    ) -> Self {
117        if num_tasks > 0 {
118            assert!(
119                num_processors > 0,
120                "num_processors must be > 0 when there are tasks"
121            );
122            assert!(deadline > 0, "deadline must be > 0 when there are tasks");
123        }
124        assert!(
125            deadline >= 0 && usize::try_from(deadline).is_ok(),
126            "deadline must be nonnegative and fit usize"
127        );
128        for &(i, j) in &precedences {
129            assert!(
130                i < num_tasks && j < num_tasks,
131                "Precedence ({}, {}) out of bounds for {} tasks",
132                i,
133                j,
134                num_tasks
135            );
136        }
137        Self {
138            num_tasks,
139            num_processors,
140            deadline,
141            precedences,
142        }
143    }
144
145    /// Get the number of tasks.
146    pub fn num_tasks(&self) -> usize {
147        self.num_tasks
148    }
149
150    /// Get the number of processors.
151    pub fn num_processors(&self) -> usize {
152        self.num_processors
153    }
154
155    /// Get the deadline.
156    pub fn deadline(&self) -> i64 {
157        self.deadline
158    }
159
160    /// Get the precedence constraints.
161    pub fn precedences(&self) -> &[(usize, usize)] {
162        &self.precedences
163    }
164
165    /// Return the number of precedence relations.
166    pub fn num_precedences(&self) -> usize {
167        self.precedences.len()
168    }
169}
170
171impl Problem for PrecedenceConstrainedScheduling {
172    const NAME: &'static str = "PrecedenceConstrainedScheduling";
173    type Solution = Vec<usize>;
174    type Value = crate::types::Or;
175
176    crate::problem_parameters![
177        ("deadline", deadline),
178        ("num_precedences", num_precedences),
179        ("num_tasks", num_tasks),
180    ];
181
182    fn variant() -> Vec<(&'static str, &'static str)> {
183        crate::variant_params![]
184    }
185
186    fn evaluate(
187        &self,
188        config: &Self::Solution,
189    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
190        Ok({
191            crate::types::Or({
192                if config.len() != self.num_tasks {
193                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
194                        "schedule length does not match the tasks".into(),
195                    ));
196                }
197                let deadline =
198                    usize::try_from(self.deadline).expect("validated deadline must fit usize");
199                if config.iter().any(|&v| v >= deadline) {
200                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
201                        "schedule contains an out-of-range time slot".into(),
202                    ));
203                }
204                // Check processor capacity: at most num_processors tasks per time slot
205                let mut slot_count = vec![0usize; deadline];
206                for &slot in config {
207                    slot_count[slot] += 1;
208                    if slot_count[slot] > self.num_processors {
209                        return Ok(crate::types::Or(false));
210                    }
211                }
212                // Check precedence constraints: for (i, j), slot[j] >= slot[i] + 1
213                for &(i, j) in &self.precedences {
214                    if config[j] < config[i] + 1 {
215                        return Ok(crate::types::Or(false));
216                    }
217                }
218                true
219            })
220        })
221    }
222}
223
224impl crate::solvers::BruteForceProblem for PrecedenceConstrainedScheduling {
225    fn dimensions(&self) -> Vec<usize> {
226        vec![
227            usize::try_from(self.deadline).expect("validated deadline must fit usize");
228            self.num_tasks
229        ]
230    }
231}
232
233crate::declare_variants! {
234    default PrecedenceConstrainedScheduling => "2^num_tasks" create PrecedenceConstrainedSchedulingCreateSpec,
235}
236
237crate::register_brute_force! {
238    PrecedenceConstrainedScheduling,
239}
240
241#[cfg(feature = "example-db")]
242pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
243    vec![crate::example_db::specs::ModelExampleSpec {
244        id: "precedence_constrained_scheduling",
245        // Issue #501 example: 8 tasks, 3 processors, deadline 4
246        instance: Box::new(PrecedenceConstrainedScheduling::new(
247            8,
248            3,
249            4,
250            vec![
251                (0, 2),
252                (0, 3),
253                (1, 3),
254                (1, 4),
255                (2, 5),
256                (3, 6),
257                (4, 6),
258                (5, 7),
259                (6, 7),
260            ],
261        )),
262        // Valid schedule: slot 0: {t0,t1}, slot 1: {t2,t3,t4}, slot 2: {t5,t6}, slot 3: {t7}
263        optimal_config: serde_json::json!(vec![0, 0, 1, 1, 1, 2, 2, 3]),
264        optimal_value: serde_json::json!(true),
265    }]
266}
267
268#[cfg(test)]
269#[path = "../../unit_tests/models/misc/precedence_constrained_scheduling.rs"]
270mod tests;
problemreductions/models/misc/precedence_constrained_scheduling.rs

problemreductions/models/misc/
precedence_constrained_scheduling.rs
