problemreductions/models/misc/
scheduling_to_minimize_weighted_completion_time.rs

1//! Scheduling to Minimize Weighted Completion Time problem implementation.
2//!
3//! An NP-hard multiprocessor scheduling optimization problem (SS13 from
4//! Garey & Johnson, 1979) where tasks with processing times and weights
5//! must be assigned to identical processors to minimize the total weighted
6//! completion time. Within each processor, tasks are ordered by Smith's
7//! rule (non-decreasing length-to-weight ratio).
8
9use crate::registry::{FieldInfo, ProblemSchemaEntry};
10use crate::traits::Problem;
11use crate::types::Min;
12use serde::{Deserialize, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "SchedulingToMinimizeWeightedCompletionTime",
17        display_name: "Scheduling to Minimize Weighted Completion Time",
18        aliases: &[],
19        dimensions: &[],
20        module_path: module_path!(),
21        description: "Assign tasks to processors to minimize total weighted completion time (Smith's rule ordering)",
22        fields: &[
23            FieldInfo { name: "lengths", type_name: "Vec<u64>", description: "Processing time l(t) for each task" },
24            FieldInfo { name: "weights", type_name: "Vec<u64>", description: "Weight w(t) for each task" },
25            FieldInfo { name: "num_processors", type_name: "usize", description: "Number of identical processors m" },
26        ],
27    }
28}
29
30/// Scheduling to Minimize Weighted Completion Time problem.
31///
32/// Given a set T of tasks with processing times `l(t)` and weights `w(t)`,
33/// and a number `m` of identical processors, find an assignment of tasks to
34/// processors that minimizes the total weighted completion time
35/// `sum_t w(t) * C(t)`, where `C(t) = start_time(t) + l(t)`.
36///
37/// Within each processor, tasks are ordered by Smith's rule: non-decreasing
38/// `l(t)/w(t)` ratio. The only free variables are the processor assignments.
39///
40/// # Representation
41///
42/// Each task has a variable in `{0, ..., m-1}` representing its processor
43/// assignment, giving `dims() = [m; n]`.
44///
45/// # Example
46///
47/// ```
48/// use problemreductions::models::misc::SchedulingToMinimizeWeightedCompletionTime;
49/// use problemreductions::{Problem, Solver, BruteForce};
50/// use problemreductions::types::Min;
51///
52/// // 5 tasks, 2 processors
53/// let problem = SchedulingToMinimizeWeightedCompletionTime::new(
54///     vec![1, 2, 3, 4, 5], vec![6, 4, 3, 2, 1], 2,
55/// );
56/// let solver = BruteForce::new();
57/// let witness = solver.find_witness(&problem).unwrap();
58/// assert_eq!(problem.evaluate(&witness), Min(Some(47)));
59/// ```
60#[derive(Debug, Clone, Serialize)]
61pub struct SchedulingToMinimizeWeightedCompletionTime {
62    lengths: Vec<u64>,
63    weights: Vec<u64>,
64    #[serde(serialize_with = "serialize_num_processors")]
65    num_processors: usize,
66}
67
68fn serialize_num_processors<S: serde::Serializer>(v: &usize, s: S) -> Result<S::Ok, S::Error> {
69    s.serialize_u64(*v as u64)
70}
71
72#[derive(Deserialize)]
73struct SchedulingToMinimizeWeightedCompletionTimeSerde {
74    lengths: Vec<u64>,
75    weights: Vec<u64>,
76    num_processors: usize,
77}
78
79impl SchedulingToMinimizeWeightedCompletionTime {
80    fn validate(lengths: &[u64], weights: &[u64], num_processors: usize) -> Result<(), String> {
81        if lengths.len() != weights.len() {
82            return Err("lengths and weights must have the same length".to_string());
83        }
84        if num_processors == 0 {
85            return Err("num_processors must be positive".to_string());
86        }
87        if lengths.contains(&0) {
88            return Err("task lengths must be positive".to_string());
89        }
90        if weights.contains(&0) {
91            return Err("task weights must be positive".to_string());
92        }
93        Ok(())
94    }
95
96    /// Create a new scheduling instance.
97    ///
98    /// # Panics
99    ///
100    /// Panics if `lengths.len() != weights.len()`, if `num_processors` is zero,
101    /// or if any length or weight is zero.
102    pub fn new(lengths: Vec<u64>, weights: Vec<u64>, num_processors: usize) -> Self {
103        Self::validate(&lengths, &weights, num_processors).unwrap_or_else(|err| panic!("{err}"));
104        Self {
105            lengths,
106            weights,
107            num_processors,
108        }
109    }
110
111    /// Returns the number of tasks.
112    pub fn num_tasks(&self) -> usize {
113        self.lengths.len()
114    }
115
116    /// Returns the number of processors.
117    pub fn num_processors(&self) -> usize {
118        self.num_processors
119    }
120
121    /// Returns the processing times.
122    pub fn lengths(&self) -> &[u64] {
123        &self.lengths
124    }
125
126    /// Returns the task weights.
127    pub fn weights(&self) -> &[u64] {
128        &self.weights
129    }
130
131    /// Compute the total weighted completion time for a given processor
132    /// assignment. Tasks on each processor are ordered by Smith's rule
133    /// (non-decreasing l(t)/w(t) ratio).
134    fn compute_weighted_completion_time(&self, config: &[usize]) -> Min<u64> {
135        let n = self.num_tasks();
136        let m = self.num_processors;
137
138        if config.len() != n {
139            return Min(None);
140        }
141        if config.iter().any(|&p| p >= m) {
142            return Min(None);
143        }
144
145        // Group task indices by processor
146        let mut processor_tasks: Vec<Vec<usize>> = vec![vec![]; m];
147        for (task, &processor) in config.iter().enumerate() {
148            processor_tasks[processor].push(task);
149        }
150
151        let mut total_weighted_completion = 0u64;
152
153        for tasks in &mut processor_tasks {
154            // Smith's rule: sort by non-decreasing l(t)/w(t)
155            // Equivalent to: l(i)*w(j) <= l(j)*w(i) (avoids floating point)
156            tasks.sort_by(|&a, &b| {
157                let lhs = self.lengths[a] as u128 * self.weights[b] as u128;
158                let rhs = self.lengths[b] as u128 * self.weights[a] as u128;
159                lhs.cmp(&rhs).then(a.cmp(&b))
160            });
161
162            let mut elapsed = 0u64;
163            for &task in tasks.iter() {
164                elapsed = elapsed
165                    .checked_add(self.lengths[task])
166                    .expect("processing time overflowed u64");
167                let contribution = elapsed
168                    .checked_mul(self.weights[task])
169                    .expect("weighted completion time overflowed u64");
170                total_weighted_completion = total_weighted_completion
171                    .checked_add(contribution)
172                    .expect("total weighted completion time overflowed u64");
173            }
174        }
175
176        Min(Some(total_weighted_completion))
177    }
178}
179
180impl TryFrom<SchedulingToMinimizeWeightedCompletionTimeSerde>
181    for SchedulingToMinimizeWeightedCompletionTime
182{
183    type Error = String;
184
185    fn try_from(
186        value: SchedulingToMinimizeWeightedCompletionTimeSerde,
187    ) -> Result<Self, Self::Error> {
188        Self::validate(&value.lengths, &value.weights, value.num_processors)?;
189        Ok(Self {
190            lengths: value.lengths,
191            weights: value.weights,
192            num_processors: value.num_processors,
193        })
194    }
195}
196
197impl<'de> Deserialize<'de> for SchedulingToMinimizeWeightedCompletionTime {
198    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
199    where
200        D: serde::Deserializer<'de>,
201    {
202        let value = SchedulingToMinimizeWeightedCompletionTimeSerde::deserialize(deserializer)?;
203        Self::try_from(value).map_err(serde::de::Error::custom)
204    }
205}
206
207impl Problem for SchedulingToMinimizeWeightedCompletionTime {
208    const NAME: &'static str = "SchedulingToMinimizeWeightedCompletionTime";
209    type Value = Min<u64>;
210
211    fn variant() -> Vec<(&'static str, &'static str)> {
212        crate::variant_params![]
213    }
214
215    fn dims(&self) -> Vec<usize> {
216        vec![self.num_processors; self.num_tasks()]
217    }
218
219    fn evaluate(&self, config: &[usize]) -> Min<u64> {
220        self.compute_weighted_completion_time(config)
221    }
222}
223
224crate::declare_variants! {
225    default SchedulingToMinimizeWeightedCompletionTime => "num_processors^num_tasks",
226}
227
228#[cfg(feature = "example-db")]
229pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
230    vec![crate::example_db::specs::ModelExampleSpec {
231        id: "scheduling_to_minimize_weighted_completion_time",
232        instance: Box::new(SchedulingToMinimizeWeightedCompletionTime::new(
233            vec![1, 2, 3, 4, 5],
234            vec![6, 4, 3, 2, 1],
235            2,
236        )),
237        // P0={t0,t2,t4}, P1={t1,t3} => config [0, 1, 0, 1, 0]
238        optimal_config: vec![0, 1, 0, 1, 0],
239        optimal_value: serde_json::json!(47),
240    }]
241}
242
243#[cfg(test)]
244#[path = "../../unit_tests/models/misc/scheduling_to_minimize_weighted_completion_time.rs"]
245mod tests;
problemreductions/models/misc/scheduling_to_minimize_weighted_completion_time.rs

problemreductions/models/misc/
scheduling_to_minimize_weighted_completion_time.rs
