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    /// Returns the number of tasks.
124    pub fn num_tasks(&self) -> usize {
125        self.lengths.len()
126    }
127
128    /// Returns the processing times.
129    pub fn lengths(&self) -> &[i64] {
130        &self.lengths
131    }
132
133    /// Returns the task weights.
134    pub fn weights(&self) -> &[i64] {
135        &self.weights
136    }
137
138    /// Returns the precedence constraints.
139    pub fn precedences(&self) -> &[(usize, usize)] {
140        &self.precedences
141    }
142
143    /// Returns the number of precedence constraints.
144    pub fn num_precedences(&self) -> usize {
145        self.precedences.len()
146    }
147
148    fn decode_schedule(&self, config: &[usize]) -> Option<Vec<usize>> {
149        super::decode_permutation(config, self.num_tasks())
150    }
151
152    fn weighted_completion_time(
153        &self,
154        schedule: &[usize],
155    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
156        let n = self.num_tasks();
157        let mut positions = vec![0usize; n];
158        let mut completion_times = vec![0i64; n];
159        let mut elapsed = 0i64;
160
161        for (position, &task) in schedule.iter().enumerate() {
162            positions[task] = position;
163            elapsed = elapsed.checked_add(self.lengths[task]).ok_or_else(|| {
164                crate::traits::EvaluationError::IntegerOverflow(
165                    "summing sequencing processing times".to_string(),
166                )
167            })?;
168            completion_times[task] = elapsed;
169        }
170
171        for &(pred, succ) in &self.precedences {
172            if positions[pred] >= positions[succ] {
173                return Ok(Min(None));
174            }
175        }
176
177        let total = completion_times
178            .iter()
179            .enumerate()
180            .try_fold(0i64, |acc, (task, &completion)| -> Option<i64> {
181                let weighted_completion = completion.checked_mul(self.weights[task])?;
182                acc.checked_add(weighted_completion)
183            })
184            .ok_or_else(|| {
185                crate::traits::EvaluationError::IntegerOverflow(
186                    "computing weighted completion time".to_string(),
187                )
188            })?;
189        Ok(Min(Some(total)))
190    }
191}
192
193impl TryFrom<SequencingToMinimizeWeightedCompletionTimeSerde>
194    for SequencingToMinimizeWeightedCompletionTime
195{
196    type Error = crate::registry::ConstructionError;
197
198    fn try_from(
199        value: SequencingToMinimizeWeightedCompletionTimeSerde,
200    ) -> Result<Self, Self::Error> {
201        Self::validate(&value.lengths, &value.weights, &value.precedences)?;
202        Ok(Self {
203            lengths: value.lengths,
204            weights: value.weights,
205            precedences: value.precedences,
206        })
207    }
208}
209
210impl<'de> Deserialize<'de> for SequencingToMinimizeWeightedCompletionTime {
211    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
212    where
213        D: serde::Deserializer<'de>,
214    {
215        let value = SequencingToMinimizeWeightedCompletionTimeSerde::deserialize(deserializer)?;
216        Self::try_from(value).map_err(serde::de::Error::custom)
217    }
218}
219
220impl Problem for SequencingToMinimizeWeightedCompletionTime {
221    const NAME: &'static str = "SequencingToMinimizeWeightedCompletionTime";
222    type Solution = Vec<usize>;
223    type Value = Min<i64>;
224
225    crate::problem_parameters![
226        ("num_precedences", num_precedences),
227        ("num_tasks", num_tasks),
228    ];
229
230    fn variant() -> Vec<(&'static str, &'static str)> {
231        crate::variant_params![]
232    }
233
234    fn evaluate(
235        &self,
236        config: &Self::Solution,
237    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
238        let n = self.num_tasks();
239        if config.len() != n {
240            return Err(crate::traits::EvaluationError::InvalidConfiguration(
241                "schedule length does not match the tasks".into(),
242            ));
243        }
244        if config.iter().any(|&task| task >= n) {
245            return Err(crate::traits::EvaluationError::InvalidConfiguration(
246                "schedule contains an out-of-range task".into(),
247            ));
248        }
249        Ok({
250            let Some(schedule) = self.decode_schedule(config) else {
251                return Ok(Min(None));
252            };
253            self.weighted_completion_time(&schedule)?
254        })
255    }
256}
257
258impl crate::solvers::BruteForceProblem for SequencingToMinimizeWeightedCompletionTime {
259    fn dimensions(&self) -> Vec<usize> {
260        super::lehmer_dims(self.num_tasks())
261    }
262}
263
264crate::declare_variants! {
265    default SequencingToMinimizeWeightedCompletionTime => "factorial(num_tasks)" create SequencingToMinimizeWeightedCompletionTimeCreateSpec,
266}
267
268crate::register_brute_force! {
269    SequencingToMinimizeWeightedCompletionTime decode |problem: &SequencingToMinimizeWeightedCompletionTime, indices: Vec<usize>| super::decode_lehmer(&indices, problem.num_tasks()).expect("enumerated Lehmer digits are valid"),
270}
271
272#[cfg(feature = "example-db")]
273pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
274    vec![crate::example_db::specs::ModelExampleSpec {
275        id: "sequencing_to_minimize_weighted_completion_time",
276        instance: Box::new(SequencingToMinimizeWeightedCompletionTime::new(
277            vec![2, 1, 3, 1, 2],
278            vec![3, 5, 1, 4, 2],
279            vec![(0, 2), (1, 4)],
280        )),
281        optimal_config: serde_json::json!(vec![1, 3, 0, 4, 2]),
282        optimal_value: serde_json::json!(46),
283    }]
284}
285
286#[cfg(test)]
287#[path = "../../unit_tests/models/misc/sequencing_to_minimize_weighted_completion_time.rs"]
288mod tests;
problemreductions/models/misc/sequencing_to_minimize_weighted_completion_time.rs

problemreductions/models/misc/
sequencing_to_minimize_weighted_completion_time.rs
