problemreductions/models/misc/
multiprocessor_scheduling.rs

1//! Multiprocessor Scheduling problem implementation.
2//!
3//! The Multiprocessor Scheduling problem asks whether a set of tasks
4//! can be assigned to identical processors such that no processor's
5//! total load exceeds a given deadline.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "MultiprocessorScheduling",
14        display_name: "Multiprocessor Scheduling",
15        aliases: &[],
16        dimensions: &[],
17        module_path: module_path!(),
18        description: "Assign tasks to processors so that no processor's load exceeds a deadline",
19        fields: &[
20            FieldInfo { name: "lengths", type_name: "Vec<u64>", description: "Processing time l(t) for each task" },
21            FieldInfo { name: "num_processors", type_name: "usize", description: "Number of identical processors m" },
22            FieldInfo { name: "deadline", type_name: "u64", description: "Global deadline D" },
23        ],
24    }
25}
26
27/// The Multiprocessor Scheduling problem.
28///
29/// Given a set T of tasks with processing times, a number m of identical
30/// processors, and a deadline D, determine whether there exists an assignment
31/// of tasks to processors such that the total load on each processor does
32/// not exceed D.
33///
34/// Because tasks are independent and processors are identical, any feasible
35/// schedule can be packed processor-by-processor without idle gaps. This makes
36/// the scheduling question equivalent to partitioning tasks among processors
37/// with per-processor load at most `D`.
38///
39/// # Representation
40///
41/// Each task has a variable in `{0, ..., m-1}` representing its processor assignment.
42///
43/// # Example
44///
45/// ```
46/// use problemreductions::models::misc::MultiprocessorScheduling;
47/// use problemreductions::{Problem, Solver, BruteForce};
48///
49/// // 5 tasks with lengths [4, 5, 3, 2, 6], 2 processors, deadline 10
50/// let problem = MultiprocessorScheduling::new(vec![4, 5, 3, 2, 6], 2, 10);
51/// let solver = BruteForce::new();
52/// let solution = solver.find_witness(&problem);
53/// assert!(solution.is_some());
54/// ```
55#[derive(Debug, Clone, Serialize, Deserialize)]
56pub struct MultiprocessorScheduling {
57    /// Processing time for each task.
58    lengths: Vec<u64>,
59    /// Number of identical processors.
60    #[serde(deserialize_with = "positive_usize::deserialize")]
61    num_processors: usize,
62    /// Global deadline.
63    deadline: u64,
64}
65
66impl MultiprocessorScheduling {
67    /// Create a new Multiprocessor Scheduling instance.
68    ///
69    /// # Panics
70    /// Panics if `num_processors` is zero.
71    pub fn new(lengths: Vec<u64>, num_processors: usize, deadline: u64) -> Self {
72        assert!(num_processors > 0, "num_processors must be positive");
73        Self {
74            lengths,
75            num_processors,
76            deadline,
77        }
78    }
79
80    /// Returns the processing times for each task.
81    pub fn lengths(&self) -> &[u64] {
82        &self.lengths
83    }
84
85    /// Returns the number of processors.
86    pub fn num_processors(&self) -> usize {
87        self.num_processors
88    }
89
90    /// Returns the deadline.
91    pub fn deadline(&self) -> u64 {
92        self.deadline
93    }
94
95    /// Returns the number of tasks.
96    pub fn num_tasks(&self) -> usize {
97        self.lengths.len()
98    }
99
100    /// Returns the total processing time of all tasks.
101    pub fn total_length(&self) -> u64 {
102        self.lengths.iter().sum()
103    }
104}
105
106impl Problem for MultiprocessorScheduling {
107    const NAME: &'static str = "MultiprocessorScheduling";
108    type Value = crate::types::Or;
109
110    fn variant() -> Vec<(&'static str, &'static str)> {
111        crate::variant_params![]
112    }
113
114    fn dims(&self) -> Vec<usize> {
115        vec![self.num_processors; self.num_tasks()]
116    }
117
118    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
119        crate::types::Or({
120            if config.len() != self.num_tasks() {
121                return crate::types::Or(false);
122            }
123            let m = self.num_processors;
124            if config.iter().any(|&p| p >= m) {
125                return crate::types::Or(false);
126            }
127            let mut loads = vec![0u64; m];
128            for (i, &processor) in config.iter().enumerate() {
129                loads[processor] += self.lengths[i];
130            }
131            loads.iter().all(|&load| load <= self.deadline)
132        })
133    }
134}
135
136crate::declare_variants! {
137    default MultiprocessorScheduling => "2^num_tasks",
138}
139
140#[cfg(feature = "example-db")]
141pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
142    vec![crate::example_db::specs::ModelExampleSpec {
143        id: "multiprocessor_scheduling",
144        instance: Box::new(MultiprocessorScheduling::new(vec![4, 5, 3, 2, 6], 2, 10)),
145        optimal_config: vec![0, 1, 1, 1, 0],
146        optimal_value: serde_json::json!(true),
147    }]
148}
149
150mod positive_usize {
151    use serde::de::Error;
152    use serde::{Deserialize, Deserializer};
153
154    pub fn deserialize<'de, D>(deserializer: D) -> Result<usize, D::Error>
155    where
156        D: Deserializer<'de>,
157    {
158        let value = usize::deserialize(deserializer)?;
159        if value == 0 {
160            return Err(D::Error::custom("expected positive integer, got 0"));
161        }
162        Ok(value)
163    }
164}
165
166#[cfg(test)]
167#[path = "../../unit_tests/models/misc/multiprocessor_scheduling.rs"]
168mod tests;
problemreductions/models/misc/multiprocessor_scheduling.rs

problemreductions/models/misc/
multiprocessor_scheduling.rs
