Struct SequencingToMinimizeWeightedTardiness 

pub struct SequencingToMinimizeWeightedTardiness { /* private fields */ }

Sequencing to Minimize Weighted Tardiness.

Given jobs with processing times l_j, weights w_j, deadlines d_j, and a bound K, determine whether there exists a permutation schedule on a single machine whose total weighted tardiness sum_j w_j * max(0, C_j - d_j) is at most K, where C_j is the completion time of job j.

Representation

Configurations use Lehmer code to encode permutations of the jobs. Decoding yields the job order processed by the single machine.

Example

use problemreductions::models::misc::SequencingToMinimizeWeightedTardiness;
use problemreductions::{BruteForce, Problem};

let problem = SequencingToMinimizeWeightedTardiness::new(
    vec![3, 4, 2, 5, 3],
    vec![2, 3, 1, 4, 2],
    vec![5, 8, 4, 15, 10],
    13,
);

let solver = BruteForce::new();
assert!(solver.solve(&problem).unwrap().is_some());

Implementations

impl SequencingToMinimizeWeightedTardiness

pub fn new( lengths: Vec<i64>, weights: Vec<i64>, deadlines: Vec<i64>, bound: i64, ) -> Self

Create a new weighted tardiness scheduling instance.

Panics

Panics if the input vectors do not have the same length.

pub fn lengths(&self) -> &[i64]

Returns the job lengths.

pub fn weights(&self) -> &[i64]

Returns the tardiness weights.

pub fn deadlines(&self) -> &[i64]

Returns the deadlines.

pub fn bound(&self) -> i64

Returns the weighted tardiness bound.

pub fn max_numeric_magnitude_bits(&self) -> u64

Smallest h >= 1 with all lengths, weights, deadlines, and the cost bound below 2^h.

pub fn num_tasks(&self) -> usize

Returns the number of jobs.

pub fn total_weighted_tardiness( &self, config: &[usize], ) -> Result<Option<i64>, EvaluationError>

Compute the total weighted tardiness of a Lehmer-encoded schedule.

Returns Ok(None) if the configuration is not a valid Lehmer code.

Trait Implementations

impl BruteForceProblem for SequencingToMinimizeWeightedTardiness

fn dimensions(&self) -> Vec<usize>

Cardinality of each coordinate in the brute-force search space.

fn num_variables(&self) -> usize

Number of coordinates in the brute-force search space.

impl Clone for SequencingToMinimizeWeightedTardiness

fn clone(&self) -> SequencingToMinimizeWeightedTardiness

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SequencingToMinimizeWeightedTardiness

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl DeclaredVariant for SequencingToMinimizeWeightedTardiness

impl<'de> Deserialize<'de> for SequencingToMinimizeWeightedTardiness

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for SequencingToMinimizeWeightedTardiness

const NAME: &'static str = "SequencingToMinimizeWeightedTardiness"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Solution = Vec<usize>

Mathematical witness type for this problem.

type Value = Or

The evaluation value type.

fn parameter_names() -> &'static [&'static str]

Canonical parameter names for this problem model.

fn parameters(&self) -> ProblemParameters

Measure the complete canonical parameters of this concrete instance.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn evaluate(&self, config: &Self::Solution) -> Result<Or, EvaluationError>

Evaluate the problem on a solution.

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP<i64, i64, Bounded>> for SequencingToMinimizeWeightedTardiness

type Result = ReductionSTMWTToILP

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl Serialize for SequencingToMinimizeWeightedTardiness

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.