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)]
55#[serde(try_from = "SequencingToMinimizeWeightedTardinessCreateSpec")]
56pub struct SequencingToMinimizeWeightedTardiness {
57    lengths: Vec<i64>,
58    weights: Vec<i64>,
59    deadlines: Vec<i64>,
60    bound: i64,
61}
62
63#[derive(Debug, Deserialize, crate::CreateSpec)]
64struct SequencingToMinimizeWeightedTardinessCreateSpec {
65    /// Processing times for each job.
66    lengths: Vec<i64>,
67    /// Tardiness weights for each job.
68    weights: Vec<i64>,
69    /// Deadlines for each job.
70    deadlines: Vec<i64>,
71    /// Upper bound on total weighted tardiness.
72    bound: i64,
73}
74impl TryFrom<SequencingToMinimizeWeightedTardinessCreateSpec>
75    for SequencingToMinimizeWeightedTardiness
76{
77    type Error = crate::registry::ConstructionError;
78    fn try_from(
79        spec: SequencingToMinimizeWeightedTardinessCreateSpec,
80    ) -> Result<Self, Self::Error> {
81        Self::try_new(spec.lengths, spec.weights, spec.deadlines, spec.bound)
82    }
83}
84
85impl SequencingToMinimizeWeightedTardiness {
86    /// Create a new weighted tardiness scheduling instance.
87    ///
88    /// # Panics
89    ///
90    /// Panics if the input vectors do not have the same length.
91    pub fn new(lengths: Vec<i64>, weights: Vec<i64>, deadlines: Vec<i64>, bound: i64) -> Self {
92        Self::try_new(lengths, weights, deadlines, bound).unwrap_or_else(|error| panic!("{error}"))
93    }
94
95    fn try_new(
96        lengths: Vec<i64>,
97        weights: Vec<i64>,
98        deadlines: Vec<i64>,
99        bound: i64,
100    ) -> Result<Self, crate::registry::ConstructionError> {
101        if lengths.len() != weights.len() {
102            return Err("weights length must equal lengths length".into());
103        }
104        if lengths.len() != deadlines.len() {
105            return Err("deadlines length must equal lengths length".into());
106        }
107        if lengths.iter().any(|&length| length < 0) {
108            return Err("task lengths must be nonnegative".into());
109        }
110        if weights.iter().any(|&weight| weight < 0) {
111            return Err("task weights must be nonnegative".into());
112        }
113        if deadlines.iter().any(|&deadline| deadline < 0) {
114            return Err("deadlines must be nonnegative".into());
115        }
116        if bound < 0 {
117            return Err("bound must be nonnegative".into());
118        }
119        Ok(Self {
120            lengths,
121            weights,
122            deadlines,
123            bound,
124        })
125    }
126
127    /// Returns the job lengths.
128    pub fn lengths(&self) -> &[i64] {
129        &self.lengths
130    }
131
132    /// Returns the tardiness weights.
133    pub fn weights(&self) -> &[i64] {
134        &self.weights
135    }
136
137    /// Returns the deadlines.
138    pub fn deadlines(&self) -> &[i64] {
139        &self.deadlines
140    }
141
142    /// Returns the weighted tardiness bound.
143    pub fn bound(&self) -> i64 {
144        self.bound
145    }
146
147    /// Smallest h >= 1 with all lengths, weights, deadlines, and the cost bound below 2^h.
148    pub fn max_numeric_magnitude_bits(&self) -> u64 {
149        crate::types::max_numeric_magnitude_bits(
150            self.lengths
151                .iter()
152                .chain(&self.weights)
153                .chain(&self.deadlines)
154                .copied()
155                .chain(std::iter::once(self.bound)),
156        )
157    }
158
159    /// Returns the number of jobs.
160    pub fn num_tasks(&self) -> usize {
161        self.lengths.len()
162    }
163
164    fn decode_schedule(&self, config: &[usize]) -> Option<Vec<usize>> {
165        super::decode_permutation(config, self.num_tasks())
166    }
167
168    fn schedule_weighted_tardiness(
169        &self,
170        schedule: &[usize],
171    ) -> Result<i64, crate::traits::EvaluationError> {
172        let mut completion_time = 0i64;
173        let mut total = 0i64;
174        for &job in schedule {
175            completion_time = completion_time
176                .checked_add(self.lengths[job])
177                .ok_or_else(|| {
178                    crate::traits::EvaluationError::IntegerOverflow(
179                        "summing weighted-tardiness completion times".to_string(),
180                    )
181                })?;
182            let tardiness = completion_time
183                .checked_sub(self.deadlines[job])
184                .ok_or_else(|| {
185                    crate::traits::EvaluationError::IntegerOverflow(
186                        "computing job tardiness".to_string(),
187                    )
188                })?
189                .max(0);
190            let weighted_tardiness = tardiness.checked_mul(self.weights[job]).ok_or_else(|| {
191                crate::traits::EvaluationError::IntegerOverflow(
192                    "multiplying tardiness by job weight".to_string(),
193                )
194            })?;
195            total = total.checked_add(weighted_tardiness).ok_or_else(|| {
196                crate::traits::EvaluationError::IntegerOverflow(
197                    "summing weighted job tardiness".to_string(),
198                )
199            })?;
200        }
201        Ok(total)
202    }
203
204    /// Compute the total weighted tardiness of a Lehmer-encoded schedule.
205    ///
206    /// Returns `Ok(None)` if the configuration is not a valid Lehmer code.
207    pub fn total_weighted_tardiness(
208        &self,
209        config: &[usize],
210    ) -> Result<Option<i64>, crate::traits::EvaluationError> {
211        let Some(schedule) = self.decode_schedule(config) else {
212            return Ok(None);
213        };
214        Ok(Some(self.schedule_weighted_tardiness(&schedule)?))
215    }
216}
217
218impl Problem for SequencingToMinimizeWeightedTardiness {
219    const NAME: &'static str = "SequencingToMinimizeWeightedTardiness";
220    type Solution = Vec<usize>;
221    type Value = crate::types::Or;
222
223    crate::problem_parameters![
224        ("max_numeric_magnitude_bits", max_numeric_magnitude_bits),
225        ("num_tasks", num_tasks),
226    ];
227
228    fn variant() -> Vec<(&'static str, &'static str)> {
229        crate::variant_params![]
230    }
231
232    fn evaluate(
233        &self,
234        config: &Self::Solution,
235    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
236        let n = self.num_tasks();
237        if config.len() != n {
238            return Err(crate::traits::EvaluationError::InvalidConfiguration(
239                "schedule length does not match the tasks".into(),
240            ));
241        }
242        if config.iter().any(|&task| task >= n) {
243            return Err(crate::traits::EvaluationError::InvalidConfiguration(
244                "schedule contains an out-of-range task".into(),
245            ));
246        }
247        Ok({
248            crate::types::Or({
249                self.total_weighted_tardiness(config)?
250                    .is_some_and(|total| total <= self.bound)
251            })
252        })
253    }
254}
255
256impl crate::solvers::BruteForceProblem for SequencingToMinimizeWeightedTardiness {
257    fn dimensions(&self) -> Vec<usize> {
258        super::lehmer_dims(self.num_tasks())
259    }
260}
261
262crate::declare_variants! {
263    default SequencingToMinimizeWeightedTardiness => "factorial(num_tasks)" create SequencingToMinimizeWeightedTardinessCreateSpec,
264}
265
266crate::register_brute_force! {
267    SequencingToMinimizeWeightedTardiness decode |problem: &SequencingToMinimizeWeightedTardiness, indices: Vec<usize>| super::decode_lehmer(&indices, problem.num_tasks()).expect("enumerated Lehmer digits are valid"),
268}
269
270#[cfg(feature = "example-db")]
271pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
272    vec![crate::example_db::specs::ModelExampleSpec {
273        id: "sequencing_to_minimize_weighted_tardiness",
274        instance: Box::new(SequencingToMinimizeWeightedTardiness::new(
275            vec![3, 4, 2, 5, 3],
276            vec![2, 3, 1, 4, 2],
277            vec![5, 8, 4, 15, 10],
278            13,
279        )),
280        optimal_config: serde_json::json!(vec![0, 1, 4, 3, 2]),
281        optimal_value: serde_json::json!(true),
282    }]
283}
284
285#[cfg(test)]
286#[path = "../../unit_tests/models/misc/sequencing_to_minimize_weighted_tardiness.rs"]
287mod tests;
problemreductions/models/misc/sequencing_to_minimize_weighted_tardiness.rs

problemreductions/models/misc/
sequencing_to_minimize_weighted_tardiness.rs
