Struct FlowShopScheduling 

pub struct FlowShopScheduling { /* private fields */ }

The Flow Shop Scheduling problem.

Given m processors and a set of n jobs, each job j consists of m tasks t_1[j], t_2[j], ..., t_m[j] with specified lengths. Tasks must be processed in processor order: job j cannot start on machine i+1 until its task on machine i is completed. The question is whether there exists a schedule such that all jobs complete by deadline D.

Representation

Configurations use Lehmer code encoding with dims() = [n, n-1, ..., 1]. A config [c_0, c_1, ..., c_{n-1}] where c_i < n - i is decoded by maintaining a list of available jobs and picking the c_i-th element:

For 3 jobs, config [2, 0, 0]: available=[0,1,2], pick index 2 → job 2; available=[0,1], pick index 0 → job 0; available=[1], pick index 0 → job 1. Result: job order [2, 0, 1].

Given a job order, start times are determined greedily (as early as possible).

Example

use problemreductions::models::misc::FlowShopScheduling;
use problemreductions::{Problem, Solver, BruteForce};

// 2 machines, 3 jobs, deadline 10
let problem = FlowShopScheduling::new(2, vec![vec![2, 3], vec![3, 2], vec![1, 4]], 10);
let solver = BruteForce::new();
let solution = solver.find_satisfying(&problem);
assert!(solution.is_some());

Implementations

impl FlowShopScheduling

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

Create a new Flow Shop Scheduling instance.

Arguments

• num_processors - Number of machines m
• task_lengths - task_lengths[j][i] = processing time of job j on machine i. Each inner Vec must have length num_processors.
• deadline - Global deadline D

Panics

Panics if any job does not have exactly num_processors tasks.

pub fn num_processors(&self) -> usize

Get the number of processors.

pub fn task_lengths(&self) -> &[Vec<u64>]

Get the task lengths matrix.

pub fn deadline(&self) -> u64

Get the deadline.

pub fn num_jobs(&self) -> usize

Get the number of jobs.

pub fn compute_makespan(&self, job_order: &[usize]) -> u64

Compute the makespan for a given job ordering.

The job_order slice must be a permutation of 0..num_jobs. Returns the completion time of the last job on the last machine.

Trait Implementations

impl Clone for FlowShopScheduling

fn clone(&self) -> FlowShopScheduling

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for FlowShopScheduling

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for FlowShopScheduling

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for FlowShopScheduling

const NAME: &'static str = "FlowShopScheduling"

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

type Metric = bool

The evaluation metric 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]) -> bool

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 Serialize for FlowShopScheduling

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 FlowShopScheduling

impl SatisfactionProblem for FlowShopScheduling