Package org.ddolib.examples.smic

Class SMICProblem

java.lang.Object
org.ddolib.examples.smic.SMICProblem
All Implemented Interfaces:
Problem<SMICState>
public class SMICProblem extends Object implements Problem<SMICState>
The SMICProblem class represents an instance of the Single Machine with Inventory Constraint (SMIC) scheduling problem.

In this problem, a set of jobs must be processed on a single machine, subject to release times, inventory capacity limits, and job types that either consume or produce inventory units. The objective is typically to minimize the total completion time or a related cost.

Each job is defined by:

  • Its processing time,
  • Its release time,
  • Its type (0 = consuming, 1 = producing inventory),
  • Its inventory change (how much it consumes or produces),
  • Its weight, used in objective computations (if applicable).
The machine starts with an initial inventory initInventory and must never exceed the maximum capacity capaInventory nor drop below zero.

This class implements the Problem interface, making it compatible with DDO (Decision Diagram Optimization) and other optimization frameworks. It provides methods to define:

  • The initial state of the problem,
  • The possible transitions between states,
  • The associated transition costs,
  • The domain of feasible decisions at each step.
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    SMICProblem(String filename)
    Constructs a SMICProblem instance by parsing a text file.
    SMICProblem(String name, int nbJob, int initInventory, int capaInventory, int[] type, int[] processing, int[] weight, int[] release, int[] inventory)
    Constructs a SMICProblem instance without a known optimal value.
    SMICProblem(String name, int nbJob, int initInventory, int capaInventory, int[] type, int[] processing, int[] weight, int[] release, int[] inventory, Optional<Double> optimal)
    Constructs a SMICProblem instance with full specification.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(SMICState state, int var)
    Returns the feasible domain of jobs that can be scheduled next, given the current inventory and remaining capacity constraints.
    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.
    SMICState
    initialState()
    Returns the initial state of the problem, where all jobs remain to be processed and the machine starts at time 0 with the initial inventory.
    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.
    String
    toString()
    SMICState
    transition(SMICState state, Decision decision)
    Applies a decision to transition from the current state to the next.
    double
    transitionCost(SMICState state, Decision decision)
    Computes the cost associated with scheduling a job from the current state.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • SMICProblem

      public SMICProblem(String name, int nbJob, int initInventory, int capaInventory, int[] type, int[] processing, int[] weight, int[] release, int[] inventory, Optional<Double> optimal)
      Constructs a SMICProblem instance with full specification.
      Parameters:
      name - the name of the instance
      nbJob - number of jobs
      initInventory - initial inventory level
      capaInventory - maximum inventory capacity
      type - job types (0 = consume, 1 = produce)
      processing - processing times for each job
      weight - weights associated with each job
      release - release times for each job
      inventory - inventory change (positive for production, negative for consumption)
      optimal - optional optimal objective value (if known)

    • SMICProblem

      public SMICProblem(String name, int nbJob, int initInventory, int capaInventory, int[] type, int[] processing, int[] weight, int[] release, int[] inventory)
      Constructs a SMICProblem instance without a known optimal value.
      Parameters:
      name - the name of the instance
      nbJob - number of jobs
      initInventory - initial inventory level
      capaInventory - maximum inventory capacity
      type - job types (0 = consume, 1 = produce)
      processing - processing times for each job
      weight - weights associated with each job
      release - release times for each job
      inventory - inventory change (positive for production, negative for consumption)

    • SMICProblem

      public SMICProblem(String filename) throws IOException
      Constructs a SMICProblem instance by parsing a text file.

      The file format must follow the convention: 

       nbJob  initInventory  capaInventory
 type_i  processing_i  weight_i  release_i  inventory_i  (for each job)
 [optional: optimal_value]
      Parameters:
      filename - the path to the problem file
      Throws:
      IOException - if the file cannot be read or parsed correctly

  • Method Details

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • nbVars

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

    • initialState

      public SMICState initialState()
      Returns the initial state of the problem, where all jobs remain to be processed and the machine starts at time 0 with the initial inventory.
      Specified by:
      initialState in interface Problem<SMICState>
      Returns:
      the initial SMICState

    • initialValue

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

    • domain

      public Iterator<Integer> domain(SMICState state, int var)
      Returns the feasible domain of jobs that can be scheduled next, given the current inventory and remaining capacity constraints.
      Specified by:
      domain in interface Problem<SMICState>
      Parameters:
      state - the current SMICState
      var - the current decision variable index (unused)
      Returns:
      an iterator over feasible job indices

    • transition

      public SMICState transition(SMICState state, Decision decision)
      Applies a decision to transition from the current state to the next.

      The method removes the scheduled job from the remaining set, updates the current time and adjusts inventory levels.

      Specified by:
      transition in interface Problem<SMICState>
      Parameters:
      state - the current state
      decision - the job to schedule next
      Returns:
      the resulting SMICState after applying the decision

    • transitionCost

      public double transitionCost(SMICState state, Decision decision)
      Computes the cost associated with scheduling a job from the current state.

      The cost includes any waiting time due to release constraints and the job’s processing time.

      Specified by:
      transitionCost in interface Problem<SMICState>
      Parameters:
      state - the current state
      decision - the decision (job) being scheduled
      Returns:
      the cost of performing the transition

    • 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<SMICState>
      Returns:
      an Optional containing the known optimal value, or empty if unknown

    • 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<SMICState>
      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.