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::{CreateSpec, 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        category: crate::registry::ProblemCategory::Misc,
18        module_path: module_path!(),
19        description: "Assign tasks to processors so that no processor's load exceeds a deadline",
20        fields: MultiprocessorSchedulingCreateSpec::FIELDS,
21    }
22}
23
24/// The Multiprocessor Scheduling problem.
25///
26/// Given a set T of tasks with processing times, a number m of identical
27/// processors, and a deadline D, determine whether there exists an assignment
28/// of tasks to processors such that the total load on each processor does
29/// not exceed D.
30///
31/// Because tasks are independent and processors are identical, any feasible
32/// schedule can be packed processor-by-processor without idle gaps. This makes
33/// the scheduling question equivalent to partitioning tasks among processors
34/// with per-processor load at most `D`.
35///
36/// # Representation
37///
38/// Each task has a variable in `{0, ..., m-1}` representing its processor assignment.
39///
40/// # Example
41///
42/// ```
43/// use problemreductions::models::misc::MultiprocessorScheduling;
44/// use problemreductions::{Problem, BruteForce};
45///
46/// // 5 tasks with lengths [4, 5, 3, 2, 6], 2 processors, deadline 10
47/// let problem = MultiprocessorScheduling::new(vec![4, 5, 3, 2, 6], 2, 10);
48/// let solver = BruteForce::new();
49/// let solution = solver.solve(&problem).unwrap();
50/// assert!(solution.is_some());
51/// ```
52#[derive(Debug, Clone, Serialize, Deserialize)]
53#[serde(try_from = "MultiprocessorSchedulingCreateSpec")]
54pub struct MultiprocessorScheduling {
55    /// Processing time for each task.
56    lengths: Vec<i64>,
57    /// Number of identical processors.
58    num_processors: usize,
59    /// Global deadline.
60    deadline: i64,
61}
62
63#[derive(Debug, Deserialize, crate::CreateSpec)]
64struct MultiprocessorSchedulingCreateSpec {
65    /// Processing time for each task.
66    lengths: Vec<i64>,
67    /// Number of identical processors.
68    num_processors: usize,
69    /// Global deadline.
70    deadline: i64,
71}
72impl TryFrom<MultiprocessorSchedulingCreateSpec> for MultiprocessorScheduling {
73    type Error = crate::registry::ConstructionError;
74    fn try_from(spec: MultiprocessorSchedulingCreateSpec) -> Result<Self, Self::Error> {
75        Self::try_new(spec.lengths, spec.num_processors, spec.deadline)
76    }
77}
78
79impl MultiprocessorScheduling {
80    /// Create a new Multiprocessor Scheduling instance.
81    ///
82    /// # Panics
83    /// Panics if `num_processors` is zero.
84    pub fn new(lengths: Vec<i64>, num_processors: usize, deadline: i64) -> Self {
85        Self::try_new(lengths, num_processors, deadline).unwrap_or_else(|error| panic!("{error}"))
86    }
87
88    fn try_new(
89        lengths: Vec<i64>,
90        num_processors: usize,
91        deadline: i64,
92    ) -> Result<Self, crate::registry::ConstructionError> {
93        if num_processors == 0 {
94            return Err("num_processors must be positive".into());
95        }
96        if lengths.iter().any(|&length| length < 0) {
97            return Err("task lengths must be nonnegative".into());
98        }
99        if deadline < 0 {
100            return Err("deadline must be nonnegative".into());
101        }
102        Ok(Self {
103            lengths,
104            num_processors,
105            deadline,
106        })
107    }
108
109    /// Returns the processing times for each task.
110    pub fn lengths(&self) -> &[i64] {
111        &self.lengths
112    }
113
114    /// Returns the number of processors.
115    pub fn num_processors(&self) -> usize {
116        self.num_processors
117    }
118
119    /// Returns the deadline.
120    pub fn deadline(&self) -> i64 {
121        self.deadline
122    }
123
124    /// Returns the number of tasks.
125    pub fn num_tasks(&self) -> usize {
126        self.lengths.len()
127    }
128
129    /// Smallest h >= 1 such that every task length and the deadline are below 2^h.
130    pub fn max_numeric_magnitude_bits(&self) -> u64 {
131        crate::types::max_numeric_magnitude_bits(
132            self.lengths
133                .iter()
134                .copied()
135                .chain(std::iter::once(self.deadline)),
136        )
137    }
138
139    /// Returns the total processing time of all tasks.
140    pub fn total_length(&self) -> i64 {
141        self.lengths.iter().sum()
142    }
143}
144
145impl Problem for MultiprocessorScheduling {
146    const NAME: &'static str = "MultiprocessorScheduling";
147    type Solution = Vec<usize>;
148    type Value = crate::types::Or;
149
150    crate::problem_parameters![
151        ("max_numeric_magnitude_bits", max_numeric_magnitude_bits),
152        ("num_processors", num_processors),
153        ("num_tasks", num_tasks),
154    ];
155
156    fn variant() -> Vec<(&'static str, &'static str)> {
157        crate::variant_params![]
158    }
159
160    fn evaluate(
161        &self,
162        config: &Self::Solution,
163    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
164        Ok({
165            crate::types::Or({
166                if config.len() != self.num_tasks() {
167                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
168                        "processor assignment length does not match the tasks".into(),
169                    ));
170                }
171                let m = self.num_processors;
172                if config.iter().any(|&processor| processor >= m) {
173                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
174                        "assignment contains an out-of-range processor".into(),
175                    ));
176                }
177                let mut loads = vec![0i64; m];
178                for (i, &processor) in config.iter().enumerate() {
179                    loads[processor] =
180                        loads[processor]
181                            .checked_add(self.lengths[i])
182                            .ok_or_else(|| {
183                                crate::traits::EvaluationError::IntegerOverflow(
184                                    "summing multiprocessor load".into(),
185                                )
186                            })?;
187                }
188                loads.iter().all(|&load| load <= self.deadline)
189            })
190        })
191    }
192}
193
194impl crate::solvers::BruteForceProblem for MultiprocessorScheduling {
195    fn dimensions(&self) -> Vec<usize> {
196        vec![self.num_processors; self.num_tasks()]
197    }
198}
199
200crate::declare_variants! {
201    default MultiprocessorScheduling => "2^num_tasks" create MultiprocessorSchedulingCreateSpec,
202}
203
204crate::register_brute_force! {
205    MultiprocessorScheduling,
206}
207
208#[cfg(feature = "example-db")]
209pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
210    vec![crate::example_db::specs::ModelExampleSpec {
211        id: "multiprocessor_scheduling",
212        instance: Box::new(MultiprocessorScheduling::new(vec![4, 5, 3, 2, 6], 2, 10)),
213        optimal_config: serde_json::json!(vec![0, 1, 1, 1, 0]),
214        optimal_value: serde_json::json!(true),
215    }]
216}
217
218#[cfg(test)]
219#[path = "../../unit_tests/models/misc/multiprocessor_scheduling.rs"]
220mod tests;
problemreductions/models/misc/multiprocessor_scheduling.rs

problemreductions/models/misc/
multiprocessor_scheduling.rs
