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, Solver, 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.find_witness(&problem);
assert!(solution.is_some());

Implementations

impl MultiprocessorScheduling

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

Create a new Multiprocessor Scheduling instance.

Panics

Panics if num_processors is zero.

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

Returns the processing times for each task.

pub fn num_processors(&self) -> usize

Returns the number of processors.

pub fn deadline(&self) -> u64

Returns the deadline.

pub fn num_tasks(&self) -> usize

Returns the number of tasks.

pub fn total_length(&self) -> u64

Returns the total processing time of all tasks.

Trait Implementations

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

type Result = ReductionMSToILP

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<MultiprocessorScheduling> for Partition

type Result = ReductionPartitionToMPS

The reduction result type.

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

Reduce this problem to the target problem type.

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.

impl DeclaredVariant for MultiprocessorScheduling