Struct MultiprocessorScheduling 

pub struct MultiprocessorScheduling { /* private fields */ }

The Multiprocessor Scheduling problem.

Given a set T of tasks with processing times, a number m of identical processors, and a deadline D, determine whether there exists an assignment of tasks to processors such that the total load on each processor does not exceed D.

Because tasks are independent and processors are identical, any feasible schedule can be packed processor-by-processor without idle gaps. This makes the scheduling question equivalent to partitioning tasks among processors with per-processor load at most D.

Representation

Each task has a variable in {0, ..., m-1} representing its processor assignment.

Example

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

// 5 tasks with lengths [4, 5, 3, 2, 6], 2 processors, deadline 10
let problem = MultiprocessorScheduling::new(vec![4, 5, 3, 2, 6], 2, 10);
let solver = BruteForce::new();
let solution = solver.solve(&problem).unwrap();
assert!(solution.is_some());

Implementations

impl MultiprocessorScheduling

pub fn new(lengths: Vec<i64>, num_processors: usize, deadline: i64) -> Self

Create a new Multiprocessor Scheduling instance.

Panics

Panics if num_processors is zero.

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

Returns the processing times for each task.

pub fn num_processors(&self) -> usize

Returns the number of processors.

pub fn deadline(&self) -> i64

Returns the deadline.

pub fn num_tasks(&self) -> usize

Returns the number of tasks.

pub fn max_numeric_magnitude_bits(&self) -> u64

Smallest h >= 1 such that every task length and the deadline are below 2^h.

pub fn total_length(&self) -> i64

Returns the total processing time of all tasks.

Trait Implementations

impl BruteForceProblem for MultiprocessorScheduling

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 MultiprocessorScheduling

fn clone(&self) -> MultiprocessorScheduling

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for MultiprocessorScheduling

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

Formats the value using the given formatter.

impl DeclaredVariant for MultiprocessorScheduling

impl<'de> Deserialize<'de> for MultiprocessorScheduling

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for MultiprocessorScheduling

const NAME: &'static str = "MultiprocessorScheduling"

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> for MultiprocessorScheduling

type Result = ReductionMSToILP

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 ReduceTo<MultiprocessorScheduling> for Partition

type Result = ReductionPartitionToMPS

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 MultiprocessorScheduling

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

where __S: Serializer,

Serialize this value into the given Serde serializer.