Package org.ddolib.examples.pigmentscheduling

Class PSProblem

java.lang.Object
org.ddolib.examples.pigmentscheduling.PSProblem
All Implemented Interfaces:
Problem<PSState>
public class PSProblem extends Object implements Problem<PSState>
Represents an instance of the Pigment Sequencing Problem (PSP) used within a Decision Diagram Optimization (DDO) framework.

The PSProblem class models a single-machine scheduling problem with production changeover costs, item-dependent stocking costs, and demand constraints distributed over a finite planning horizon.

Each time period can be assigned to the production of one item or remain idle. The goal of the optimization is to minimize the total cost, which includes:

  • Stocking costs — penalizing early production of items before their demand dates.
  • Changeover costs — incurred when switching production between different items.

This class implements the Problem interface parameterized by PSState, and defines all problem-specific behavior such as initial state construction, variable domain generation, state transitions, and transition cost computation.

The structure of this problem is based on instances compatible with the PhD thesis of Vianney Coppe (2024).

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    IDLE
    Represents the idle state of the machine (no production).

  • Constructor Summary

    Constructors
    Constructor
    Description
    PSProblem(int nItems, int horizon, int[] stockingCost, int[][] changeoverCost, int[][] previousDemands)
    Constructs a PSP instance from explicit data arrays without a known optimal value.
    PSProblem(int nItems, int horizon, int[] stockingCost, int[][] changeoverCost, int[][] previousDemands, Optional<Double> optimal)
    Constructs a PSP instance from explicit data arrays and a known optimal value.
    PSProblem(String filename)
    Constructs a PSP instance from a data file.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(PSState state, int depth)
    Defines the domain of feasible decisions (items to produce or idle) for a given state and time depth.
    double
    evaluate(int[] solution)
    Given a solution such that solution[i] is the value of the variable x_i, returns the value of this solution and checks if the solution respects the problem's constraints.
    PSState
    initialState()
    Builds the initial problem state, where no items have been produced and the machine is idle.
    double
    initialValue()
    Returns the initial objective value associated with the initial state.
    int
    nbVars()
    Optional<Double>
    optimalValue()
    Returns the known optimal value of the problem, if available.
    void
    setName(String name)
    Assigns a name to the problem instance for display or debugging purposes.
    String
    toString()
    PSState
    transition(PSState state, Decision decision)
    Applies a production decision to the current state and returns the resulting new state.
    double
    transitionCost(PSState state, Decision decision)
    Computes the cost incurred by executing a given decision from the current state.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • IDLE

      public static final int IDLE
      Represents the idle state of the machine (no production).
      See Also:

  • Constructor Details

    • PSProblem

      public PSProblem(int nItems, int horizon, int[] stockingCost, int[][] changeoverCost, int[][] previousDemands, Optional<Double> optimal)
      Constructs a PSP instance from explicit data arrays and a known optimal value.
      Parameters:
      nItems - number of item types
      horizon - number of time periods
      stockingCost - array of stocking costs for each item type
      changeoverCost - matrix of changeover costs between item types
      previousDemands - matrix of previous demand indices for each item and time
      optimal - known optimal objective value (if available)

    • PSProblem

      public PSProblem(int nItems, int horizon, int[] stockingCost, int[][] changeoverCost, int[][] previousDemands)
      Constructs a PSP instance from explicit data arrays without a known optimal value.
      Parameters:
      nItems - number of item types
      horizon - number of time periods
      stockingCost - array of stocking costs for each item type
      changeoverCost - matrix of changeover costs between item types
      previousDemands - matrix of previous demand indices for each item and time

    • PSProblem

      public PSProblem(String filename)
      Constructs a PSP instance from a data file.

      The file format is expected to contain:

      1. Horizon (number of time periods)
      2. Number of item types
      3. Number of orders
      4. Changeover cost matrix (nItems × nItems)
      5. Stocking costs for each item
      6. Demand matrix (nItems × horizon)
      7. Known optimal value (optional)
      Parameters:
      filename - path to the input data file

  • Method Details

    • setName

      public void setName(String name)
      Assigns a name to the problem instance for display or debugging purposes.
      Parameters:
      name - the name of the instance

    • optimalValue

      public Optional<Double> optimalValue()
      Returns the known optimal value of the problem, if available.

      Note: This value should correspond to the expected output of the solver. For maximization problems, be careful with negative values.

      Specified by:
      optimalValue in interface Problem<PSState>
      Returns:
      an Optional containing the known optimal value, or empty if unknown

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • nbVars

      public int nbVars()
      Specified by:
      nbVars in interface Problem<PSState>
      Returns:
      the total number of decision variables in this problem

    • initialValue

      public double initialValue()
      Returns the initial objective value associated with the initial state.
      Specified by:
      initialValue in interface Problem<PSState>
      Returns:
      the starting value of the objective function

    • initialState

      public PSState initialState()
      Builds the initial problem state, where no items have been produced and the machine is idle.
      Specified by:
      initialState in interface Problem<PSState>
      Returns:
      the initial PSState representing the start of the planning horizon

    • domain

      public Iterator<Integer> domain(PSState state, int depth)
      Defines the domain of feasible decisions (items to produce or idle) for a given state and time depth.

      The domain depends on the remaining demands and available time periods. If there is insufficient time to satisfy all remaining demands, the domain becomes empty. Otherwise, the IDLE option may be included if there is enough slack in the schedule.

      Specified by:
      domain in interface Problem<PSState>
      Parameters:
      state - the current scheduling state
      depth - the depth of the decision variable (i.e., time index)
      Returns:
      an iterator over feasible item indices (and possibly IDLE)

    • transition

      public PSState transition(PSState state, Decision decision)
      Applies a production decision to the current state and returns the resulting new state.
      Specified by:
      transition in interface Problem<PSState>
      Parameters:
      state - the current scheduling state
      decision - the production decision (item index or IDLE)
      Returns:
      the successor state after applying the decision

    • transitionCost

      public double transitionCost(PSState state, Decision decision)
      Computes the cost incurred by executing a given decision from the current state.

      The cost consists of two components:

      • Stocking cost: proportional to how early the produced item is made relative to its next demand time.
      • Changeover cost: cost of switching from the last produced item to the current one.
      Specified by:
      transitionCost in interface Problem<PSState>
      Parameters:
      state - the current state
      decision - the production decision (item or idle)
      Returns:
      the transition cost incurred by the decision

    • evaluate

      public double evaluate(int[] solution) throws InvalidSolutionException
      Description copied from interface: Problem
      Given a solution such that solution[i] is the value of the variable x_i, returns the value of this solution and checks if the solution respects the problem's constraints.

      Note: For maximization problems, the returned value is minus the computed value.

      Specified by:
      evaluate in interface Problem<PSState>
      Parameters:
      solution - A solution of the problem.
      Returns:
      The value of the input solution
      Throws:
      InvalidSolutionException - If the solution does not respect problem's constraints.