Package org.ddolib.examples.msct

Class MSCTDominance

java.lang.Object
org.ddolib.examples.msct.MSCTDominance
All Implemented Interfaces:
Dominance<MSCTState>
public class MSCTDominance extends Object implements Dominance<MSCTState>
Implements the dominance relation for the Maximum Sum of Compatible Tasks (MSCT) problem.

This class defines how two states of the MSCT problem can be compared in terms of dominance. In this context, a state state1 is said to be dominated or equal to another state state2 if both states have the same set of remaining jobs to schedule, and state2 achieves the same or an earlier current time (i.e., a better schedule in terms of completion time).

The dominance relation is used in search algorithms (such as DDO or A*) to prune suboptimal states — if one state dominates another, the dominated state can be safely discarded without affecting optimality.

Example:

 MSCTState s1 = new MSCTState(remainingJobs1, 10);
 MSCTState s2 = new MSCTState(remainingJobs1, 8);

 MSCTDominance dominance = new MSCTDominance();
 boolean result = dominance.isDominatedOrEqual(s1, s2); // true, since s2.currentTime() is less than s1.currentTime()

  • Constructor Details

    • MSCTDominance

      public MSCTDominance()

  • Method Details

    • getKey

      public Integer getKey(MSCTState state)
      Returns a key used for grouping states before applying dominance checks.

      In this simple implementation, all states share the same key (always 0), meaning that the dominance check can potentially compare any two states. This can be customized for efficiency in larger problems.

      Specified by:
      getKey in interface Dominance<MSCTState>
      Parameters:
      state - the state from which to extract the key.
      Returns:
      an integer key representing the group of comparable states (always 0 here).

    • isDominatedOrEqual

      public boolean isDominatedOrEqual(MSCTState state1, MSCTState state2)
      Checks whether the first state state1 is dominated or equal to the second state state2.

      A state state1 is dominated by state2 if:

      • Both states have the same set of remaining jobs to schedule, and
      • The current time of state2 is less than or equal to that of state1.
      This indicates that state2 represents a better (or equivalent) scheduling situation, making state1 redundant in the search process.
      Specified by:
      isDominatedOrEqual in interface Dominance<MSCTState>
      Parameters:
      state1 - the first state to test for dominance.
      state2 - the second state, potentially dominating the first.
      Returns:
      true if state1 is dominated or equal to state2; false otherwise.