Class Montagne

  • All Implemented Interfaces:
    ConstructiveHeuristic<Permutation>

    public final class Montagne
    extends WeightedShortestProcessingTime

    This is an implementation of Montagne's heuristic heuristic. This heuristic is defined as: h(j) = (w[j]/p[j])(1 - (d[j]/Σip[i]), where w[j] is the weight of job j, p[j] is its processing time, and d[j] is job j's due date. The Σip[i] is the sum of the processing times of the remaining unscheduled jobs.

    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.