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//!
8//! This model accepts zero-length tasks in addition to positive-length
9//! tasks. That choice matches the standard Lawler reduction from
10//! Optimal Linear Arrangement, which uses zero-length edge jobs instead
11//! of padding them to unit length.
12
13use crate::registry::{CreateSpec, ProblemSchemaEntry};
14use crate::traits::Problem;
15use crate::types::Min;
16use serde::{Deserialize, Serialize};
17
18inventory::submit! {
19    ProblemSchemaEntry {
20        name: "SequencingToMinimizeWeightedCompletionTime",
21        display_name: "Sequencing to Minimize Weighted Completion Time",
22        aliases: &[],
23        dimensions: &[],
24        category: crate::registry::ProblemCategory::Misc,
25        module_path: module_path!(),
26        description: "Schedule tasks with lengths, weights, and precedence constraints to minimize total weighted completion time",
27        fields: SequencingToMinimizeWeightedCompletionTimeCreateSpec::FIELDS,
28    }
29}
30
31/// Sequencing to Minimize Weighted Completion Time problem.
32///
33/// Given tasks with nonnegative processing times `l(t)`, weights `w(t)`, and precedence
34/// constraints, find a single-machine schedule that respects the precedences
35/// and minimizes `sum_t w(t) * C(t)`, where `C(t)` is the completion time of
36/// task `t`.
37///
38/// Configurations use Lehmer code with `dims() = [n, n-1, ..., 1]`.
39#[derive(Debug, Clone, Serialize)]
40pub struct SequencingToMinimizeWeightedCompletionTime {
41    lengths: Vec<i64>,
42    weights: Vec<i64>,
43    precedences: Vec<(usize, usize)>,
44}
45
46#[derive(Debug, Deserialize, crate::CreateSpec)]
47struct SequencingToMinimizeWeightedCompletionTimeCreateSpec {
48    lengths: Vec<i64>,
49    weights: Vec<i64>,
50    precedences: Option<Vec<(usize, usize)>>,
51}
52
53impl TryFrom<SequencingToMinimizeWeightedCompletionTimeCreateSpec>
54    for SequencingToMinimizeWeightedCompletionTime
55{
56    type Error = crate::registry::ConstructionError;
57
58    fn try_from(
59        spec: SequencingToMinimizeWeightedCompletionTimeCreateSpec,
60    ) -> Result<Self, Self::Error> {
61        let precedences = spec.precedences.unwrap_or_default();
62        Self::validate(&spec.lengths, &spec.weights, &precedences)?;
63        Ok(Self::new(spec.lengths, spec.weights, precedences))
64    }
65}
66
67#[derive(Deserialize)]
68struct SequencingToMinimizeWeightedCompletionTimeSerde {
69    lengths: Vec<i64>,
70    weights: Vec<i64>,
71    precedences: Vec<(usize, usize)>,
72}
73
74impl SequencingToMinimizeWeightedCompletionTime {
75    fn validate(
76        lengths: &[i64],
77        weights: &[i64],
78        precedences: &[(usize, usize)],
79    ) -> Result<(), crate::registry::ConstructionError> {
80        if lengths.len() != weights.len() {
81            return Err("lengths length must equal weights length"
82                .to_string()
83                .into());
84        }
85
86        let num_tasks = lengths.len();
87        for &(pred, succ) in precedences {
88            if pred >= num_tasks {
89                return Err(format!(
90                    "predecessor index {} out of range (num_tasks = {})",
91                    pred, num_tasks
92                )
93                .into());
94            }
95            if succ >= num_tasks {
96                return Err(format!(
97                    "successor index {} out of range (num_tasks = {})",
98                    succ, num_tasks
99                )
100                .into());
101            }
102        }
103
104        Ok(())
105    }
106
107    /// Create a new sequencing instance.
108    ///
109    /// # Panics
110    ///
111    /// Panics if `lengths.len() != weights.len()` or if any precedence
112    /// endpoint is out of range.
113    pub fn new(lengths: Vec<i64>, weights: Vec<i64>, precedences: Vec<(usize, usize)>) -> Self {
114        Self::validate(&lengths, &weights, &precedences).unwrap_or_else(|err| panic!("{err}"));
115
116        Self {
117            lengths,
118            weights,
119            precedences,
120        }
121    }
122
123    /// Smallest h >= 1 bounding every processing time in magnitude strictly by 2^h.
124    pub fn max_processing_time_bits(&self) -> u64 {
125        crate::types::max_numeric_magnitude_bits(self.lengths.iter().copied())
126    }
127
128    /// Returns the number of tasks.
129    pub fn num_tasks(&self) -> usize {
130        self.lengths.len()
131    }
132
133    /// Returns the processing times.
134    pub fn lengths(&self) -> &[i64] {
135        &self.lengths
136    }
137
138    /// Returns the task weights.
139    pub fn weights(&self) -> &[i64] {
140        &self.weights
141    }
142
143    /// Returns the precedence constraints.
144    pub fn precedences(&self) -> &[(usize, usize)] {
145        &self.precedences
146    }
147
148    /// Returns the number of precedence constraints.
149    pub fn num_precedences(&self) -> usize {
150        self.precedences.len()
151    }
152
153    fn decode_schedule(&self, config: &[usize]) -> Option<Vec<usize>> {
154        super::decode_permutation(config, self.num_tasks())
155    }
156
157    fn weighted_completion_time(
158        &self,
159        schedule: &[usize],
160    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
161        let n = self.num_tasks();
162        let mut positions = vec![0usize; n];
163        let mut completion_times = vec![0i64; n];
164        let mut elapsed = 0i64;
165
166        for (position, &task) in schedule.iter().enumerate() {
167            positions[task] = position;
168            elapsed = elapsed.checked_add(self.lengths[task]).ok_or_else(|| {
169                crate::traits::EvaluationError::IntegerOverflow(
170                    "summing sequencing processing times".to_string(),
171                )
172            })?;
173            completion_times[task] = elapsed;
174        }
175
176        for &(pred, succ) in &self.precedences {
177            if positions[pred] >= positions[succ] {
178                return Ok(Min(None));
179            }
180        }
181
182        let total = completion_times
183            .iter()
184            .enumerate()
185            .try_fold(0i64, |acc, (task, &completion)| -> Option<i64> {
186                let weighted_completion = completion.checked_mul(self.weights[task])?;
187                acc.checked_add(weighted_completion)
188            })
189            .ok_or_else(|| {
190                crate::traits::EvaluationError::IntegerOverflow(
191                    "computing weighted completion time".to_string(),
192                )
193            })?;
194        Ok(Min(Some(total)))
195    }
196}
197
198impl TryFrom<SequencingToMinimizeWeightedCompletionTimeSerde>
199    for SequencingToMinimizeWeightedCompletionTime
200{
201    type Error = crate::registry::ConstructionError;
202
203    fn try_from(
204        value: SequencingToMinimizeWeightedCompletionTimeSerde,
205    ) -> Result<Self, Self::Error> {
206        Self::validate(&value.lengths, &value.weights, &value.precedences)?;
207        Ok(Self {
208            lengths: value.lengths,
209            weights: value.weights,
210            precedences: value.precedences,
211        })
212    }
213}
214
215impl<'de> Deserialize<'de> for SequencingToMinimizeWeightedCompletionTime {
216    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
217    where
218        D: serde::Deserializer<'de>,
219    {
220        let value = SequencingToMinimizeWeightedCompletionTimeSerde::deserialize(deserializer)?;
221        Self::try_from(value).map_err(serde::de::Error::custom)
222    }
223}
224
225impl Problem for SequencingToMinimizeWeightedCompletionTime {
226    const NAME: &'static str = "SequencingToMinimizeWeightedCompletionTime";
227    type Solution = Vec<usize>;
228    type Value = Min<i64>;
229
230    crate::problem_parameters![
231        ("max_processing_time_bits", max_processing_time_bits),
232        ("num_precedences", num_precedences),
233        ("num_tasks", num_tasks),
234    ];
235
236    fn variant() -> Vec<(&'static str, &'static str)> {
237        crate::variant_params![]
238    }
239
240    fn evaluate(
241        &self,
242        config: &Self::Solution,
243    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
244        let n = self.num_tasks();
245        if config.len() != n {
246            return Err(crate::traits::EvaluationError::InvalidConfiguration(
247                "schedule length does not match the tasks".into(),
248            ));
249        }
250        if config.iter().any(|&task| task >= n) {
251            return Err(crate::traits::EvaluationError::InvalidConfiguration(
252                "schedule contains an out-of-range task".into(),
253            ));
254        }
255        Ok({
256            let Some(schedule) = self.decode_schedule(config) else {
257                return Ok(Min(None));
258            };
259            self.weighted_completion_time(&schedule)?
260        })
261    }
262}
263
264impl crate::solvers::BruteForceProblem for SequencingToMinimizeWeightedCompletionTime {
265    fn dimensions(&self) -> Vec<usize> {
266        super::lehmer_dims(self.num_tasks())
267    }
268}
269
270crate::declare_variants! {
271    default SequencingToMinimizeWeightedCompletionTime => "factorial(num_tasks)" create SequencingToMinimizeWeightedCompletionTimeCreateSpec,
272}
273
274crate::register_brute_force! {
275    SequencingToMinimizeWeightedCompletionTime decode |problem: &SequencingToMinimizeWeightedCompletionTime, indices: Vec<usize>| super::decode_lehmer(&indices, problem.num_tasks()).expect("enumerated Lehmer digits are valid"),
276}
277
278#[cfg(feature = "example-db")]
279pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
280    vec![crate::example_db::specs::ModelExampleSpec {
281        id: "sequencing_to_minimize_weighted_completion_time",
282        instance: Box::new(SequencingToMinimizeWeightedCompletionTime::new(
283            vec![2, 1, 3, 1, 2],
284            vec![3, 5, 1, 4, 2],
285            vec![(0, 2), (1, 4)],
286        )),
287        optimal_config: serde_json::json!(vec![1, 3, 0, 4, 2]),
288        optimal_value: serde_json::json!(46),
289    }]
290}
291
292#[cfg(test)]
293#[path = "../../unit_tests/models/misc/sequencing_to_minimize_weighted_completion_time.rs"]
294mod tests;
problemreductions/models/misc/sequencing_to_minimize_weighted_completion_time.rs

problemreductions/models/misc/
sequencing_to_minimize_weighted_completion_time.rs
