problemreductions/models/misc/
minimum_tardiness_sequencing.rs

1//! Minimum Tardiness Sequencing problem implementation.
2//!
3//! A classical NP-complete single-machine scheduling problem (SS2 from
4//! Garey & Johnson, 1979) where tasks with precedence constraints
5//! and deadlines must be scheduled to minimize the number of tardy tasks.
6//!
7//! Variants:
8//! - `MinimumTardinessSequencing<One>` — unit-length tasks (`1|prec, pj=1|∑Uj`)
9//! - `MinimumTardinessSequencing<i32>` — arbitrary-length tasks (`1|prec|∑Uj`)
10
11use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
12use crate::traits::Problem;
13use crate::types::{Min, One, WeightElement};
14use serde::{Deserialize, Serialize};
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "MinimumTardinessSequencing",
19        display_name: "Minimum Tardiness Sequencing",
20        aliases: &[],
21        dimensions: &[VariantDimension::new("weight", "One", &["One", "i32"])],
22        module_path: module_path!(),
23        description: "Schedule tasks with precedence constraints and deadlines to minimize the number of tardy tasks",
24        fields: &[
25            FieldInfo { name: "lengths", type_name: "Vec<W>", description: "Processing time l(t) for each task" },
26            FieldInfo { name: "deadlines", type_name: "Vec<usize>", description: "Deadline d(t) for each task" },
27            FieldInfo { name: "precedences", type_name: "Vec<(usize, usize)>", description: "Precedence pairs (predecessor, successor)" },
28        ],
29    }
30}
31
32/// Minimum Tardiness Sequencing problem.
33///
34/// Given a set T of tasks, each with a processing time l(t) and a deadline d(t),
35/// and a partial order (precedence constraints) on T, find a schedule
36/// that is a valid permutation respecting precedence constraints
37/// and minimizes the number of tardy tasks.
38///
39/// # Type Parameters
40///
41/// * `W` - The weight/length type. `One` for unit-length tasks, `i32` for arbitrary.
42///
43/// # Example
44///
45/// ```
46/// use problemreductions::models::misc::MinimumTardinessSequencing;
47/// use problemreductions::types::One;
48/// use problemreductions::{Problem, Solver, BruteForce};
49///
50/// // Unit-length: 3 tasks, task 0 must precede task 2
51/// let problem = MinimumTardinessSequencing::<One>::new(
52///     3,
53///     vec![2, 3, 1],
54///     vec![(0, 2)],
55/// );
56/// let solver = BruteForce::new();
57/// let solution = solver.find_witness(&problem);
58/// assert!(solution.is_some());
59/// ```
60#[derive(Debug, Clone, Serialize, Deserialize)]
61pub struct MinimumTardinessSequencing<W> {
62    lengths: Vec<W>,
63    deadlines: Vec<usize>,
64    precedences: Vec<(usize, usize)>,
65}
66
67impl MinimumTardinessSequencing<One> {
68    /// Create a new unit-length MinimumTardinessSequencing instance.
69    ///
70    /// # Panics
71    ///
72    /// Panics if `deadlines.len() != num_tasks` or if any task index in `precedences`
73    /// is out of range.
74    pub fn new(num_tasks: usize, deadlines: Vec<usize>, precedences: Vec<(usize, usize)>) -> Self {
75        assert_eq!(
76            deadlines.len(),
77            num_tasks,
78            "deadlines length must equal num_tasks"
79        );
80        validate_precedences(num_tasks, &precedences);
81        Self {
82            lengths: vec![One; num_tasks],
83            deadlines,
84            precedences,
85        }
86    }
87}
88
89impl MinimumTardinessSequencing<i32> {
90    /// Create a new arbitrary-length MinimumTardinessSequencing instance.
91    ///
92    /// # Panics
93    ///
94    /// Panics if `lengths.len() != deadlines.len()`, if any length is 0,
95    /// or if any task index in `precedences` is out of range.
96    pub fn with_lengths(
97        lengths: Vec<i32>,
98        deadlines: Vec<usize>,
99        precedences: Vec<(usize, usize)>,
100    ) -> Self {
101        assert_eq!(
102            lengths.len(),
103            deadlines.len(),
104            "lengths and deadlines must have the same length"
105        );
106        assert!(
107            lengths.iter().all(|&l| l > 0),
108            "all task lengths must be positive"
109        );
110        let num_tasks = lengths.len();
111        validate_precedences(num_tasks, &precedences);
112        Self {
113            lengths,
114            deadlines,
115            precedences,
116        }
117    }
118}
119
120fn validate_precedences(num_tasks: usize, precedences: &[(usize, usize)]) {
121    for &(pred, succ) in precedences {
122        assert!(
123            pred < num_tasks,
124            "predecessor index {} out of range (num_tasks = {})",
125            pred,
126            num_tasks
127        );
128        assert!(
129            succ < num_tasks,
130            "successor index {} out of range (num_tasks = {})",
131            succ,
132            num_tasks
133        );
134    }
135}
136
137impl<W: WeightElement> MinimumTardinessSequencing<W> {
138    /// Returns the number of tasks.
139    pub fn num_tasks(&self) -> usize {
140        self.deadlines.len()
141    }
142
143    /// Returns the task lengths.
144    pub fn lengths(&self) -> &[W] {
145        &self.lengths
146    }
147
148    /// Returns the deadlines.
149    pub fn deadlines(&self) -> &[usize] {
150        &self.deadlines
151    }
152
153    /// Returns the precedence constraints.
154    pub fn precedences(&self) -> &[(usize, usize)] {
155        &self.precedences
156    }
157
158    /// Returns the number of precedence constraints.
159    pub fn num_precedences(&self) -> usize {
160        self.precedences.len()
161    }
162
163    /// Decode and validate a schedule, returning the inverse permutation (sigma).
164    /// Returns None if the config is invalid or violates precedences.
165    fn decode_and_validate(&self, config: &[usize]) -> Option<Vec<usize>> {
166        let n = self.num_tasks();
167        let schedule = super::decode_lehmer(config, n)?;
168
169        let mut sigma = vec![0usize; n];
170        for (pos, &task) in schedule.iter().enumerate() {
171            sigma[task] = pos;
172        }
173
174        for &(pred, succ) in &self.precedences {
175            if sigma[pred] >= sigma[succ] {
176                return None;
177            }
178        }
179
180        Some(sigma)
181    }
182}
183
184impl Problem for MinimumTardinessSequencing<One> {
185    const NAME: &'static str = "MinimumTardinessSequencing";
186    type Value = Min<usize>;
187
188    fn variant() -> Vec<(&'static str, &'static str)> {
189        crate::variant_params![One]
190    }
191
192    fn dims(&self) -> Vec<usize> {
193        super::lehmer_dims(self.num_tasks())
194    }
195
196    fn evaluate(&self, config: &[usize]) -> Min<usize> {
197        let n = self.num_tasks();
198        let Some(sigma) = self.decode_and_validate(config) else {
199            return Min(None);
200        };
201
202        // Unit length: completion time at position p is p + 1
203        let tardy_count = (0..n).filter(|&t| sigma[t] + 1 > self.deadlines[t]).count();
204
205        Min(Some(tardy_count))
206    }
207}
208
209impl Problem for MinimumTardinessSequencing<i32> {
210    const NAME: &'static str = "MinimumTardinessSequencing";
211    type Value = Min<usize>;
212
213    fn variant() -> Vec<(&'static str, &'static str)> {
214        crate::variant_params![i32]
215    }
216
217    fn dims(&self) -> Vec<usize> {
218        super::lehmer_dims(self.num_tasks())
219    }
220
221    fn evaluate(&self, config: &[usize]) -> Min<usize> {
222        let n = self.num_tasks();
223        let Some(sigma) = self.decode_and_validate(config) else {
224            return Min(None);
225        };
226
227        // Build schedule order from sigma (inverse permutation)
228        let mut schedule = vec![0usize; n];
229        for (task, &pos) in sigma.iter().enumerate() {
230            schedule[pos] = task;
231        }
232
233        // Compute completion times using actual lengths
234        let mut completion = vec![0usize; n];
235        let mut cumulative = 0usize;
236        for &task in &schedule {
237            cumulative += self.lengths[task] as usize;
238            completion[task] = cumulative;
239        }
240
241        let tardy_count = (0..n)
242            .filter(|&t| completion[t] > self.deadlines[t])
243            .count();
244
245        Min(Some(tardy_count))
246    }
247}
248
249crate::declare_variants! {
250    default MinimumTardinessSequencing<One> => "2^num_tasks",
251    MinimumTardinessSequencing<i32> => "2^num_tasks",
252}
253
254#[cfg(feature = "example-db")]
255pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
256    vec![
257        // Unit-length variant
258        crate::example_db::specs::ModelExampleSpec {
259            id: "minimum_tardiness_sequencing",
260            instance: Box::new(MinimumTardinessSequencing::<One>::new(
261                4,
262                vec![2, 3, 1, 4],
263                vec![(0, 2)],
264            )),
265            optimal_config: vec![0, 0, 0, 0],
266            optimal_value: serde_json::json!(1),
267        },
268        // Arbitrary-length variant
269        crate::example_db::specs::ModelExampleSpec {
270            id: "minimum_tardiness_sequencing_weighted",
271            // 5 tasks, lengths [3,2,2,1,2], deadlines [4,3,8,3,6], prec (0→2, 1→3)
272            // Optimal schedule: t0,t4,t2,t1,t3 → 2 tardy
273            // Lehmer [0,3,1,0,0]: avail=[0,1,2,3,4] pick 0→0; [1,2,3,4] pick 3→4;
274            //   [1,2,3] pick 1→2; [1,3] pick 0→1; [3] pick 0→3
275            instance: Box::new(MinimumTardinessSequencing::<i32>::with_lengths(
276                vec![3, 2, 2, 1, 2],
277                vec![4, 3, 8, 3, 6],
278                vec![(0, 2), (1, 3)],
279            )),
280            optimal_config: vec![0, 3, 1, 0, 0],
281            optimal_value: serde_json::json!(2),
282        },
283    ]
284}
285
286#[cfg(test)]
287#[path = "../../unit_tests/models/misc/minimum_tardiness_sequencing.rs"]
288mod tests;
problemreductions/models/misc/minimum_tardiness_sequencing.rs

problemreductions/models/misc/
minimum_tardiness_sequencing.rs
