Package org.ddolib.examples.msct

Class MSCTProblem

java.lang.Object
org.ddolib.examples.msct.MSCTProblem
All Implemented Interfaces:
Problem<MSCTState>
public class MSCTProblem extends Object implements Problem<MSCTState>
Represents an instance of the **Minimum Sum of Completion Times (MSCT)** problem.

The MSCT problem consists in scheduling a set of jobs on a single machine to minimize the total completion time (or sum of finishing times). Each job j has:

  • a release date release[j] — the earliest time the job can start,
  • a processing time processing[j] — the duration required to complete the job.
The problem can be defined formally as: 
   minimize   ∑ C_j
   subject to start_j ≥ release_j
               start_j + processing_j = C_j
               machine processes only one job at a time

This class implements the Problem interface to be used by generic optimization solvers (A*, ACS, DDO, etc.) from the decision diagram framework.

Multiple constructors are provided to:

  • Load a problem instance from a text file,
  • Manually provide release and processing times,
  • Randomly generate a synthetic instance for testing.

Expected file format:

  • The first line contains the number of jobs, optionally followed by the known optimal value.
  • Each of the next n lines contains two integers: the release time and processing time of each job.
  • Example:
 5 215.0
 0 3
 1 2
 2 1
 0 4
 3 2
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    MSCTProblem(int n)
    Constructs a randomly generated MSCT problem instance for testing purposes.
    MSCTProblem(int[] release, int[] processing)
    Constructs an MSCT problem from explicit arrays of release and processing times, without specifying an optimal value.
    MSCTProblem(int[] release, int[] processing, Optional<Double> optimal)
    Constructs an MSCT problem from explicit arrays of release and processing times, with an optional known optimal value.
    MSCTProblem(String fname)
    Constructs an MSCT problem by reading data from a text file.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(MSCTState state, int var)
    Returns the domain of possible decisions at the current state.
    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.
    MSCTState
    initialState()
    Returns the initial state of the problem, where all jobs are unscheduled.
    double
    initialValue()
    Returns the initial cost value of the problem (always 0 at the start).
    int
    nbVars()
    Returns the number of jobs in this instance.
    Optional<Double>
    optimalValue()
    Returns the known optimal value of this instance, if available.
    String
    toString()
    Returns a string representation of this MSCT instance for debugging purposes.
    MSCTState
    transition(MSCTState state, Decision decision)
    Computes the next state resulting from scheduling a given job.
    double
    transitionCost(MSCTState state, Decision decision)
    Returns the cost of scheduling a given job from the current state.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • MSCTProblem

      public MSCTProblem(int[] release, int[] processing, Optional<Double> optimal)
      Constructs an MSCT problem from explicit arrays of release and processing times, with an optional known optimal value.
      Parameters:
      release - an array of release times for each job.
      processing - an array of processing times for each job.
      optimal - an Optional containing the known optimal solution value.

    • MSCTProblem

      public MSCTProblem(int[] release, int[] processing)
      Constructs an MSCT problem from explicit arrays of release and processing times, without specifying an optimal value.
      Parameters:
      release - an array of release times for each job.
      processing - an array of processing times for each job.

    • MSCTProblem

      public MSCTProblem(String fname) throws IOException
      Constructs an MSCT problem by reading data from a text file.

      The file must contain the number of jobs, optionally followed by the optimal value, and then one line per job with its release and processing times.

      Parameters:
      fname - the path to the file containing the problem instance.
      Throws:
      IOException - if an error occurs while reading the file.

    • MSCTProblem

      public MSCTProblem(int n)
      Constructs a randomly generated MSCT problem instance for testing purposes.
      Parameters:
      n - the number of jobs to generate.

  • Method Details

    • nbVars

      public int nbVars()
      Returns the number of jobs in this instance.
      Specified by:
      nbVars in interface Problem<MSCTState>
      Returns:
      the number of variables (jobs).

    • initialState

      public MSCTState initialState()
      Returns the initial state of the problem, where all jobs are unscheduled.
      Specified by:
      initialState in interface Problem<MSCTState>
      Returns:
      an MSCTState representing all jobs remaining and current time = 0.

    • initialValue

      public double initialValue()
      Returns the initial cost value of the problem (always 0 at the start).
      Specified by:
      initialValue in interface Problem<MSCTState>
      Returns:
      0.0

    • domain

      public Iterator<Integer> domain(MSCTState state, int var)
      Returns the domain of possible decisions at the current state.

      The domain corresponds to the indices of remaining jobs that can still be scheduled.

      Specified by:
      domain in interface Problem<MSCTState>
      Parameters:
      state - the current state.
      var - the variable index (not used here but required by the interface).
      Returns:
      an iterator over the remaining job indices.

    • transition

      public MSCTState transition(MSCTState state, Decision decision)
      Computes the next state resulting from scheduling a given job.
      Specified by:
      transition in interface Problem<MSCTState>
      Parameters:
      state - the current scheduling state.
      decision - the decision representing the next job to schedule.
      Returns:
      a new MSCTState reflecting the updated remaining jobs and current time.

    • transitionCost

      public double transitionCost(MSCTState state, Decision decision)
      Returns the cost of scheduling a given job from the current state.

      The cost corresponds to the completion time of the scheduled job.

      Specified by:
      transitionCost in interface Problem<MSCTState>
      Parameters:
      state - the current scheduling state.
      decision - the decision representing the next job to schedule.
      Returns:
      the completion time of the selected job.

    • optimalValue

      public Optional<Double> optimalValue()
      Returns the known optimal value of this instance, if available.
      Specified by:
      optimalValue in interface Problem<MSCTState>
      Returns:
      the negated optimal value wrapped in an Optional, 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<MSCTState>
      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.

    • toString

      public String toString()
      Returns a string representation of this MSCT instance for debugging purposes.
      Overrides:
      toString in class Object
      Returns:
      a string listing the release and processing times.