Class WeightedShortestProcessingTimeLateOnly

  • All Implemented Interfaces:
    ConstructiveHeuristic<Permutation>

    public final class WeightedShortestProcessingTimeLateOnly
    extends WeightedShortestProcessingTime
    This is an implementation of the weighted shortest process time heuristic. There are two variations of the weighted shortest processing time heuristic. The basic form (implemented in WeightedShortestProcessingTime) is defined as: h(j) = w[j] / p[j], where w[j] is the weight of job j, and p[j] is its processing time. However, for some scheduling cost functions, performance is improved if the heuristic is modified as follows. If the job j is already late (i.e., its due date d[j] < T, where T is the current time), then its heuristic value is: h(j) = w[j] / p[j], just like in the basic version. Otherwise, if the due date hasn't passed yet, then h(j) = 0. This implementation alters this definition slightly as: If job j is already late, then h(j) = max( MIN_H, w[j] / p[j]), where MIN_H is a small non-zero value. If the job j is not yet late, then h(j) = MIN_H. For deterministic construction of a schedule, this adjustment is unnecessary. However, for stochastic sampling algorithms it is important for the heuristic to return positive values.