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)]
50#[serde(try_from = "PrecedenceConstrainedSchedulingData")]
51pub struct PrecedenceConstrainedScheduling {
52    num_tasks: usize,
53    num_processors: usize,
54    deadline: i64,
55    precedences: Vec<(usize, usize)>,
56}
57
58#[derive(Deserialize)]
59struct PrecedenceConstrainedSchedulingData {
60    num_tasks: usize,
61    num_processors: usize,
62    deadline: i64,
63    precedences: Vec<(usize, usize)>,
64}
65
66impl TryFrom<PrecedenceConstrainedSchedulingData> for PrecedenceConstrainedScheduling {
67    type Error = crate::registry::ConstructionError;
68    fn try_from(data: PrecedenceConstrainedSchedulingData) -> Result<Self, Self::Error> {
69        Self::try_new(
70            data.num_tasks,
71            data.num_processors,
72            data.deadline,
73            data.precedences,
74        )
75    }
76}
77
78#[derive(Debug, Deserialize, crate::CreateSpec)]
79struct PrecedenceConstrainedSchedulingCreateSpec {
80    num_tasks: usize,
81    num_processors: usize,
82    deadline: i64,
83    precedences: Option<Vec<(usize, usize)>>,
84}
85
86impl TryFrom<PrecedenceConstrainedSchedulingCreateSpec> for PrecedenceConstrainedScheduling {
87    type Error = crate::registry::ConstructionError;
88
89    fn try_from(spec: PrecedenceConstrainedSchedulingCreateSpec) -> Result<Self, Self::Error> {
90        Self::try_new(
91            spec.num_tasks,
92            spec.num_processors,
93            spec.deadline,
94            spec.precedences.unwrap_or_default(),
95        )
96    }
97}
98
99impl PrecedenceConstrainedScheduling {
100    /// Create a new Precedence Constrained Scheduling instance.
101    ///
102    /// # Panics
103    ///
104    /// Panics if `num_processors` or `deadline` is zero (when `num_tasks > 0`),
105    /// or if any precedence index is out of bounds (>= num_tasks).
106    pub fn new(
107        num_tasks: usize,
108        num_processors: usize,
109        deadline: i64,
110        precedences: Vec<(usize, usize)>,
111    ) -> Self {
112        Self::try_new(num_tasks, num_processors, deadline, precedences)
113            .unwrap_or_else(|error| panic!("{error}"))
114    }
115
116    fn try_new(
117        num_tasks: usize,
118        num_processors: usize,
119        deadline: i64,
120        precedences: Vec<(usize, usize)>,
121    ) -> Result<Self, crate::registry::ConstructionError> {
122        if num_tasks > 0 {
123            if num_processors == 0 {
124                return Err("num_processors must be > 0 when there are tasks".into());
125            }
126            if deadline <= 0 {
127                return Err("deadline must be > 0 when there are tasks".into());
128            }
129        }
130        if deadline < 0 || usize::try_from(deadline).is_err() {
131            return Err("deadline must be nonnegative and fit usize".into());
132        }
133        for &(i, j) in &precedences {
134            if i >= num_tasks || j >= num_tasks {
135                return Err(format!(
136                    "Precedence ({}, {}) out of bounds for {} tasks",
137                    i, j, num_tasks
138                )
139                .into());
140            }
141        }
142        Ok(Self {
143            num_tasks,
144            num_processors,
145            deadline,
146            precedences,
147        })
148    }
149
150    /// Get the number of tasks.
151    pub fn num_tasks(&self) -> usize {
152        self.num_tasks
153    }
154
155    /// Get the number of processors.
156    pub fn num_processors(&self) -> usize {
157        self.num_processors
158    }
159
160    /// Get the deadline.
161    pub fn deadline(&self) -> i64 {
162        self.deadline
163    }
164
165    /// Get the precedence constraints.
166    pub fn precedences(&self) -> &[(usize, usize)] {
167        &self.precedences
168    }
169
170    /// Return the number of precedence relations.
171    pub fn num_precedences(&self) -> usize {
172        self.precedences.len()
173    }
174}
175
176impl Problem for PrecedenceConstrainedScheduling {
177    const NAME: &'static str = "PrecedenceConstrainedScheduling";
178    type Solution = Vec<usize>;
179    type Value = crate::types::Or;
180
181    crate::problem_parameters![
182        ("deadline", deadline),
183        ("num_precedences", num_precedences),
184        ("num_tasks", num_tasks),
185    ];
186
187    fn variant() -> Vec<(&'static str, &'static str)> {
188        crate::variant_params![]
189    }
190
191    fn evaluate(
192        &self,
193        config: &Self::Solution,
194    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
195        Ok({
196            crate::types::Or({
197                if config.len() != self.num_tasks {
198                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
199                        "schedule length does not match the tasks".into(),
200                    ));
201                }
202                let deadline =
203                    usize::try_from(self.deadline).expect("validated deadline must fit usize");
204                if config.iter().any(|&v| v >= deadline) {
205                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
206                        "schedule contains an out-of-range time slot".into(),
207                    ));
208                }
209                // Check processor capacity: at most num_processors tasks per time slot
210                let mut slot_count = std::collections::BTreeMap::new();
211                for &slot in config {
212                    let count = slot_count.entry(slot).or_insert(0usize);
213                    *count += 1;
214                    if *count > self.num_processors {
215                        return Ok(crate::types::Or(false));
216                    }
217                }
218                // Check precedence constraints: for (i, j), slot[j] >= slot[i] + 1
219                for &(i, j) in &self.precedences {
220                    if config[j] < config[i] + 1 {
221                        return Ok(crate::types::Or(false));
222                    }
223                }
224                true
225            })
226        })
227    }
228}
229
230impl crate::solvers::BruteForceProblem for PrecedenceConstrainedScheduling {
231    fn dimensions(&self) -> Vec<usize> {
232        vec![
233            usize::try_from(self.deadline).expect("validated deadline must fit usize");
234            self.num_tasks
235        ]
236    }
237}
238
239crate::declare_variants! {
240    default PrecedenceConstrainedScheduling => "2^num_tasks" create PrecedenceConstrainedSchedulingCreateSpec,
241}
242
243crate::register_brute_force! {
244    PrecedenceConstrainedScheduling,
245}
246
247#[cfg(feature = "example-db")]
248pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
249    vec![crate::example_db::specs::ModelExampleSpec {
250        id: "precedence_constrained_scheduling",
251        // Issue #501 example: 8 tasks, 3 processors, deadline 4
252        instance: Box::new(PrecedenceConstrainedScheduling::new(
253            8,
254            3,
255            4,
256            vec![
257                (0, 2),
258                (0, 3),
259                (1, 3),
260                (1, 4),
261                (2, 5),
262                (3, 6),
263                (4, 6),
264                (5, 7),
265                (6, 7),
266            ],
267        )),
268        // Valid schedule: slot 0: {t0,t1}, slot 1: {t2,t3,t4}, slot 2: {t5,t6}, slot 3: {t7}
269        optimal_config: serde_json::json!(vec![0, 0, 1, 1, 1, 2, 2, 3]),
270        optimal_value: serde_json::json!(true),
271    }]
272}
273
274#[cfg(test)]
275#[path = "../../unit_tests/models/misc/precedence_constrained_scheduling.rs"]
276mod tests;
problemreductions/models/misc/precedence_constrained_scheduling.rs

problemreductions/models/misc/
precedence_constrained_scheduling.rs
