Package org.ddolib.examples.smic

Class SMICFastLowerBound

java.lang.Object
org.ddolib.examples.smic.SMICFastLowerBound
All Implemented Interfaces:
FastLowerBound<SMICState>
public class SMICFastLowerBound extends Object implements FastLowerBound<SMICState>
The SMICFastLowerBound class provides a fast and simple estimation of the lower bound of the remaining cost (or completion time) in the Single Machine with Inventory Constraint (SMIC) scheduling problem.

This lower bound is computed based on the processing times and release dates of the remaining jobs to be scheduled in a given state of the search process. It is intended to provide a quick and computationally inexpensive approximation to guide search algorithms such as DDO (Decision Diagram Optimization) or ACS (Anytime Column Search).

Computation principle:

  • The method accumulates the total processing time of all remaining jobs.
  • It also identifies the earliest release time among these jobs.
  • The lower bound is then the sum of these processing times plus a correction based on the difference between the earliest release date and the current time.

The bound does not attempt to be exact but rather provides a quick estimation to help pruning suboptimal branches in the search tree.

See Also:

  • Constructor Details

    • SMICFastLowerBound

      public SMICFastLowerBound(SMICProblem problem)
      Constructs a fast lower bound estimator for the given SMIC problem.
      Parameters:
      problem - the SMICProblem instance containing job data such as processing times and release dates

  • Method Details

    • fastLowerBound

      public double fastLowerBound(SMICState state, Set<Integer> variables)
      Computes a fast lower bound for the current search state.

      The lower bound is estimated as: 

           LB = (min(0, minRelease - currentTime)) + sum(processingTimes)
      where:
      • minRelease is the smallest release time among the remaining jobs,
      • currentTime is the current machine time in the state,
      • sum(processingTimes) is the total processing time of all remaining jobs.
      Specified by:
      fastLowerBound in interface FastLowerBound<SMICState>
      Parameters:
      state - the current SMICState, representing the partial schedule
      variables - the set of remaining decision variables (unused in this heuristic)
      Returns:
      a lower bound estimate of the remaining cost or completion time