problemreductions/models/misc/
sequencing_to_minimize_tardy_task_weight.rs

1//! Sequencing to Minimize Tardy Task Weight problem implementation.
2//!
3//! A classical NP-hard single-machine scheduling problem (SS8 from
4//! Garey & Johnson, 1979) where tasks with processing times, weights,
5//! and deadlines must be scheduled to minimize the total weight of tardy tasks.
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use crate::types::Min;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "SequencingToMinimizeTardyTaskWeight",
15        display_name: "Sequencing to Minimize Tardy Task Weight",
16        aliases: &[],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Schedule tasks with lengths, weights, and deadlines to minimize total weight of tardy tasks",
21        fields: SequencingToMinimizeTardyTaskWeightCreateSpec::FIELDS,
22    }
23}
24
25/// Sequencing to Minimize Tardy Task Weight problem.
26///
27/// Given tasks with processing times `l(t)`, weights `w(t)`, and deadlines
28/// `d(t)`, find a single-machine schedule that minimizes `sum_{t tardy} w(t)`,
29/// where task `t` is tardy if its completion time `C(t) > d(t)`.
30///
31/// This is the weighted generalization of minimizing the number of tardy tasks
32/// (problem SS8 in Garey & Johnson, 1979, written $1 || sum w_j U_j$).
33///
34/// Configurations are direct permutation encodings with `dims() = [n; n]`:
35/// each position holds the index of the task scheduled at that position.
36/// A configuration is valid iff it is a permutation of `0..n`.
37#[derive(Debug, Clone, Serialize)]
38pub struct SequencingToMinimizeTardyTaskWeight {
39    lengths: Vec<i64>,
40    weights: Vec<i64>,
41    deadlines: Vec<i64>,
42}
43
44#[derive(Debug, Deserialize, crate::CreateSpec)]
45struct SequencingToMinimizeTardyTaskWeightCreateSpec {
46    /// Processing time for each task.
47    lengths: Vec<i64>,
48    /// Task weights; defaults to one per task.
49    weights: Option<Vec<i64>>,
50    /// Deadline for each task.
51    deadlines: Vec<i64>,
52}
53impl TryFrom<SequencingToMinimizeTardyTaskWeightCreateSpec>
54    for SequencingToMinimizeTardyTaskWeight
55{
56    type Error = crate::registry::ConstructionError;
57    fn try_from(spec: SequencingToMinimizeTardyTaskWeightCreateSpec) -> Result<Self, Self::Error> {
58        let count = spec.lengths.len();
59        if spec.deadlines.len() != count {
60            return Err("deadlines length must equal lengths length"
61                .to_string()
62                .into());
63        }
64        let weights = spec.weights.unwrap_or_else(|| vec![1; count]);
65        if weights.len() != count {
66            return Err("weights length must equal lengths length"
67                .to_string()
68                .into());
69        }
70        Ok(Self::new(spec.lengths, weights, spec.deadlines))
71    }
72}
73
74#[derive(Deserialize)]
75struct SequencingToMinimizeTardyTaskWeightSerde {
76    lengths: Vec<i64>,
77    weights: Vec<i64>,
78    deadlines: Vec<i64>,
79}
80
81impl SequencingToMinimizeTardyTaskWeight {
82    fn validate(
83        lengths: &[i64],
84        weights: &[i64],
85        deadlines: &[i64],
86    ) -> Result<(), crate::registry::ConstructionError> {
87        if lengths.len() != weights.len() {
88            return Err("lengths length must equal weights length"
89                .to_string()
90                .into());
91        }
92        if lengths.len() != deadlines.len() {
93            return Err("lengths length must equal deadlines length"
94                .to_string()
95                .into());
96        }
97        if lengths.contains(&0) {
98            return Err("task lengths must be positive".to_string().into());
99        }
100        if weights.contains(&0) {
101            return Err("task weights must be positive".to_string().into());
102        }
103        Ok(())
104    }
105
106    /// Create a new sequencing instance.
107    ///
108    /// # Panics
109    ///
110    /// Panics if `lengths`, `weights`, and `deadlines` are not all the same
111    /// length, or if any length or weight is zero.
112    pub fn new(lengths: Vec<i64>, weights: Vec<i64>, deadlines: Vec<i64>) -> Self {
113        Self::validate(&lengths, &weights, &deadlines).unwrap_or_else(|err| panic!("{err}"));
114        Self {
115            lengths,
116            weights,
117            deadlines,
118        }
119    }
120
121    /// Returns the number of tasks.
122    pub fn num_tasks(&self) -> usize {
123        self.lengths.len()
124    }
125
126    /// Returns the processing times.
127    pub fn lengths(&self) -> &[i64] {
128        &self.lengths
129    }
130
131    /// Returns the task weights.
132    pub fn weights(&self) -> &[i64] {
133        &self.weights
134    }
135
136    /// Returns the task deadlines.
137    pub fn deadlines(&self) -> &[i64] {
138        &self.deadlines
139    }
140
141    fn tardy_task_weight(
142        &self,
143        schedule: &[usize],
144    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
145        let mut elapsed: i64 = 0;
146        let mut total: i64 = 0;
147        for &task in schedule {
148            elapsed = elapsed.checked_add(self.lengths[task]).ok_or_else(|| {
149                crate::traits::EvaluationError::IntegerOverflow(
150                    "summing tardiness sequencing processing times".to_string(),
151                )
152            })?;
153            if elapsed > self.deadlines[task] {
154                total = total.checked_add(self.weights[task]).ok_or_else(|| {
155                    crate::traits::EvaluationError::IntegerOverflow(
156                        "summing tardy task weights".to_string(),
157                    )
158                })?;
159            }
160        }
161        Ok(Min(Some(total)))
162    }
163}
164
165impl TryFrom<SequencingToMinimizeTardyTaskWeightSerde> for SequencingToMinimizeTardyTaskWeight {
166    type Error = crate::registry::ConstructionError;
167
168    fn try_from(value: SequencingToMinimizeTardyTaskWeightSerde) -> Result<Self, Self::Error> {
169        Self::validate(&value.lengths, &value.weights, &value.deadlines)?;
170        Ok(Self {
171            lengths: value.lengths,
172            weights: value.weights,
173            deadlines: value.deadlines,
174        })
175    }
176}
177
178impl<'de> Deserialize<'de> for SequencingToMinimizeTardyTaskWeight {
179    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
180    where
181        D: serde::Deserializer<'de>,
182    {
183        let value = SequencingToMinimizeTardyTaskWeightSerde::deserialize(deserializer)?;
184        Self::try_from(value).map_err(serde::de::Error::custom)
185    }
186}
187
188impl Problem for SequencingToMinimizeTardyTaskWeight {
189    const NAME: &'static str = "SequencingToMinimizeTardyTaskWeight";
190    type Solution = Vec<usize>;
191    type Value = Min<i64>;
192
193    crate::problem_parameters![("num_tasks", num_tasks),];
194
195    fn variant() -> Vec<(&'static str, &'static str)> {
196        crate::variant_params![]
197    }
198
199    fn evaluate(
200        &self,
201        config: &Self::Solution,
202    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
203        let n = self.num_tasks();
204        if config.len() != n {
205            return Err(crate::traits::EvaluationError::InvalidConfiguration(
206                "schedule length does not match the tasks".into(),
207            ));
208        }
209        if config.iter().any(|&task| task >= n) {
210            return Err(crate::traits::EvaluationError::InvalidConfiguration(
211                "schedule contains an out-of-range task".into(),
212            ));
213        }
214        Ok({
215            let Some(schedule) = super::decode_permutation(config, n) else {
216                return Ok(Min(None));
217            };
218            self.tardy_task_weight(&schedule)?
219        })
220    }
221}
222
223impl crate::solvers::BruteForceProblem for SequencingToMinimizeTardyTaskWeight {
224    fn dimensions(&self) -> Vec<usize> {
225        let n = self.num_tasks();
226        vec![n; n]
227    }
228}
229
230crate::declare_variants! {
231    default SequencingToMinimizeTardyTaskWeight => "factorial(num_tasks)" create SequencingToMinimizeTardyTaskWeightCreateSpec,
232}
233
234crate::register_brute_force! {
235    SequencingToMinimizeTardyTaskWeight,
236}
237
238#[cfg(feature = "example-db")]
239pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
240    vec![crate::example_db::specs::ModelExampleSpec {
241        id: "sequencing_to_minimize_tardy_task_weight",
242        // 5 tasks, lengths [3,2,4,1,2], weights [5,3,7,2,4], deadlines [6,4,10,2,8]
243        // Optimal schedule: [t4,t1,t5,t3,t2] = config [3,0,4,2,1]
244        // Start times: t4 starts 0, completes 1 (tardy: C=1 <= d=2, ok)
245        // t1 starts 1, completes 4 (tardy: C=4 <= d=6, ok)
246        // t5 starts 4, completes 6 (tardy: C=6 <= d=8, ok)
247        // t3 starts 6, completes 10 (tardy: C=10 <= d=10, ok)
248        // t2 starts 10, completes 12 (tardy: C=12 > d=4, tardy weight 3)
249        // Total tardy weight = 3
250        instance: Box::new(SequencingToMinimizeTardyTaskWeight::new(
251            vec![3, 2, 4, 1, 2],
252            vec![5, 3, 7, 2, 4],
253            vec![6, 4, 10, 2, 8],
254        )),
255        optimal_config: serde_json::json!(vec![3, 0, 4, 2, 1]),
256        optimal_value: serde_json::json!(3),
257    }]
258}
259
260#[cfg(test)]
261#[path = "../../unit_tests/models/misc/sequencing_to_minimize_tardy_task_weight.rs"]
262mod tests;
problemreductions/models/misc/sequencing_to_minimize_tardy_task_weight.rs

problemreductions/models/misc/
sequencing_to_minimize_tardy_task_weight.rs
