problemreductions/models/misc/
sequencing_to_minimize_weighted_tardiness.rs

1//! Sequencing to Minimize Weighted Tardiness problem implementation.
2//!
3//! A classical NP-complete single-machine scheduling problem (SS5 from
4//! Garey & Johnson, 1979) asking whether there exists a job order whose
5//! total weighted tardiness is at most a given bound.
6//! Corresponds to scheduling notation `1 || sum w_j T_j`.
7
8use crate::registry::{CreateSpec, ProblemSchemaEntry};
9use crate::traits::Problem;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "SequencingToMinimizeWeightedTardiness",
15        display_name: "Sequencing to Minimize Weighted Tardiness",
16        aliases: &[],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Schedule jobs on one machine so total weighted tardiness is at most K",
21        fields: SequencingToMinimizeWeightedTardinessCreateSpec::FIELDS,
22    }
23}
24
25/// Sequencing to Minimize Weighted Tardiness.
26///
27/// Given jobs with processing times `l_j`, weights `w_j`, deadlines `d_j`,
28/// and a bound `K`, determine whether there exists a permutation schedule on a
29/// single machine whose total weighted tardiness
30/// `sum_j w_j * max(0, C_j - d_j)` is at most `K`, where `C_j` is the
31/// completion time of job `j`.
32///
33/// # Representation
34///
35/// Configurations use Lehmer code to encode permutations of the jobs.
36/// Decoding yields the job order processed by the single machine.
37///
38/// # Example
39///
40/// ```
41/// use problemreductions::models::misc::SequencingToMinimizeWeightedTardiness;
42/// use problemreductions::{BruteForce, Problem};
43///
44/// let problem = SequencingToMinimizeWeightedTardiness::new(
45///     vec![3, 4, 2, 5, 3],
46///     vec![2, 3, 1, 4, 2],
47///     vec![5, 8, 4, 15, 10],
48///     13,
49/// );
50///
51/// let solver = BruteForce::new();
52/// assert!(solver.solve(&problem).unwrap().is_some());
53/// ```
54#[derive(Debug, Clone, Serialize, Deserialize)]
55pub struct SequencingToMinimizeWeightedTardiness {
56    lengths: Vec<i64>,
57    weights: Vec<i64>,
58    deadlines: Vec<i64>,
59    bound: i64,
60}
61
62#[derive(Debug, Deserialize, crate::CreateSpec)]
63struct SequencingToMinimizeWeightedTardinessCreateSpec {
64    /// Processing times for each job.
65    lengths: Vec<i64>,
66    /// Tardiness weights for each job.
67    weights: Vec<i64>,
68    /// Deadlines for each job.
69    deadlines: Vec<i64>,
70    /// Upper bound on total weighted tardiness.
71    bound: i64,
72}
73impl TryFrom<SequencingToMinimizeWeightedTardinessCreateSpec>
74    for SequencingToMinimizeWeightedTardiness
75{
76    type Error = crate::registry::ConstructionError;
77    fn try_from(
78        spec: SequencingToMinimizeWeightedTardinessCreateSpec,
79    ) -> Result<Self, Self::Error> {
80        if spec.lengths.len() != spec.weights.len() {
81            return Err("weights length must equal lengths length"
82                .to_string()
83                .into());
84        }
85        if spec.lengths.len() != spec.deadlines.len() {
86            return Err("deadlines length must equal lengths length"
87                .to_string()
88                .into());
89        }
90        Ok(Self::new(
91            spec.lengths,
92            spec.weights,
93            spec.deadlines,
94            spec.bound,
95        ))
96    }
97}
98
99impl SequencingToMinimizeWeightedTardiness {
100    /// Create a new weighted tardiness scheduling instance.
101    ///
102    /// # Panics
103    ///
104    /// Panics if the input vectors do not have the same length.
105    pub fn new(lengths: Vec<i64>, weights: Vec<i64>, deadlines: Vec<i64>, bound: i64) -> Self {
106        assert_eq!(
107            lengths.len(),
108            weights.len(),
109            "weights length must equal lengths length"
110        );
111        assert_eq!(
112            lengths.len(),
113            deadlines.len(),
114            "deadlines length must equal lengths length"
115        );
116        assert!(
117            lengths.iter().all(|&length| length >= 0),
118            "task lengths must be nonnegative"
119        );
120        assert!(
121            weights.iter().all(|&weight| weight >= 0),
122            "task weights must be nonnegative"
123        );
124        assert!(
125            deadlines.iter().all(|&deadline| deadline >= 0),
126            "deadlines must be nonnegative"
127        );
128        assert!(bound >= 0, "bound must be nonnegative");
129        Self {
130            lengths,
131            weights,
132            deadlines,
133            bound,
134        }
135    }
136
137    /// Returns the job lengths.
138    pub fn lengths(&self) -> &[i64] {
139        &self.lengths
140    }
141
142    /// Returns the tardiness weights.
143    pub fn weights(&self) -> &[i64] {
144        &self.weights
145    }
146
147    /// Returns the deadlines.
148    pub fn deadlines(&self) -> &[i64] {
149        &self.deadlines
150    }
151
152    /// Returns the weighted tardiness bound.
153    pub fn bound(&self) -> i64 {
154        self.bound
155    }
156
157    /// Returns the number of jobs.
158    pub fn num_tasks(&self) -> usize {
159        self.lengths.len()
160    }
161
162    fn decode_schedule(&self, config: &[usize]) -> Option<Vec<usize>> {
163        super::decode_permutation(config, self.num_tasks())
164    }
165
166    fn schedule_weighted_tardiness(
167        &self,
168        schedule: &[usize],
169    ) -> Result<i64, crate::traits::EvaluationError> {
170        let mut completion_time = 0i64;
171        let mut total = 0i64;
172        for &job in schedule {
173            completion_time = completion_time
174                .checked_add(self.lengths[job])
175                .ok_or_else(|| {
176                    crate::traits::EvaluationError::IntegerOverflow(
177                        "summing weighted-tardiness completion times".to_string(),
178                    )
179                })?;
180            let tardiness = completion_time
181                .checked_sub(self.deadlines[job])
182                .ok_or_else(|| {
183                    crate::traits::EvaluationError::IntegerOverflow(
184                        "computing job tardiness".to_string(),
185                    )
186                })?
187                .max(0);
188            let weighted_tardiness = tardiness.checked_mul(self.weights[job]).ok_or_else(|| {
189                crate::traits::EvaluationError::IntegerOverflow(
190                    "multiplying tardiness by job weight".to_string(),
191                )
192            })?;
193            total = total.checked_add(weighted_tardiness).ok_or_else(|| {
194                crate::traits::EvaluationError::IntegerOverflow(
195                    "summing weighted job tardiness".to_string(),
196                )
197            })?;
198        }
199        Ok(total)
200    }
201
202    /// Compute the total weighted tardiness of a Lehmer-encoded schedule.
203    ///
204    /// Returns `Ok(None)` if the configuration is not a valid Lehmer code.
205    pub fn total_weighted_tardiness(
206        &self,
207        config: &[usize],
208    ) -> Result<Option<i64>, crate::traits::EvaluationError> {
209        let Some(schedule) = self.decode_schedule(config) else {
210            return Ok(None);
211        };
212        Ok(Some(self.schedule_weighted_tardiness(&schedule)?))
213    }
214}
215
216impl Problem for SequencingToMinimizeWeightedTardiness {
217    const NAME: &'static str = "SequencingToMinimizeWeightedTardiness";
218    type Solution = Vec<usize>;
219    type Value = crate::types::Or;
220
221    crate::problem_parameters![("num_tasks", num_tasks),];
222
223    fn variant() -> Vec<(&'static str, &'static str)> {
224        crate::variant_params![]
225    }
226
227    fn evaluate(
228        &self,
229        config: &Self::Solution,
230    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
231        let n = self.num_tasks();
232        if config.len() != n {
233            return Err(crate::traits::EvaluationError::InvalidConfiguration(
234                "schedule length does not match the tasks".into(),
235            ));
236        }
237        if config.iter().any(|&task| task >= n) {
238            return Err(crate::traits::EvaluationError::InvalidConfiguration(
239                "schedule contains an out-of-range task".into(),
240            ));
241        }
242        Ok({
243            crate::types::Or({
244                self.total_weighted_tardiness(config)?
245                    .is_some_and(|total| total <= self.bound)
246            })
247        })
248    }
249}
250
251impl crate::solvers::BruteForceProblem for SequencingToMinimizeWeightedTardiness {
252    fn dimensions(&self) -> Vec<usize> {
253        super::lehmer_dims(self.num_tasks())
254    }
255}
256
257crate::declare_variants! {
258    default SequencingToMinimizeWeightedTardiness => "factorial(num_tasks)" create SequencingToMinimizeWeightedTardinessCreateSpec,
259}
260
261crate::register_brute_force! {
262    SequencingToMinimizeWeightedTardiness decode |problem: &SequencingToMinimizeWeightedTardiness, indices: Vec<usize>| super::decode_lehmer(&indices, problem.num_tasks()).expect("enumerated Lehmer digits are valid"),
263}
264
265#[cfg(feature = "example-db")]
266pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
267    vec![crate::example_db::specs::ModelExampleSpec {
268        id: "sequencing_to_minimize_weighted_tardiness",
269        instance: Box::new(SequencingToMinimizeWeightedTardiness::new(
270            vec![3, 4, 2, 5, 3],
271            vec![2, 3, 1, 4, 2],
272            vec![5, 8, 4, 15, 10],
273            13,
274        )),
275        optimal_config: serde_json::json!(vec![0, 1, 4, 3, 2]),
276        optimal_value: serde_json::json!(true),
277    }]
278}
279
280#[cfg(test)]
281#[path = "../../unit_tests/models/misc/sequencing_to_minimize_weighted_tardiness.rs"]
282mod tests;
problemreductions/models/misc/sequencing_to_minimize_weighted_tardiness.rs

problemreductions/models/misc/
sequencing_to_minimize_weighted_tardiness.rs
