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, Solver};

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.find_witness(&problem).is_some());

Implementations

impl SequencingToMinimizeWeightedTardiness

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

Create a new weighted tardiness scheduling instance.

Panics

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

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

Returns the job lengths.

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

Returns the tardiness weights.

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

Returns the deadlines.

pub fn bound(&self) -> u64

Returns the weighted tardiness bound.

pub fn num_tasks(&self) -> usize

Returns the number of jobs.

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

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

Returns None if the configuration is not a valid Lehmer code or if the accumulated objective does not fit in u64.

Trait Implementations

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<'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 Value = Or

The evaluation value type.

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

Returns variant attributes derived from type parameters.

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

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> Or

Evaluate the problem on a configuration.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP<i32>> for SequencingToMinimizeWeightedTardiness

type Result = ReductionSTMWTToILP

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

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.

impl DeclaredVariant for SequencingToMinimizeWeightedTardiness