Class MinimizeMakespan

  • All Implemented Interfaces:
    IntegerCostOptimizationProblem<Permutation>, Problem<Permutation>, SingleMachineSchedulingProblem

    public final class MinimizeMakespan
    extends Object
    implements SingleMachineSchedulingProblem
    Implements the common scheduling cost function known as makespan. The makespan of a schedule is equal to the completion time of the last job in the schedule. If the problem doesn't have release dates and setup times, then minimizing makespan is trivial since all possible permutations of the jobs has a makespan simply equal to the sum of the process times. If the problem has sequence-dependent setups, then minimizing makespan is NP-Hard and is roughly equivalent to the wandering salesperson problem.
    • Constructor Detail

      • MinimizeMakespan

        public MinimizeMakespan​(SingleMachineSchedulingProblemData instanceData)
        Constructs a single machine scheduling problem for minimizing makespan.
        Parameters:
        instanceData - An encapsulation of the job characteristics, such as processing times, etc.
    • Method Detail

      • cost

        public int cost​(Permutation candidate)
        Description copied from interface: IntegerCostOptimizationProblem
        Computes the cost of a candidate solution to the problem instance. The lower the cost, the more optimal the candidate solution.
        Specified by:
        cost in interface IntegerCostOptimizationProblem<Permutation>
        Parameters:
        candidate - The candidate solution to evaluate.
        Returns:
        The cost of the candidate solution. Lower cost means better solution.
      • minCost

        public int minCost()
        Description copied from interface: IntegerCostOptimizationProblem
        A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution. The default implementation returns Integer.MIN_VALUE.
        Specified by:
        minCost in interface IntegerCostOptimizationProblem<Permutation>
        Returns:
        A lower bound on the minimum theoretical cost of the problem instance.