problemreductions/models/misc/

minimum_tardiness_sequencing.rs

//! Minimum Tardiness Sequencing problem implementation.
//!
//! A classical NP-complete single-machine scheduling problem (SS2 from
//! Garey & Johnson, 1979) where tasks with precedence constraints
//! and deadlines must be scheduled to minimize the number of tardy tasks.
//!
//! Variants:
//! - `MinimumTardinessSequencing<One>` — unit-length tasks (`1|prec, pj=1|∑Uj`)
//! - `MinimumTardinessSequencing<i64>` — arbitrary-length tasks (`1|prec|∑Uj`)

use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
use crate::traits::Problem;
use crate::types::{Min, One, WeightElement};
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "MinimumTardinessSequencing",
        display_name: "Minimum Tardiness Sequencing",
        aliases: &[],
        dimensions: &[VariantDimension::new("weight", "One", &["One", "i64"])],
        category: crate::registry::ProblemCategory::Misc,
        module_path: module_path!(),
        description: "Schedule tasks with precedence constraints and deadlines to minimize the number of tardy tasks",
        fields: MinimumTardinessSequencingI64CreateSpec::FIELDS,
    }
}

/// Minimum Tardiness Sequencing problem.
///
/// Given a set T of tasks, each with a processing time l(t) and a deadline d(t),
/// and a partial order (precedence constraints) on T, find a schedule
/// that is a valid permutation respecting precedence constraints
/// and minimizes the number of tardy tasks.
///
/// # Type Parameters
///
/// * `W` - The weight/length type. `One` for unit-length tasks, `i64` for arbitrary.
///
/// # Example
///
/// ```
/// use problemreductions::models::misc::MinimumTardinessSequencing;
/// use problemreductions::types::One;
/// use problemreductions::{Problem, BruteForce};
///
/// // Unit-length: 3 tasks, task 0 must precede task 2
/// let problem = MinimumTardinessSequencing::<One>::new(
///     3,
///     vec![2, 3, 1],
///     vec![(0, 2)],
/// );
/// let solver = BruteForce::new();
/// let solution = solver.solve(&problem).unwrap();
/// assert!(solution.is_some());
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(try_from = "MinimumTardinessSequencingData<W>")]
#[serde(bound(
    deserialize = "W: Deserialize<'de>, Self: TryFrom<MinimumTardinessSequencingData<W>>, <Self as TryFrom<MinimumTardinessSequencingData<W>>>::Error: std::fmt::Display"
))]
pub struct MinimumTardinessSequencing<W> {
    lengths: Vec<W>,
    deadlines: Vec<i64>,
    precedences: Vec<(usize, usize)>,
}

#[derive(Deserialize)]
struct MinimumTardinessSequencingData<W> {
    lengths: Vec<W>,
    deadlines: Vec<i64>,
    precedences: Vec<(usize, usize)>,
}

impl TryFrom<MinimumTardinessSequencingData<One>> for MinimumTardinessSequencing<One> {
    type Error = crate::registry::ConstructionError;

    fn try_from(data: MinimumTardinessSequencingData<One>) -> Result<Self, Self::Error> {
        Self::try_new(data.lengths.len(), data.deadlines, data.precedences)
    }
}

impl TryFrom<MinimumTardinessSequencingData<i64>> for MinimumTardinessSequencing<i64> {
    type Error = crate::registry::ConstructionError;

    fn try_from(data: MinimumTardinessSequencingData<i64>) -> Result<Self, Self::Error> {
        Self::try_with_lengths(data.lengths, data.deadlines, data.precedences)
    }
}

#[derive(Debug, Deserialize, crate::CreateSpec)]
struct MinimumTardinessSequencingOneCreateSpec {
    deadlines: Vec<i64>,
    precedences: Option<Vec<(usize, usize)>>,
}
impl TryFrom<MinimumTardinessSequencingOneCreateSpec> for MinimumTardinessSequencing<One> {
    type Error = crate::registry::ConstructionError;
    fn try_from(spec: MinimumTardinessSequencingOneCreateSpec) -> Result<Self, Self::Error> {
        let num_tasks = spec.deadlines.len();
        let precedences = spec.precedences.unwrap_or_default();
        Self::try_new(num_tasks, spec.deadlines, precedences)
    }
}

#[derive(Debug, Deserialize, crate::CreateSpec)]
struct MinimumTardinessSequencingI64CreateSpec {
    lengths: Vec<i64>,
    deadlines: Vec<i64>,
    precedences: Option<Vec<(usize, usize)>>,
}
impl TryFrom<MinimumTardinessSequencingI64CreateSpec> for MinimumTardinessSequencing<i64> {
    type Error = crate::registry::ConstructionError;
    fn try_from(spec: MinimumTardinessSequencingI64CreateSpec) -> Result<Self, Self::Error> {
        Self::try_with_lengths(
            spec.lengths,
            spec.deadlines,
            spec.precedences.unwrap_or_default(),
        )
    }
}

impl MinimumTardinessSequencing<One> {
    /// Create a new unit-length MinimumTardinessSequencing instance.
    ///
    /// # Panics
    ///
    /// Panics if `deadlines.len() != num_tasks` or if any task index in `precedences`
    /// is out of range.
    pub fn new(num_tasks: usize, deadlines: Vec<i64>, precedences: Vec<(usize, usize)>) -> Self {
        Self::try_new(num_tasks, deadlines, precedences).unwrap_or_else(|error| panic!("{error}"))
    }

    fn try_new(
        num_tasks: usize,
        deadlines: Vec<i64>,
        precedences: Vec<(usize, usize)>,
    ) -> Result<Self, crate::registry::ConstructionError> {
        validate_task_data(num_tasks, &deadlines, &precedences)?;
        Ok(Self {
            lengths: vec![One; num_tasks],
            deadlines,
            precedences,
        })
    }
}

impl MinimumTardinessSequencing<i64> {
    /// Create a new arbitrary-length MinimumTardinessSequencing instance.
    ///
    /// # Panics
    ///
    /// Panics if `lengths.len() != deadlines.len()`, if any length is 0,
    /// or if any task index in `precedences` is out of range.
    pub fn with_lengths(
        lengths: Vec<i64>,
        deadlines: Vec<i64>,
        precedences: Vec<(usize, usize)>,
    ) -> Self {
        Self::try_with_lengths(lengths, deadlines, precedences)
            .unwrap_or_else(|error| panic!("{error}"))
    }

    fn try_with_lengths(
        lengths: Vec<i64>,
        deadlines: Vec<i64>,
        precedences: Vec<(usize, usize)>,
    ) -> Result<Self, crate::registry::ConstructionError> {
        validate_task_data(lengths.len(), &deadlines, &precedences)?;
        if lengths.iter().any(|&length| length <= 0) {
            return Err("all task lengths must be positive".into());
        }
        Ok(Self {
            lengths,
            deadlines,
            precedences,
        })
    }
}

fn validate_task_data(
    num_tasks: usize,
    deadlines: &[i64],
    precedences: &[(usize, usize)],
) -> Result<(), crate::registry::ConstructionError> {
    if deadlines.len() != num_tasks {
        return Err("deadlines length must equal num_tasks".into());
    }
    for &(pred, succ) in precedences {
        if pred >= num_tasks {
            return Err(
                format!("predecessor index {pred} out of range (num_tasks = {num_tasks})").into(),
            );
        }
        if succ >= num_tasks {
            return Err(
                format!("successor index {succ} out of range (num_tasks = {num_tasks})").into(),
            );
        }
    }
    Ok(())
}

impl<W: WeightElement> MinimumTardinessSequencing<W> {
    /// Smallest h >= 1 with every processing time strictly below 2^h.
    pub fn max_processing_time_bits(&self) -> u64 {
        crate::types::max_numeric_magnitude_bits(self.lengths.iter().map(|length| length.to_sum()))
    }

    /// Returns the number of tasks.
    pub fn num_tasks(&self) -> usize {
        self.deadlines.len()
    }

    /// Returns the task lengths.
    pub fn lengths(&self) -> &[W] {
        &self.lengths
    }

    /// Returns the deadlines.
    pub fn deadlines(&self) -> &[i64] {
        &self.deadlines
    }

    /// Returns the precedence constraints.
    pub fn precedences(&self) -> &[(usize, usize)] {
        &self.precedences
    }

    /// Returns the number of precedence constraints.
    pub fn num_precedences(&self) -> usize {
        self.precedences.len()
    }

    /// Validate a schedule and return the inverse permutation (sigma).
    /// Returns None if the config is invalid or violates precedences.
    fn decode_and_validate(&self, config: &[usize]) -> Option<Vec<usize>> {
        let n = self.num_tasks();
        let schedule = super::decode_permutation(config, n)?;

        let mut sigma = vec![0usize; n];
        for (pos, &task) in schedule.iter().enumerate() {
            sigma[task] = pos;
        }

        for &(pred, succ) in &self.precedences {
            if sigma[pred] >= sigma[succ] {
                return None;
            }
        }

        Some(sigma)
    }
}

impl Problem for MinimumTardinessSequencing<One> {
    const NAME: &'static str = "MinimumTardinessSequencing";
    type Solution = Vec<usize>;
    type Value = Min<i64>;

    crate::problem_parameters![
        ("max_processing_time_bits", max_processing_time_bits),
        ("num_precedences", num_precedences),
        ("num_tasks", num_tasks),
    ];

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![One]
    }

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
        let n = self.num_tasks();
        if config.len() != n {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "schedule length does not match the tasks".into(),
            ));
        }
        if config.iter().any(|&task| task >= n) {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "schedule contains an out-of-range task".into(),
            ));
        }
        Ok({
            let Some(sigma) = self.decode_and_validate(config) else {
                return Ok(Min(None));
            };

            // Unit length: completion time at position p is p + 1
            let mut tardy_count = 0_i64;
            for (task, &position) in sigma.iter().enumerate() {
                let completion = i64::try_from(position)
                    .ok()
                    .and_then(|position| position.checked_add(1))
                    .ok_or_else(|| {
                        crate::traits::EvaluationError::IntegerOverflow(
                            "computing a unit-length task completion time".to_string(),
                        )
                    })?;
                if completion > self.deadlines[task] {
                    tardy_count = tardy_count.checked_add(1).ok_or_else(|| {
                        crate::traits::EvaluationError::IntegerOverflow(
                            "counting tardy tasks".to_string(),
                        )
                    })?;
                }
            }

            Min(Some(tardy_count))
        })
    }
}

impl crate::solvers::BruteForceProblem for MinimumTardinessSequencing<One> {
    fn dimensions(&self) -> Vec<usize> {
        super::lehmer_dims(self.num_tasks())
    }
}

impl Problem for MinimumTardinessSequencing<i64> {
    const NAME: &'static str = "MinimumTardinessSequencing";
    type Solution = Vec<usize>;
    type Value = Min<i64>;

    crate::problem_parameters![
        ("max_processing_time_bits", max_processing_time_bits),
        ("num_precedences", num_precedences),
        ("num_tasks", num_tasks),
    ];

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![i64]
    }

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
        let n = self.num_tasks();
        if config.len() != n {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "schedule length does not match the tasks".into(),
            ));
        }
        if config.iter().any(|&task| task >= n) {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "schedule contains an out-of-range task".into(),
            ));
        }
        Ok({
            let Some(sigma) = self.decode_and_validate(config) else {
                return Ok(Min(None));
            };

            // Build schedule order from sigma (inverse permutation)
            let mut schedule = vec![0usize; n];
            for (task, &pos) in sigma.iter().enumerate() {
                schedule[pos] = task;
            }

            // Compute completion times using actual lengths
            let mut completion = vec![0_i64; n];
            let mut cumulative = 0_i64;
            for &task in &schedule {
                cumulative = cumulative.checked_add(self.lengths[task]).ok_or_else(|| {
                    crate::traits::EvaluationError::IntegerOverflow(
                        "summing task lengths while computing completion times".to_string(),
                    )
                })?;
                completion[task] = cumulative;
            }

            let mut tardy_count = 0_i64;
            for (task, &completion_time) in completion.iter().enumerate() {
                if completion_time > self.deadlines[task] {
                    tardy_count = tardy_count.checked_add(1).ok_or_else(|| {
                        crate::traits::EvaluationError::IntegerOverflow(
                            "counting tardy tasks".to_string(),
                        )
                    })?;
                }
            }

            Min(Some(tardy_count))
        })
    }
}

impl crate::solvers::BruteForceProblem for MinimumTardinessSequencing<i64> {
    fn dimensions(&self) -> Vec<usize> {
        super::lehmer_dims(self.num_tasks())
    }
}

crate::declare_variants! {
    default MinimumTardinessSequencing<One> => "2^num_tasks" create MinimumTardinessSequencingOneCreateSpec,
    MinimumTardinessSequencing<i64> => "2^num_tasks" create MinimumTardinessSequencingI64CreateSpec,
}

crate::register_brute_force! {
    MinimumTardinessSequencing<One> decode |problem: &MinimumTardinessSequencing<One>, indices: Vec<usize>| super::decode_lehmer(&indices, problem.num_tasks()).expect("enumerated Lehmer digits are valid"),
    MinimumTardinessSequencing<i64> decode |problem: &MinimumTardinessSequencing<i64>, indices: Vec<usize>| super::decode_lehmer(&indices, problem.num_tasks()).expect("enumerated Lehmer digits are valid"),
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![
        // Unit-length variant
        crate::example_db::specs::ModelExampleSpec {
            id: "minimum_tardiness_sequencing",
            instance: Box::new(MinimumTardinessSequencing::<One>::new(
                4,
                vec![2, 3, 1, 4],
                vec![(0, 2)],
            )),
            optimal_config: serde_json::json!(vec![0, 1, 2, 3]),
            optimal_value: serde_json::json!(1),
        },
        // Arbitrary-length variant
        crate::example_db::specs::ModelExampleSpec {
            id: "minimum_tardiness_sequencing_weighted",
            // 5 tasks, lengths [3,2,2,1,2], deadlines [4,3,8,3,6], prec (0→2, 1→3)
            // Optimal schedule: t0,t4,t2,t1,t3 → 2 tardy
            // Lehmer [0,3,1,0,0]: avail=[0,1,2,3,4] pick 0→0; [1,2,3,4] pick 3→4;
            //   [1,2,3] pick 1→2; [1,3] pick 0→1; [3] pick 0→3
            instance: Box::new(MinimumTardinessSequencing::<i64>::with_lengths(
                vec![3, 2, 2, 1, 2],
                vec![4, 3, 8, 3, 6],
                vec![(0, 2), (1, 3)],
            )),
            optimal_config: serde_json::json!(vec![0, 4, 2, 1, 3]),
            optimal_value: serde_json::json!(2),
        },
    ]
}

#[cfg(test)]
#[path = "../../unit_tests/models/misc/minimum_tardiness_sequencing.rs"]
mod tests;