Class WeightedCostOverTime

  • All Implemented Interfaces:
    ConstructiveHeuristic<Permutation>

    public final class WeightedCostOverTime
    extends WeightedShortestProcessingTime

    This is an implementation of the weighted COVERT heuristic. COVERT is an abbreviation for Cost Over Time. Weighted COVERT is defined as: h(j) = (w[j]/p[j]) max{0, (1 - max(0,S(j)) / (k p[j]))}, 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[j]. The d[j] is the job's due date, T is the current time, and s[j] is any setup time of the job (for problems with setup times). The k is a parameter that can be tuned based on problem instance characteristics.

    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 Detail

      • 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:
        Constant Field Values
    • Constructor Detail

      • WeightedCostOverTime

        public WeightedCostOverTime​(SingleMachineSchedulingProblem problem,
                                    double k)
        Constructs an WeightedCostOverTime 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.
      • WeightedCostOverTime

        public WeightedCostOverTime​(SingleMachineSchedulingProblem problem)
        Constructs an WeightedCostOverTime 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.