Implements the classical flow shop scheduling problem. More...

#include <FlowShop.h>

Public Member Functions
Constructors
	FlowShop ()
	Constructs a FlowShop problem with zero dimensions.
	FlowShop (size_t num_jobs, size_t num_machines)
	Constructs a FlowShop problem with specified dimensions.
	FlowShop (size_t num_jobs, size_t num_machines, std::vector< uint64_t > &&data)
	Internal constructor used by pybind11 bindings.
Data Access
size_t	num_jobs () const
	Returns the number of jobs in this problem.
size_t	num_machines () const
	Returns the number of machines in this problem.
uint64_t *	data ()
	Returns mutable pointer to flattened processing times matrix.
const uint64_t *	data () const
	Returns const pointer to flattened processing times matrix.
uint64_t *	due_dates_data ()
	Returns mutable pointer to due dates vector.
const uint64_t *	due_dates_data () const
	Returns const pointer to due dates vector.
Problem Configuration
void	set_jobs (size_t num_jobs, size_t num_machines, std::vector< uint64_t > &&new_data)
	Replaces the entire processing times matrix and dimensions.
void	set_due_dates (std::vector< uint64_t > &&new_data)
	Replaces the due dates vector.
Optimization Methods
FlowShopResult	runNEH (bool blocking=false, bool optimizeTardiness=false)
	Optimizes the flow shop schedule using the NEH heuristic.
FlowShopResult	runDE (bool blocking, bool optimizeTardiness, size_t popSize, double f, double cr, size_t maxGenerations, unsigned long seed, std::string &mutationStrategy, std::string &crossoverStrategy)
	Optimizes the flow shop schedule using Differential Evolution.
Evaluable Concept Implementation
void	getInitialSolutions (std::vector< std::vector< double > > &population)
	Generates an initial population of candidate solutions.
constexpr double	getLowerBounds () const
	Returns the lower bound for the optimization domain.
constexpr double	getUpperBounds () const
	Returns the upper bound for the optimization domain.
double	evaluateSolution (const std::vector< double > &solution)
	Evaluates the objective function for a given solution.

Detailed Description

Implements the classical flow shop scheduling problem.

The FlowShop class models a manufacturing environment where jobs must be processed sequentially through a series of machines in a fixed order. The goal is to find an optimal job scheduling order that minimizes either makespan (total completion time) or total tardiness (sum of lateness over all jobs).

Problem Definition:

Given:

n jobs, each with execution times on m machines
Optional due dates for each job
Two objective functions: makespan or total tardiness
Optional blocking constraint (job cannot leave a machine until next is free)

Find: A permutation of jobs that minimizes the chosen objective.

Key Features:

Dual optimization support: NEH heuristic (fast approximation) and DE (high-quality)
Two objective metrics: makespan minimization and tardiness minimization
Optional job blocking for realistic manufacturing constraints
Intelligent population initialization (NEH seed + perturbations + random)
SPV (Smallest Position Value) encoding for seamless DE integration
Thread-safe evaluation with OpenMP parallelization

Problem Data:

jobs_times_: m×n matrix (row-major flattened) storing processing times. jobs_times_[i * num_machines + j] = time for job i on machine j.
due_dates_: Vector of n due dates, one per job (for tardiness calculation).

Evaluable Concept:

FlowShop satisfies the Evaluable concept, allowing it to be optimized directly by DifferentialEvolution:

getInitialSolutions(): Generates population with NEH seeding
evaluateSolution(): Converts SPV vector to job order and evaluates schedule
getLowerBounds()/getUpperBounds(): Returns [-1.0, 1.0] for SPV encoding

Note: The problem assumes uniform bounds across dimensions (SPV encoding).; All evaluation is deterministic once scheduling parameters are set (blocking, tardiness).

Constructor & Destructor Documentation

◆ FlowShop() [1/3]

FlowShop::FlowShop ( )

inline

Constructs a FlowShop problem with zero dimensions.

Creates an empty problem instance. Data must be populated via set_jobs() before optimization.

◆ FlowShop() [2/3]

FlowShop::FlowShop	(	size_t	num_jobs,
		size_t	num_machines )

inline

Constructs a FlowShop problem with specified dimensions.

Allocates storage for a problem with num_jobs jobs and num_machines machines. All processing times initialize to zero; call set_jobs() to populate actual data.

Parameters

num_jobs	Number of jobs in the scheduling problem
num_machines	Number of machines in sequence

Exceptions

std::runtime_error if num_jobs or num_machines is zero

◆ FlowShop() [3/3]

FlowShop::FlowShop	(	size_t	num_jobs,
		size_t	num_machines,
		std::vector< uint64_t > &&	data )

inline

Internal constructor used by pybind11 bindings.

Constructs a FlowShop with pre-allocated data moved from caller. Validates that data size matches the dimensions (num_jobs × num_machines).

Parameters

num_jobs	Number of jobs
num_machines	Number of machines
data	Rvalue reference to flattened m×n matrix (row-major)

Exceptions

std::runtime_error if data.size() != num_jobs * num_machines

Note: This constructor is primarily for Python interoperability; use other constructors for C++ code unless specifically integrating with pybind11.

Member Function Documentation

◆ data() [1/2]

uint64_t * FlowShop::data ( )

inline

Returns mutable pointer to flattened processing times matrix.

The matrix is stored in row-major order: jobs_times[i * num_machines + j] contains the processing time of job i on machine j.

Returns: Pointer to first element of jobs_times_ vector

◆ data() [2/2]

const uint64_t * FlowShop::data ( ) const

inline

Returns const pointer to flattened processing times matrix.

Returns: Const pointer to first element of jobs_times_ vector

See also: data()

◆ due_dates_data() [1/2]

uint64_t * FlowShop::due_dates_data ( )

inline

Returns mutable pointer to due dates vector.

The vector has size num_jobs; due_dates_[i] is the due date for job i. Used for tardiness calculation: tardiness = max(0, completion_time - due_date).

Returns: Pointer to first element of due_dates_ vector

◆ due_dates_data() [2/2]

const uint64_t * FlowShop::due_dates_data ( ) const

inline

Returns const pointer to due dates vector.

Returns: Const pointer to first element of due_dates_ vector

See also: due_dates_data()

◆ evaluateSolution()

double FlowShop::evaluateSolution ( const std::vector< double > & solution )

Evaluates the objective function for a given solution.

Converts an SPV-encoded vector to a job permutation, evaluates the resulting schedule, and returns the objective value (makespan or tardiness).

Algorithm:

Convert SPV vector to job order via spvToPerm()
Calculate completion times for the schedule
Return makespan (if optimizeTardiness=false) or total tardiness (if true)

Complexity: O(nm) for completion time calculation + O(n log n) for SPV conversion.

Parameters

[in] solution SPV-encoded solution vector (size = num_jobs, values in [-1, 1])

Returns

Objective value:

Makespan (completion time of last job) if optimizeTardiness=false
Total tardiness (sum of individual tardiness) if optimizeTardiness=true Returned as double for compatibility with DE optimizer.

Thread Safety: This method is thread-safe for concurrent evaluation when blocking and optimizeTardiness fields are constant. Must not be called concurrently with runDE() or field modifications.

Requirements: blocking and optimizeTardiness must be set before calling (typically by runDE() prior to optimizer invocation).

◆ getInitialSolutions()

void FlowShop::getInitialSolutions ( std::vector< std::vector< double > > & population )

Generates an initial population of candidate solutions.

Creates population.size() SPV-encoded solutions using three strategies:

First solution: NEH heuristic schedule
Next 25%: NEH with small random perturbations
Remaining: Uniformly random in [-1, 1]^n

This initialization biases the population toward high-quality regions (NEH solutions) while maintaining diversity for exploration.

Parameters

[out] population Pre-allocated vector of population.size() solution vectors. Each solution is filled with SPV values in [-1, 1].

Thread Safety: Uses OpenMP parallelization to generate initial solutions quickly.

Note: This method requires blocking and optimizeTardiness fields to be set (typically by runDE() before calling DifferentialEvolution::optimize).

See also: initPopulationVectors()

◆ getLowerBounds()

double FlowShop::getLowerBounds ( ) const

inlineconstexpr

Returns the lower bound for the optimization domain.

For SPV encoding, all dimensions share a uniform lower bound of -1.0.

Returns: Constant value -1.0

◆ getUpperBounds()

double FlowShop::getUpperBounds ( ) const

inlineconstexpr

Returns the upper bound for the optimization domain.

For SPV encoding, all dimensions share a uniform upper bound of 1.0.

Returns: Constant value 1.0

◆ num_jobs()

size_t FlowShop::num_jobs ( ) const

inline

Returns the number of jobs in this problem.

Returns: Number of jobs (rows in processing time matrix)

◆ num_machines()

size_t FlowShop::num_machines ( ) const

inline

Returns the number of machines in this problem.

Returns: Number of machines (columns in processing time matrix)

◆ runDE()

FlowShopResult FlowShop::runDE	(	bool	blocking,
		bool	optimizeTardiness,
		size_t	popSize,
		double	f,
		double	cr,
		size_t	maxGenerations,
		unsigned long	seed,
		std::string &	mutationStrategy,
		std::string &	crossoverStrategy )

Optimizes the flow shop schedule using Differential Evolution.

Applies the DE metaheuristic to find high-quality solutions. The algorithm:

Initializes population with NEH seed, perturbations, and random solutions
Iterates over generations, applying mutation and crossover
Evaluates each candidate by converting SPV encoding to job order
Returns best solution found and convergence history

Solution Encoding: SPV (Smallest Position Value)

Continuous vector in [-1, 1]^n representing job priorities
Higher values = earlier scheduling position
Enables DE's continuous operators on permutation problem

Population Initialization:

1 solution: NEH-generated schedule (converted to SPV)
25% of population: NEH with small random perturbations
Remaining: Uniformly random solutions in [-1, 1]^n

Parameters

blocking	If true, enforces job blocking constraints
optimizeTardiness	If true, minimizes tardiness; if false, minimizes makespan
popSize	Population size; typically 20-50 for small problems
f	Differential weight (mutation scale factor); typical range (0, 2], e.g., 0.8
cr	Crossover rate; range [0, 1], e.g., 0.9 (higher = more diversity)
maxGenerations	Maximum iterations; termination criterion
seed	Random seed for reproducible results
mutationStrategy	Name of mutation operator; one of: "rand1", "rand2", "best1", "best2", "randToBest1" Defaults to "rand1" if empty
crossoverStrategy	Name of crossover operator; one of: "bin" (binomial, default), "exp" (exponential) Defaults to "bin" if empty

Returns

FlowShopResult containing:

sequence: Best job order found
makespan: Makespan of best solution
completionTimes: Completion times for best solution
tardiness: Tardiness vector for best solution
fitnesses: Convergence history (best fitness per generation)

Thread Safety: Evaluation is parallelized with OpenMP. Concurrent solution evaluations are safe; problem state (blocking, optimizeTardiness) is read-only during optimization.

Example:

FlowShop problem(20, 10);
// ... set jobs and due dates ...
FlowShopResult result = problem.runDE(
    true,              // blocking
    true,              // optimize tardiness
    30,                // population size
    0.8,               // F
    0.9,               // CR
    100,               // generations
    42,                // seed
    mutationStrategy = "best1",
    crossoverStrategy = "bin"
);

◆ runNEH()

FlowShopResult FlowShop::runNEH	(	bool	blocking = false,
		bool	optimizeTardiness = false )

Optimizes the flow shop schedule using the NEH heuristic.

The Nawaz-Enscore-Ham (NEH) algorithm is a polynomial-time approximation algorithm that produces high-quality solutions quickly:

Initialization: Sort jobs by total processing time (or due date).
Insertion: Iteratively insert each remaining job at the position that minimizes the chosen objective (makespan or tardiness).
Output: Return the final job order and computed metrics.

Complexity: O(n² m) for makespan; O(n² m) for tardiness with due dates.

Parameters

blocking	If true, enforces job blocking: a job cannot leave machine i until machine i+1 is free (models buffer constraints)
optimizeTardiness	If true, minimizes total tardiness (sum of max(0, completion - due_date)); if false, minimizes makespan (final completion time)

Returns

FlowShopResult containing:

sequence: Job order (indices 0 to num_jobs-1)
makespan: Total completion time of final job on final machine
completionTimes: m×n matrix of completion times
tardiness: Vector of tardiness for each job (if optimizeTardiness=true)
fitnesses: Empty vector (NEH does not track convergence)

Example:

FlowShop problem(10, 5);  // 10 jobs, 5 machines
// ... populate jobs_times and due_dates ...
FlowShopResult result = problem.runNEH(false, true);  // Tardiness, no blocking

◆ set_due_dates()

void FlowShop::set_due_dates ( std::vector< uint64_t > && new_data )

inline

Replaces the due dates vector.

Sets new due dates for tardiness-based optimization. Must have exactly num_jobs elements.

Parameters

new_data Rvalue reference to due dates vector (size = num_jobs)

Exceptions

std::runtime_error if new_data.size() != num_jobs_

Postcondition: due_dates_ contains the new due date values

Note: Due dates are only used when optimizeTardiness=true in runNEH() or runDE().

◆ set_jobs()

void FlowShop::set_jobs	(	size_t	num_jobs,
		size_t	num_machines,
		std::vector< uint64_t > &&	new_data )

inline

Replaces the entire processing times matrix and dimensions.

Sets new problem dimensions and processing time data. Validates that the data size matches dimensions. Resets due_dates to zero for all jobs.

Parameters

num_jobs	New number of jobs
num_machines	New number of machines
new_data	Rvalue reference to flattened m×n matrix (row-major, size = num_jobs × num_machines)

Exceptions

std::runtime_error if new_data.size() != num_jobs * num_machines

Postcondition: num_jobs_ and num_machines_ are updated; jobs_times_ contains the new data; due_dates_ is reset to [0, 0, ..., 0]

The documentation for this class was generated from the following files:

src/opti_py/cpp/include/opti_py/FlowShop/FlowShop.h
src/opti_py/cpp/src/FlowShop/FlowShop.cpp

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ FlowShop() [1/3]

◆ FlowShop() [2/3]

◆ FlowShop() [3/3]

Member Function Documentation

◆ data() [1/2]

◆ data() [2/2]

◆ due_dates_data() [1/2]

◆ due_dates_data() [2/2]

◆ evaluateSolution()

◆ getInitialSolutions()

◆ getLowerBounds()

◆ getUpperBounds()

◆ num_jobs()

◆ num_machines()

◆ runDE()

◆ runNEH()

◆ set_due_dates()

◆ set_jobs()