problemreductions/models/misc/
sequencing_to_minimize_weighted_completion_time.rs

1//! Sequencing to Minimize Weighted Completion Time problem implementation.
2//!
3//! A classical NP-hard single-machine scheduling problem (SS4 from
4//! Garey & Johnson, 1979) where tasks with processing times, weights,
5//! and precedence constraints must be scheduled to minimize the total
6//! weighted completion time.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use crate::types::Min;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "SequencingToMinimizeWeightedCompletionTime",
16        display_name: "Sequencing to Minimize Weighted Completion Time",
17        aliases: &[],
18        dimensions: &[],
19        module_path: module_path!(),
20        description: "Schedule tasks with lengths, weights, and precedence constraints to minimize total weighted completion time",
21        fields: &[
22            FieldInfo { name: "lengths", type_name: "Vec<u64>", description: "Processing time l(t) for each task" },
23            FieldInfo { name: "weights", type_name: "Vec<u64>", description: "Weight w(t) for each task" },
24            FieldInfo { name: "precedences", type_name: "Vec<(usize, usize)>", description: "Precedence pairs (predecessor, successor)" },
25        ],
26    }
27}
28
29/// Sequencing to Minimize Weighted Completion Time problem.
30///
31/// Given tasks with processing times `l(t)`, weights `w(t)`, and precedence
32/// constraints, find a single-machine schedule that respects the precedences
33/// and minimizes `sum_t w(t) * C(t)`, where `C(t)` is the completion time of
34/// task `t`.
35///
36/// Configurations use Lehmer code with `dims() = [n, n-1, ..., 1]`.
37#[derive(Debug, Clone, Serialize)]
38pub struct SequencingToMinimizeWeightedCompletionTime {
39    lengths: Vec<u64>,
40    weights: Vec<u64>,
41    precedences: Vec<(usize, usize)>,
42}
43
44#[derive(Deserialize)]
45struct SequencingToMinimizeWeightedCompletionTimeSerde {
46    lengths: Vec<u64>,
47    weights: Vec<u64>,
48    precedences: Vec<(usize, usize)>,
49}
50
51impl SequencingToMinimizeWeightedCompletionTime {
52    fn validate(
53        lengths: &[u64],
54        weights: &[u64],
55        precedences: &[(usize, usize)],
56    ) -> Result<(), String> {
57        if lengths.len() != weights.len() {
58            return Err("lengths length must equal weights length".to_string());
59        }
60        if lengths.contains(&0) {
61            return Err("task lengths must be positive".to_string());
62        }
63
64        let num_tasks = lengths.len();
65        for &(pred, succ) in precedences {
66            if pred >= num_tasks {
67                return Err(format!(
68                    "predecessor index {} out of range (num_tasks = {})",
69                    pred, num_tasks
70                ));
71            }
72            if succ >= num_tasks {
73                return Err(format!(
74                    "successor index {} out of range (num_tasks = {})",
75                    succ, num_tasks
76                ));
77            }
78        }
79
80        Ok(())
81    }
82
83    /// Create a new sequencing instance.
84    ///
85    /// # Panics
86    ///
87    /// Panics if `lengths.len() != weights.len()` or if any precedence endpoint
88    /// is out of range.
89    pub fn new(lengths: Vec<u64>, weights: Vec<u64>, precedences: Vec<(usize, usize)>) -> Self {
90        Self::validate(&lengths, &weights, &precedences).unwrap_or_else(|err| panic!("{err}"));
91
92        Self {
93            lengths,
94            weights,
95            precedences,
96        }
97    }
98
99    /// Returns the number of tasks.
100    pub fn num_tasks(&self) -> usize {
101        self.lengths.len()
102    }
103
104    /// Returns the processing times.
105    pub fn lengths(&self) -> &[u64] {
106        &self.lengths
107    }
108
109    /// Returns the task weights.
110    pub fn weights(&self) -> &[u64] {
111        &self.weights
112    }
113
114    /// Returns the precedence constraints.
115    pub fn precedences(&self) -> &[(usize, usize)] {
116        &self.precedences
117    }
118
119    /// Returns the number of precedence constraints.
120    pub fn num_precedences(&self) -> usize {
121        self.precedences.len()
122    }
123
124    /// Returns the sum of all processing times.
125    pub fn total_processing_time(&self) -> u64 {
126        self.lengths
127            .iter()
128            .try_fold(0u64, |acc, &length| acc.checked_add(length))
129            .expect("total processing time overflowed u64")
130    }
131
132    fn decode_schedule(&self, config: &[usize]) -> Option<Vec<usize>> {
133        super::decode_lehmer(config, self.num_tasks())
134    }
135
136    fn weighted_completion_time(&self, schedule: &[usize]) -> Min<u64> {
137        let n = self.num_tasks();
138        let mut positions = vec![0usize; n];
139        let mut completion_times = vec![0u64; n];
140        let mut elapsed = 0u64;
141
142        for (position, &task) in schedule.iter().enumerate() {
143            positions[task] = position;
144            elapsed = elapsed
145                .checked_add(self.lengths[task])
146                .expect("total processing time overflowed u64");
147            completion_times[task] = elapsed;
148        }
149
150        for &(pred, succ) in &self.precedences {
151            if positions[pred] >= positions[succ] {
152                return Min(None);
153            }
154        }
155
156        let total = completion_times
157            .iter()
158            .enumerate()
159            .try_fold(0u64, |acc, (task, &completion)| -> Option<u64> {
160                let weighted_completion = completion.checked_mul(self.weights[task])?;
161                acc.checked_add(weighted_completion)
162            })
163            .expect("weighted completion time overflowed u64");
164        Min(Some(total))
165    }
166}
167
168impl TryFrom<SequencingToMinimizeWeightedCompletionTimeSerde>
169    for SequencingToMinimizeWeightedCompletionTime
170{
171    type Error = String;
172
173    fn try_from(
174        value: SequencingToMinimizeWeightedCompletionTimeSerde,
175    ) -> Result<Self, Self::Error> {
176        Self::validate(&value.lengths, &value.weights, &value.precedences)?;
177        Ok(Self {
178            lengths: value.lengths,
179            weights: value.weights,
180            precedences: value.precedences,
181        })
182    }
183}
184
185impl<'de> Deserialize<'de> for SequencingToMinimizeWeightedCompletionTime {
186    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
187    where
188        D: serde::Deserializer<'de>,
189    {
190        let value = SequencingToMinimizeWeightedCompletionTimeSerde::deserialize(deserializer)?;
191        Self::try_from(value).map_err(serde::de::Error::custom)
192    }
193}
194
195impl Problem for SequencingToMinimizeWeightedCompletionTime {
196    const NAME: &'static str = "SequencingToMinimizeWeightedCompletionTime";
197    type Value = Min<u64>;
198
199    fn variant() -> Vec<(&'static str, &'static str)> {
200        crate::variant_params![]
201    }
202
203    fn dims(&self) -> Vec<usize> {
204        super::lehmer_dims(self.num_tasks())
205    }
206
207    fn evaluate(&self, config: &[usize]) -> Min<u64> {
208        let Some(schedule) = self.decode_schedule(config) else {
209            return Min(None);
210        };
211        self.weighted_completion_time(&schedule)
212    }
213}
214
215crate::declare_variants! {
216    default SequencingToMinimizeWeightedCompletionTime => "factorial(num_tasks)",
217}
218
219#[cfg(feature = "example-db")]
220pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
221    vec![crate::example_db::specs::ModelExampleSpec {
222        id: "sequencing_to_minimize_weighted_completion_time",
223        instance: Box::new(SequencingToMinimizeWeightedCompletionTime::new(
224            vec![2, 1, 3, 1, 2],
225            vec![3, 5, 1, 4, 2],
226            vec![(0, 2), (1, 4)],
227        )),
228        optimal_config: vec![1, 2, 0, 1, 0],
229        optimal_value: serde_json::json!(46),
230    }]
231}
232
233#[cfg(test)]
234#[path = "../../unit_tests/models/misc/sequencing_to_minimize_weighted_completion_time.rs"]
235mod tests;
problemreductions/models/misc/sequencing_to_minimize_weighted_completion_time.rs

problemreductions/models/misc/
sequencing_to_minimize_weighted_completion_time.rs
