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    /// Smallest h >= 1 bounding every processing time in magnitude strictly by 2^h.
146    pub fn max_processing_time_bits(&self) -> u64 {
147        crate::types::max_numeric_magnitude_bits(self.lengths.iter().copied())
148    }
149
150    /// Returns the number of tasks.
151    pub fn num_tasks(&self) -> usize {
152        self.lengths.len()
153    }
154
155    /// Returns the number of processors.
156    pub fn num_processors(&self) -> usize {
157        self.num_processors
158    }
159
160    /// Returns the processing times.
161    pub fn lengths(&self) -> &[i64] {
162        &self.lengths
163    }
164
165    /// Returns the task weights.
166    pub fn weights(&self) -> &[i64] {
167        &self.weights
168    }
169
170    /// Compute the total weighted completion time for a given processor
171    /// assignment. Tasks on each processor are ordered by Smith's rule
172    /// (non-decreasing l(t)/w(t) ratio).
173    fn compute_weighted_completion_time(
174        &self,
175        config: &[usize],
176    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
177        let n = self.num_tasks();
178        let m = self.num_processors;
179
180        if config.len() != n {
181            return Ok(Min(None));
182        }
183        if config.iter().any(|&p| p >= m) {
184            return Ok(Min(None));
185        }
186
187        // Group task indices by processor
188        let mut processor_tasks: Vec<Vec<usize>> = vec![vec![]; m];
189        for (task, &processor) in config.iter().enumerate() {
190            processor_tasks[processor].push(task);
191        }
192
193        let mut total_weighted_completion = 0i64;
194
195        for tasks in &mut processor_tasks {
196            // Smith's rule: sort by non-decreasing l(t)/w(t)
197            // Equivalent to: l(i)*w(j) <= l(j)*w(i) (avoids floating point)
198            for index in 1..tasks.len() {
199                let mut position = index;
200                while position > 0 {
201                    let a = tasks[position - 1];
202                    let b = tasks[position];
203                    let lhs = self.lengths[a]
204                        .checked_mul(self.weights[b])
205                        .ok_or_else(|| {
206                            crate::traits::EvaluationError::IntegerOverflow(
207                                "comparing weighted-completion task ratios".into(),
208                            )
209                        })?;
210                    let rhs = self.lengths[b]
211                        .checked_mul(self.weights[a])
212                        .ok_or_else(|| {
213                            crate::traits::EvaluationError::IntegerOverflow(
214                                "comparing weighted-completion task ratios".into(),
215                            )
216                        })?;
217                    if lhs < rhs || (lhs == rhs && a < b) {
218                        break;
219                    }
220                    tasks.swap(position - 1, position);
221                    position -= 1;
222                }
223            }
224
225            let mut elapsed = 0i64;
226            for &task in tasks.iter() {
227                elapsed = elapsed.checked_add(self.lengths[task]).ok_or_else(|| {
228                    crate::traits::EvaluationError::IntegerOverflow(
229                        "summing parallel-machine processing times".to_string(),
230                    )
231                })?;
232                let contribution = elapsed.checked_mul(self.weights[task]).ok_or_else(|| {
233                    crate::traits::EvaluationError::IntegerOverflow(
234                        "multiplying task weight by completion time".to_string(),
235                    )
236                })?;
237                total_weighted_completion = total_weighted_completion
238                    .checked_add(contribution)
239                    .ok_or_else(|| {
240                        crate::traits::EvaluationError::IntegerOverflow(
241                            "summing weighted completion times".to_string(),
242                        )
243                    })?;
244            }
245        }
246
247        Ok(Min(Some(total_weighted_completion)))
248    }
249}
250
251impl TryFrom<SchedulingToMinimizeWeightedCompletionTimeSerde>
252    for SchedulingToMinimizeWeightedCompletionTime
253{
254    type Error = crate::registry::ConstructionError;
255
256    fn try_from(
257        value: SchedulingToMinimizeWeightedCompletionTimeSerde,
258    ) -> Result<Self, Self::Error> {
259        Self::validate(&value.lengths, &value.weights, value.num_processors)?;
260        Ok(Self {
261            lengths: value.lengths,
262            weights: value.weights,
263            num_processors: value.num_processors,
264        })
265    }
266}
267
268impl<'de> Deserialize<'de> for SchedulingToMinimizeWeightedCompletionTime {
269    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
270    where
271        D: serde::Deserializer<'de>,
272    {
273        let value = SchedulingToMinimizeWeightedCompletionTimeSerde::deserialize(deserializer)?;
274        Self::try_from(value).map_err(serde::de::Error::custom)
275    }
276}
277
278impl Problem for SchedulingToMinimizeWeightedCompletionTime {
279    const NAME: &'static str = "SchedulingToMinimizeWeightedCompletionTime";
280    type Solution = Vec<usize>;
281    type Value = Min<i64>;
282
283    crate::problem_parameters![
284        ("max_processing_time_bits", max_processing_time_bits),
285        ("num_processors", num_processors),
286        ("num_tasks", num_tasks),
287    ];
288
289    fn variant() -> Vec<(&'static str, &'static str)> {
290        crate::variant_params![]
291    }
292
293    fn evaluate(
294        &self,
295        config: &Self::Solution,
296    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
297        if config.len() != self.num_tasks() {
298            return Err(crate::traits::EvaluationError::InvalidConfiguration(
299                "processor assignment length does not match the tasks".into(),
300            ));
301        }
302        if config
303            .iter()
304            .any(|&processor| processor >= self.num_processors)
305        {
306            return Err(crate::traits::EvaluationError::InvalidConfiguration(
307                "assignment contains an out-of-range processor".into(),
308            ));
309        }
310        self.compute_weighted_completion_time(config)
311    }
312}
313
314impl crate::solvers::BruteForceProblem for SchedulingToMinimizeWeightedCompletionTime {
315    fn dimensions(&self) -> Vec<usize> {
316        vec![self.num_processors; self.num_tasks()]
317    }
318}
319
320crate::declare_variants! {
321    default SchedulingToMinimizeWeightedCompletionTime => "num_processors^num_tasks" create SchedulingToMinimizeWeightedCompletionTimeCreateSpec,
322}
323
324crate::register_brute_force! {
325    SchedulingToMinimizeWeightedCompletionTime,
326}
327
328#[cfg(feature = "example-db")]
329pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
330    vec![crate::example_db::specs::ModelExampleSpec {
331        id: "scheduling_to_minimize_weighted_completion_time",
332        instance: Box::new(SchedulingToMinimizeWeightedCompletionTime::new(
333            vec![1, 2, 3, 4, 5],
334            vec![6, 4, 3, 2, 1],
335            2,
336        )),
337        // P0={t0,t2,t4}, P1={t1,t3} => config [0, 1, 0, 1, 0]
338        optimal_config: serde_json::json!(vec![0, 1, 0, 1, 0]),
339        optimal_value: serde_json::json!(47),
340    }]
341}
342
343#[cfg(test)]
344#[path = "../../unit_tests/models/misc/scheduling_to_minimize_weighted_completion_time.rs"]
345mod tests;
problemreductions/models/misc/scheduling_to_minimize_weighted_completion_time.rs

problemreductions/models/misc/
scheduling_to_minimize_weighted_completion_time.rs
