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::{CreateSpec, 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        category: crate::registry::ProblemCategory::Misc,
21        module_path: module_path!(),
22        description: "Assign tasks to processors to minimize total weighted completion time (Smith's rule ordering)",
23        fields: SchedulingToMinimizeWeightedCompletionTimeCreateSpec::FIELDS,
24    }
25}
26
27/// Scheduling to Minimize Weighted Completion Time problem.
28///
29/// Given a set T of tasks with processing times `l(t)` and weights `w(t)`,
30/// and a number `m` of identical processors, find an assignment of tasks to
31/// processors that minimizes the total weighted completion time
32/// `sum_t w(t) * C(t)`, where `C(t) = start_time(t) + l(t)`.
33///
34/// Within each processor, tasks are ordered by Smith's rule: non-decreasing
35/// `l(t)/w(t)` ratio. The only free variables are the processor assignments.
36///
37/// # Representation
38///
39/// Each task has a variable in `{0, ..., m-1}` representing its processor
40/// assignment, giving `dims() = [m; n]`.
41///
42/// # Example
43///
44/// ```
45/// use problemreductions::models::misc::SchedulingToMinimizeWeightedCompletionTime;
46/// use problemreductions::{Problem, BruteForce};
47/// use problemreductions::types::Min;
48///
49/// // 5 tasks, 2 processors
50/// let problem = SchedulingToMinimizeWeightedCompletionTime::new(
51///     vec![1, 2, 3, 4, 5], vec![6, 4, 3, 2, 1], 2,
52/// );
53/// let solver = BruteForce::new();
54/// let witness = solver.solve(&problem).unwrap().unwrap();
55/// assert_eq!(problem.evaluate(&witness).unwrap(), Min(Some(47)));
56/// ```
57#[derive(Debug, Clone, Serialize)]
58pub struct SchedulingToMinimizeWeightedCompletionTime {
59    lengths: Vec<i64>,
60    weights: Vec<i64>,
61    #[serde(serialize_with = "serialize_num_processors")]
62    num_processors: usize,
63}
64
65#[derive(Debug, Deserialize, crate::CreateSpec)]
66struct SchedulingToMinimizeWeightedCompletionTimeCreateSpec {
67    /// Processing time for each task.
68    lengths: Vec<i64>,
69    /// Task weights; defaults to one per task.
70    weights: Option<Vec<i64>>,
71    /// Number of identical processors.
72    num_processors: usize,
73}
74impl TryFrom<SchedulingToMinimizeWeightedCompletionTimeCreateSpec>
75    for SchedulingToMinimizeWeightedCompletionTime
76{
77    type Error = crate::registry::ConstructionError;
78    fn try_from(
79        spec: SchedulingToMinimizeWeightedCompletionTimeCreateSpec,
80    ) -> Result<Self, Self::Error> {
81        if spec.num_processors == 0 {
82            return Err("num_processors must be positive".to_string().into());
83        }
84        let count = spec.lengths.len();
85        let weights = spec.weights.unwrap_or_else(|| vec![1; count]);
86        if weights.len() != count {
87            return Err("weights length must equal lengths length"
88                .to_string()
89                .into());
90        }
91        Ok(Self::new(spec.lengths, weights, spec.num_processors))
92    }
93}
94
95fn serialize_num_processors<S: serde::Serializer>(v: &usize, s: S) -> Result<S::Ok, S::Error> {
96    let value = i64::try_from(*v).map_err(serde::ser::Error::custom)?;
97    s.serialize_i64(value)
98}
99
100#[derive(Deserialize)]
101struct SchedulingToMinimizeWeightedCompletionTimeSerde {
102    lengths: Vec<i64>,
103    weights: Vec<i64>,
104    num_processors: usize,
105}
106
107impl SchedulingToMinimizeWeightedCompletionTime {
108    fn validate(
109        lengths: &[i64],
110        weights: &[i64],
111        num_processors: usize,
112    ) -> Result<(), crate::registry::ConstructionError> {
113        if lengths.len() != weights.len() {
114            return Err("lengths and weights must have the same length"
115                .to_string()
116                .into());
117        }
118        if num_processors == 0 {
119            return Err("num_processors must be positive".to_string().into());
120        }
121        if lengths.contains(&0) {
122            return Err("task lengths must be positive".to_string().into());
123        }
124        if weights.contains(&0) {
125            return Err("task weights must be positive".to_string().into());
126        }
127        Ok(())
128    }
129
130    /// Create a new scheduling instance.
131    ///
132    /// # Panics
133    ///
134    /// Panics if `lengths.len() != weights.len()`, if `num_processors` is zero,
135    /// or if any length or weight is zero.
136    pub fn new(lengths: Vec<i64>, weights: Vec<i64>, num_processors: usize) -> Self {
137        Self::validate(&lengths, &weights, num_processors).unwrap_or_else(|err| panic!("{err}"));
138        Self {
139            lengths,
140            weights,
141            num_processors,
142        }
143    }
144
145    /// Returns the number of tasks.
146    pub fn num_tasks(&self) -> usize {
147        self.lengths.len()
148    }
149
150    /// Returns the number of processors.
151    pub fn num_processors(&self) -> usize {
152        self.num_processors
153    }
154
155    /// Returns the processing times.
156    pub fn lengths(&self) -> &[i64] {
157        &self.lengths
158    }
159
160    /// Returns the task weights.
161    pub fn weights(&self) -> &[i64] {
162        &self.weights
163    }
164
165    /// Compute the total weighted completion time for a given processor
166    /// assignment. Tasks on each processor are ordered by Smith's rule
167    /// (non-decreasing l(t)/w(t) ratio).
168    fn compute_weighted_completion_time(
169        &self,
170        config: &[usize],
171    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
172        let n = self.num_tasks();
173        let m = self.num_processors;
174
175        if config.len() != n {
176            return Ok(Min(None));
177        }
178        if config.iter().any(|&p| p >= m) {
179            return Ok(Min(None));
180        }
181
182        // Group task indices by processor
183        let mut processor_tasks: Vec<Vec<usize>> = vec![vec![]; m];
184        for (task, &processor) in config.iter().enumerate() {
185            processor_tasks[processor].push(task);
186        }
187
188        let mut total_weighted_completion = 0i64;
189
190        for tasks in &mut processor_tasks {
191            // Smith's rule: sort by non-decreasing l(t)/w(t)
192            // Equivalent to: l(i)*w(j) <= l(j)*w(i) (avoids floating point)
193            for index in 1..tasks.len() {
194                let mut position = index;
195                while position > 0 {
196                    let a = tasks[position - 1];
197                    let b = tasks[position];
198                    let lhs = self.lengths[a]
199                        .checked_mul(self.weights[b])
200                        .ok_or_else(|| {
201                            crate::traits::EvaluationError::IntegerOverflow(
202                                "comparing weighted-completion task ratios".into(),
203                            )
204                        })?;
205                    let rhs = self.lengths[b]
206                        .checked_mul(self.weights[a])
207                        .ok_or_else(|| {
208                            crate::traits::EvaluationError::IntegerOverflow(
209                                "comparing weighted-completion task ratios".into(),
210                            )
211                        })?;
212                    if lhs < rhs || (lhs == rhs && a < b) {
213                        break;
214                    }
215                    tasks.swap(position - 1, position);
216                    position -= 1;
217                }
218            }
219
220            let mut elapsed = 0i64;
221            for &task in tasks.iter() {
222                elapsed = elapsed.checked_add(self.lengths[task]).ok_or_else(|| {
223                    crate::traits::EvaluationError::IntegerOverflow(
224                        "summing parallel-machine processing times".to_string(),
225                    )
226                })?;
227                let contribution = elapsed.checked_mul(self.weights[task]).ok_or_else(|| {
228                    crate::traits::EvaluationError::IntegerOverflow(
229                        "multiplying task weight by completion time".to_string(),
230                    )
231                })?;
232                total_weighted_completion = total_weighted_completion
233                    .checked_add(contribution)
234                    .ok_or_else(|| {
235                        crate::traits::EvaluationError::IntegerOverflow(
236                            "summing weighted completion times".to_string(),
237                        )
238                    })?;
239            }
240        }
241
242        Ok(Min(Some(total_weighted_completion)))
243    }
244}
245
246impl TryFrom<SchedulingToMinimizeWeightedCompletionTimeSerde>
247    for SchedulingToMinimizeWeightedCompletionTime
248{
249    type Error = crate::registry::ConstructionError;
250
251    fn try_from(
252        value: SchedulingToMinimizeWeightedCompletionTimeSerde,
253    ) -> Result<Self, Self::Error> {
254        Self::validate(&value.lengths, &value.weights, value.num_processors)?;
255        Ok(Self {
256            lengths: value.lengths,
257            weights: value.weights,
258            num_processors: value.num_processors,
259        })
260    }
261}
262
263impl<'de> Deserialize<'de> for SchedulingToMinimizeWeightedCompletionTime {
264    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
265    where
266        D: serde::Deserializer<'de>,
267    {
268        let value = SchedulingToMinimizeWeightedCompletionTimeSerde::deserialize(deserializer)?;
269        Self::try_from(value).map_err(serde::de::Error::custom)
270    }
271}
272
273impl Problem for SchedulingToMinimizeWeightedCompletionTime {
274    const NAME: &'static str = "SchedulingToMinimizeWeightedCompletionTime";
275    type Solution = Vec<usize>;
276    type Value = Min<i64>;
277
278    crate::problem_parameters![("num_processors", num_processors), ("num_tasks", num_tasks),];
279
280    fn variant() -> Vec<(&'static str, &'static str)> {
281        crate::variant_params![]
282    }
283
284    fn evaluate(
285        &self,
286        config: &Self::Solution,
287    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
288        if config.len() != self.num_tasks() {
289            return Err(crate::traits::EvaluationError::InvalidConfiguration(
290                "processor assignment length does not match the tasks".into(),
291            ));
292        }
293        if config
294            .iter()
295            .any(|&processor| processor >= self.num_processors)
296        {
297            return Err(crate::traits::EvaluationError::InvalidConfiguration(
298                "assignment contains an out-of-range processor".into(),
299            ));
300        }
301        self.compute_weighted_completion_time(config)
302    }
303}
304
305impl crate::solvers::BruteForceProblem for SchedulingToMinimizeWeightedCompletionTime {
306    fn dimensions(&self) -> Vec<usize> {
307        vec![self.num_processors; self.num_tasks()]
308    }
309}
310
311crate::declare_variants! {
312    default SchedulingToMinimizeWeightedCompletionTime => "num_processors^num_tasks" create SchedulingToMinimizeWeightedCompletionTimeCreateSpec,
313}
314
315crate::register_brute_force! {
316    SchedulingToMinimizeWeightedCompletionTime,
317}
318
319#[cfg(feature = "example-db")]
320pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
321    vec![crate::example_db::specs::ModelExampleSpec {
322        id: "scheduling_to_minimize_weighted_completion_time",
323        instance: Box::new(SchedulingToMinimizeWeightedCompletionTime::new(
324            vec![1, 2, 3, 4, 5],
325            vec![6, 4, 3, 2, 1],
326            2,
327        )),
328        // P0={t0,t2,t4}, P1={t1,t3} => config [0, 1, 0, 1, 0]
329        optimal_config: serde_json::json!(vec![0, 1, 0, 1, 0]),
330        optimal_value: serde_json::json!(47),
331    }]
332}
333
334#[cfg(test)]
335#[path = "../../unit_tests/models/misc/scheduling_to_minimize_weighted_completion_time.rs"]
336mod tests;
problemreductions/models/misc/scheduling_to_minimize_weighted_completion_time.rs

problemreductions/models/misc/
scheduling_to_minimize_weighted_completion_time.rs
