Package org.ddolib.examples.msct

Class MSCTFastLowerBound

java.lang.Object
org.ddolib.examples.msct.MSCTFastLowerBound
All Implemented Interfaces:
FastLowerBound<MSCTState>
public class MSCTFastLowerBound extends Object implements FastLowerBound<MSCTState>
Provides a fast lower bound computation for the Maximum Sum of Compatible Tasks (MSCT) problem.

The MSCTFastLowerBound class estimates a lower bound on the total completion time (or cost) that can be achieved from a given partial state of the problem. This lower bound is used within search-based optimization algorithms (such as A*, ACS, or DDO) to prune suboptimal branches and guide the search toward promising solutions.

The lower bound is computed based on the remaining tasks to be scheduled and the current state of the system. It takes into account the earliest possible start time (release date) and the smallest processing time among the remaining tasks.

Computation logic:

  • Let k be the number of remaining tasks to schedule.
  • minProcessing is the smallest processing time among the remaining tasks.
  • minRelease is the smallest release time among the remaining tasks.
  • u is the maximum between state.currentTime() and minRelease.
The lower bound is then estimated as: 
     LB = k * u + minProcessing * (k * (k + 1) / 2.0)

This formula roughly estimates the minimal cumulative processing time that remains given the current schedule state.

Example:

 MSCTProblem problem = new MSCTProblem("data/MSCT/msct1.txt");
 MSCTState state = new MSCTState(...);
 MSCTFastLowerBound lb = new MSCTFastLowerBound(problem);

 double lowerBound = lb.fastLowerBound(state, Set.of(0, 1, 2));
 System.out.println("Estimated lower bound: " + lowerBound);

  • Constructor Details

    • MSCTFastLowerBound

      public MSCTFastLowerBound(MSCTProblem problem)
      Constructs a lower bound evaluator for a specific instance of the MSCT problem.
      Parameters:
      problem - the MSCTProblem instance containing the task data (processing times, release dates, etc.).

  • Method Details

    • fastLowerBound

      public double fastLowerBound(MSCTState state, Set<Integer> variables)
      Computes a fast lower bound on the total completion time (or cost) from the given state and remaining variables.

      This method evaluates how good a partial solution can potentially become by estimating the minimal additional cost required to schedule the remaining tasks.

      Specified by:
      fastLowerBound in interface FastLowerBound<MSCTState>
      Parameters:
      state - the current state of the problem, representing already scheduled tasks.
      variables - the set of remaining variables (tasks) to be scheduled.
      Returns:
      an estimated lower bound on the minimal total cost achievable from the current state.