Struct OpenShopScheduling 

pub struct OpenShopScheduling { /* private fields */ }

The Open Shop Scheduling problem.

Given m machines and n jobs, where job j has one task on each machine i with processing time p[j][i], find a non-preemptive schedule that minimizes the makespan. Unlike flow-shop or job-shop scheduling, there is no prescribed order for the tasks of a given job — each job’s tasks may be processed on the machines in any order.

Constraints

1. Machine constraint: Each machine processes at most one job at a time.
2. Job constraint: Each job occupies at most one machine at a time.

Configuration Encoding

The configuration is a flat array of n * m values. config[i * n .. (i + 1) * n] gives the permutation of jobs on machine i (direct job indices, not Lehmer code). A segment is valid iff it is a permutation of 0..n. Invalid configs return Min(None).

Example

use problemreductions::models::misc::OpenShopScheduling;
use problemreductions::{Problem, Solver, BruteForce};
use problemreductions::types::Min;

// 2 machines, 2 jobs
let p = vec![vec![1, 2], vec![2, 1]];
let problem = OpenShopScheduling::new(2, p);
let solver = BruteForce::new();
let value = Solver::solve(&solver, &problem);
assert_eq!(value, Min(Some(3)));

Implementations

impl OpenShopScheduling

pub fn new(num_machines: usize, processing_times: Vec<Vec<usize>>) -> Self

Create a new Open Shop Scheduling instance.

Arguments

• num_machines - Number of machines m
• processing_times - processing_times[j][i] = processing time of job j on machine i. Each inner Vec must have length num_machines.

Panics

Panics if any job does not have exactly num_machines processing times.

pub fn num_machines(&self) -> usize

Get the number of machines.

pub fn num_jobs(&self) -> usize

Get the number of jobs.

pub fn processing_times(&self) -> &[Vec<usize>]

Get the processing time matrix.

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

Decode the per-machine job orderings from a config.

Returns None if the config length is wrong or any segment is not a valid permutation of 0..n.

pub fn compute_makespan(&self, orders: &[Vec<usize>]) -> usize

Compute the makespan from a set of per-machine job orderings.

Uses a greedy simulation: at each step, among all machines whose next scheduled job can start (both machine and job are free), schedule the one with the earliest available start time.

Trait Implementations

impl Clone for OpenShopScheduling

fn clone(&self) -> OpenShopScheduling

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for OpenShopScheduling

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for OpenShopScheduling

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for OpenShopScheduling

const NAME: &'static str = "OpenShopScheduling"

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

type Value = Min<usize>

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]) -> Min<usize>

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 OpenShopScheduling

type Result = ReductionOSSToILP

The reduction result type.

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

Reduce this problem to the target problem type.

impl ReduceTo<OpenShopScheduling> for Partition

type Result = ReductionPartitionToOpenShopScheduling

The reduction result type.

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

Reduce this problem to the target problem type.

impl Serialize for OpenShopScheduling

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 OpenShopScheduling