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    /// Smallest h >= 1 bounding every processing time in magnitude strictly by 2^h.
122    pub fn max_processing_time_bits(&self) -> u64 {
123        crate::types::max_numeric_magnitude_bits(self.lengths.iter().copied())
124    }
125
126    /// Returns the number of tasks.
127    pub fn num_tasks(&self) -> usize {
128        self.lengths.len()
129    }
130
131    /// Returns the processing times.
132    pub fn lengths(&self) -> &[i64] {
133        &self.lengths
134    }
135
136    /// Returns the task weights.
137    pub fn weights(&self) -> &[i64] {
138        &self.weights
139    }
140
141    /// Returns the task deadlines.
142    pub fn deadlines(&self) -> &[i64] {
143        &self.deadlines
144    }
145
146    fn tardy_task_weight(
147        &self,
148        schedule: &[usize],
149    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
150        let mut elapsed: i64 = 0;
151        let mut total: i64 = 0;
152        for &task in schedule {
153            elapsed = elapsed.checked_add(self.lengths[task]).ok_or_else(|| {
154                crate::traits::EvaluationError::IntegerOverflow(
155                    "summing tardiness sequencing processing times".to_string(),
156                )
157            })?;
158            if elapsed > self.deadlines[task] {
159                total = total.checked_add(self.weights[task]).ok_or_else(|| {
160                    crate::traits::EvaluationError::IntegerOverflow(
161                        "summing tardy task weights".to_string(),
162                    )
163                })?;
164            }
165        }
166        Ok(Min(Some(total)))
167    }
168}
169
170impl TryFrom<SequencingToMinimizeTardyTaskWeightSerde> for SequencingToMinimizeTardyTaskWeight {
171    type Error = crate::registry::ConstructionError;
172
173    fn try_from(value: SequencingToMinimizeTardyTaskWeightSerde) -> Result<Self, Self::Error> {
174        Self::validate(&value.lengths, &value.weights, &value.deadlines)?;
175        Ok(Self {
176            lengths: value.lengths,
177            weights: value.weights,
178            deadlines: value.deadlines,
179        })
180    }
181}
182
183impl<'de> Deserialize<'de> for SequencingToMinimizeTardyTaskWeight {
184    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
185    where
186        D: serde::Deserializer<'de>,
187    {
188        let value = SequencingToMinimizeTardyTaskWeightSerde::deserialize(deserializer)?;
189        Self::try_from(value).map_err(serde::de::Error::custom)
190    }
191}
192
193impl Problem for SequencingToMinimizeTardyTaskWeight {
194    const NAME: &'static str = "SequencingToMinimizeTardyTaskWeight";
195    type Solution = Vec<usize>;
196    type Value = Min<i64>;
197
198    crate::problem_parameters![
199        ("max_processing_time_bits", max_processing_time_bits),
200        ("num_tasks", num_tasks),
201    ];
202
203    fn variant() -> Vec<(&'static str, &'static str)> {
204        crate::variant_params![]
205    }
206
207    fn evaluate(
208        &self,
209        config: &Self::Solution,
210    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
211        let n = self.num_tasks();
212        if config.len() != n {
213            return Err(crate::traits::EvaluationError::InvalidConfiguration(
214                "schedule length does not match the tasks".into(),
215            ));
216        }
217        if config.iter().any(|&task| task >= n) {
218            return Err(crate::traits::EvaluationError::InvalidConfiguration(
219                "schedule contains an out-of-range task".into(),
220            ));
221        }
222        Ok({
223            let Some(schedule) = super::decode_permutation(config, n) else {
224                return Ok(Min(None));
225            };
226            self.tardy_task_weight(&schedule)?
227        })
228    }
229}
230
231impl crate::solvers::BruteForceProblem for SequencingToMinimizeTardyTaskWeight {
232    fn dimensions(&self) -> Vec<usize> {
233        let n = self.num_tasks();
234        vec![n; n]
235    }
236}
237
238crate::declare_variants! {
239    default SequencingToMinimizeTardyTaskWeight => "factorial(num_tasks)" create SequencingToMinimizeTardyTaskWeightCreateSpec,
240}
241
242crate::register_brute_force! {
243    SequencingToMinimizeTardyTaskWeight,
244}
245
246#[cfg(feature = "example-db")]
247pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
248    vec![crate::example_db::specs::ModelExampleSpec {
249        id: "sequencing_to_minimize_tardy_task_weight",
250        // 5 tasks, lengths [3,2,4,1,2], weights [5,3,7,2,4], deadlines [6,4,10,2,8]
251        // Optimal schedule: [t4,t1,t5,t3,t2] = config [3,0,4,2,1]
252        // Start times: t4 starts 0, completes 1 (tardy: C=1 <= d=2, ok)
253        // t1 starts 1, completes 4 (tardy: C=4 <= d=6, ok)
254        // t5 starts 4, completes 6 (tardy: C=6 <= d=8, ok)
255        // t3 starts 6, completes 10 (tardy: C=10 <= d=10, ok)
256        // t2 starts 10, completes 12 (tardy: C=12 > d=4, tardy weight 3)
257        // Total tardy weight = 3
258        instance: Box::new(SequencingToMinimizeTardyTaskWeight::new(
259            vec![3, 2, 4, 1, 2],
260            vec![5, 3, 7, 2, 4],
261            vec![6, 4, 10, 2, 8],
262        )),
263        optimal_config: serde_json::json!(vec![3, 0, 4, 2, 1]),
264        optimal_value: serde_json::json!(3),
265    }]
266}
267
268#[cfg(test)]
269#[path = "../../unit_tests/models/misc/sequencing_to_minimize_tardy_task_weight.rs"]
270mod tests;
271
272crate::decision_problem_meta!(
273    SequencingToMinimizeTardyTaskWeight,
274    "DecisionSequencingToMinimizeTardyTaskWeight"
275);
276crate::register_decision_variant!(
277    SequencingToMinimizeTardyTaskWeight, "DecisionSequencingToMinimizeTardyTaskWeight", "factorial(num_tasks)", &[],
278    "Does a feasible solution have objective value <= the bound?",
279    category: crate::registry::ProblemCategory::Misc,
280    dims: [],
281    fields: [
282crate::registry::FieldInfo { name: "lengths", type_name: "Vec<i64>", description: "Lengths" },
283crate::registry::FieldInfo { name: "weights", type_name: "Option<Vec<i64>>", description: "Weights" },
284crate::registry::FieldInfo { name: "deadlines", type_name: "Vec<i64>", description: "Deadlines" },
285crate::registry::FieldInfo { name: "bound", type_name: "i64", description: "Accept objective values <= this bound" },
286],
287    decode: |_, indices: Vec<usize>| indices
288);
289
290#[cfg(feature = "example-db")]
291pub(crate) fn decision_canonical_rule_example_specs(
292) -> Vec<crate::example_db::specs::RuleExampleSpec> {
293    vec![crate::example_db::specs::RuleExampleSpec {
294        id: "decision_sequencing_to_minimize_tardy_task_weight_to_sequencing_to_minimize_tardy_task_weight",
295        build: || {
296            let source = crate::models::decision::Decision::new(SequencingToMinimizeTardyTaskWeight::new(
297            vec![3, 2, 4, 1, 2],
298            vec![5, 3, 7, 2, 4],
299            vec![6, 4, 10, 2, 8],
300        ), 3);
301            let witness = serde_json::json!(vec![3, 0, 4, 2, 1]);
302            crate::example_db::specs::rule_example_with_witness::<_, SequencingToMinimizeTardyTaskWeight>(
303                source,
304                crate::export::SolutionPair { source_config: witness.clone(), target_config: witness },
305            )
306        },
307    }]
308}
problemreductions/models/misc/sequencing_to_minimize_tardy_task_weight.rs

problemreductions/models/misc/
sequencing_to_minimize_tardy_task_weight.rs
