Class ApparentTardinessCostSetupAdjusted

java.lang.Object
org.cicirello.search.problems.scheduling.WeightedShortestProcessingPlusSetupTime
org.cicirello.search.problems.scheduling.ApparentTardinessCostSetupAdjusted
All Implemented Interfaces:
ConstructiveHeuristic<Permutation>

public final class ApparentTardinessCostSetupAdjusted extends WeightedShortestProcessingPlusSetupTime

This is an implementation of a variation of the Apparent Tardiness Cost (ATC) heuristic, with a simple adjustment for setup times for problems with sequence-dependent setups. Note that this is NOT the Apparent Tardiness Cost with Setups (ATCS) heuristic, although that heuristic can also be found in the library.

ATC is defined as: h(j) = (w[j]/p[j]) exp( -max(0,S(j)) / (k p̄) ), where w[j] is the weight of job j, p[j] is its processing time, and S(j) is a calculation of the slack of job j where slack S(j) is d[j] - T - p[j] - s[i][j]. The d[j] is the job's due date, T is the current time, and s[i][j] is setup time of the job if it follows job i on the machine (for problems with setup times). The k is a parameter that can be tuned based on problem instance characteristics, and p̄ is the average processing time of remaining unscheduled jobs.

Our simple adjustment for setup time is as follows: h(j) = (w[j]/(p[j]+s[i][j])) exp( -max(0,S(j)) / (k p̄) ).

The constant MIN_H defines the minimum value the heuristic will return, preventing h(j)=0 in support of stochastic sampling algorithms for which h(j)=0 is problematic. This implementation returns max( MIN_H, h(j)), where MIN_H is a small non-zero value.

  • Field Details

    • MIN_H

      public static final double MIN_H
      The minimum heuristic value. If the heuristic value as calculated is lower than MIN_H, then MIN_H is used as the heuristic value. The reason is related to the primary purpose of the constructive heuristics in the library: heuristic guidance for stochastic sampling algorithms, which assume positive heuristic values (e.g., an h of 0 would be problematic).
      See Also:
  • Constructor Details

    • ApparentTardinessCostSetupAdjusted

      public ApparentTardinessCostSetupAdjusted(SingleMachineSchedulingProblem problem, double k)
      Constructs an ApparentTardinessCostSetupAdjusted heuristic.
      Parameters:
      problem - The instance of a scheduling problem that is the target of the heuristic.
      k - A parameter to the heuristic, which must be positive. Typical good values are in the interval [1.0, 4.0] but it is not limited to that interval.
      Throws:
      IllegalArgumentException - if problem.hasDueDates() returns false.
      IllegalArgumentException - if k ≤ 0.0.
    • ApparentTardinessCostSetupAdjusted

      public ApparentTardinessCostSetupAdjusted(SingleMachineSchedulingProblem problem)
      Constructs an ApparentTardinessCostSetupAdjusted heuristic. Uses a default of k=2.
      Parameters:
      problem - The instance of a scheduling problem that is the target of the heuristic.
      Throws:
      IllegalArgumentException - if problem.hasDueDates() returns false.
  • Method Details