Interface SingleMachineSchedulingProblemData

  • All Known Implementing Classes:
    CommonDuedateScheduling, WeightedStaticScheduling, WeightedStaticSchedulingWithSetups

    public interface SingleMachineSchedulingProblemData

    Classes that implement single machine scheduling problems should implement this interface to enable heuristic, etc to interact with the data that defines the jobs of the scheduling instance, such as the process times, setup times (if any), due-dates, etc of the jobs.

    This interface includes methods for accessing all of the common elements of scheduling problems: processing times, due dates, release dates, weights, setup times. It also has methods for checking whether each of these (except processing times) are present. Some scheduling cost functions are influenced only by some of these, etc. Default implementations are included for all of these potential properties except for processing times, where the defaults make the obvious interpretation if that property is not present. For example, the default release date is 0, for available for scheduling right from the start of the schedule, which is the assumption made by many scheduling problems. See the various method documentation for details of defaults for the others.

    The design rationale for providing access to all of these properties, with defaults, is to have a generalized interface to scheduling problem data to enable easily mixing and matching implementations of scheduling instance generators with scheduling cost functions. For example, with this approach, we can take a scheduling problem generator for a common due date problem (which has both early and late weights) and instead optimize weighted tardiness (which doesn't care about early weights). Therefore, we have separated the scheduling cost functions from the classes that represent scheduling problem characteristics in the library.

    • Method Summary

      All Methods Instance Methods Abstract Methods Default Methods 
      Modifier and Type Method Description
      int[] getCompletionTimes​(Permutation schedule)
      Computes the completion times of all of the jobs if they were scheduled in the order defined by the specified Permutation.
      default int getDueDate​(int j)
      Gets the due date of a job, for scheduling problems that have due dates.
      default int getEarlyWeight​(int j)
      Gets the early weight of a job, for weighted scheduling problems that have early weights.
      int getProcessingTime​(int j)
      Gets the processing time of a job, which is the amount of time required by the machine to process the job.
      default int getReleaseDate​(int j)
      Gets the release date of a job, for scheduling problems that have release dates.
      default int getSetupTime​(int j)
      Gets the setup time of a job if it is the first job processed on the machine.
      default int getSetupTime​(int i, int j)
      Gets the setup time of a job if it was to immediately follow a specified job on the machine, for problems that have sequence dependent setups.
      default int getWeight​(int j)
      Gets the weight of a job, for weighted scheduling problems, where a job's weight indicates its importance or priority (higher weight implies higher priority).
      default boolean hasDueDates()
      Checks whether this single machine scheduling instance has due dates.
      default boolean hasEarlyWeights()
      Checks whether this single machine scheduling instance has early weights.
      default boolean hasReleaseDates()
      Checks whether this single machine scheduling instance has release dates.
      default boolean hasSetupTimes()
      Checks whether this single machine scheduling instance has setup times.
      default boolean hasWeights()
      Checks whether this single machine scheduling instance has weights.
      int numberOfJobs()
      Gets the number of jobs of this scheduling problem instance.
    • Method Detail

      • numberOfJobs

        int numberOfJobs()
        Gets the number of jobs of this scheduling problem instance.
        Returns:
        the number of jobs
      • getProcessingTime

        int getProcessingTime​(int j)
        Gets the processing time of a job, which is the amount of time required by the machine to process the job.
        Parameters:
        j - The index of the job, which must be in the interval: [0, numberOfJobs()).
        Returns:
        the processing time of job j.
        Throws:
        IndexOutOfBoundsException - if j < 0 or j ≥ numberOfJobs()
      • getCompletionTimes

        int[] getCompletionTimes​(Permutation schedule)
        Computes the completion times of all of the jobs if they were scheduled in the order defined by the specified Permutation. The completion times are computed according to the processing times of the jobs, as well as setup times and ready times if the problem has these.
        Parameters:
        schedule - A schedule (i.e., sequence of jobs on the machine).
        Returns:
        An array of completion times. Let C be the array of completion times. C.length must equal schedule.length(). Additionally, C[j] must be the completion time of job j (and not the completion time of the job in position j of the Permutation). That is, the indexes into C correspond to the parameter j of the getProcessingTime(int) method, and other related methods of this interface.
        Throws:
        IllegalArgumentException - if schedule.length() is not equal to numberOfJobs()
      • getDueDate

        default int getDueDate​(int j)
        Gets the due date of a job, for scheduling problems that have due dates. The meaning of a due date, and its effect on the optimization cost function, may vary by problem. See the documentation of the specific scheduling problem's cost function for details. .
        Parameters:
        j - The index of the job, which must be in the interval: [0, numberOfJobs()).
        Returns:
        the due date of job j.
        Throws:
        UnsupportedOperationException - if hasDueDates() returns false. This is the behavior if the scheduling problem definition doesn't have due dates.
        IndexOutOfBoundsException - if j < 0 or j ≥ numberOfJobs()
      • hasDueDates

        default boolean hasDueDates()
        Checks whether this single machine scheduling instance has due dates.
        Returns:
        true iff due dates are present.
      • getReleaseDate

        default int getReleaseDate​(int j)
        Gets the release date of a job, for scheduling problems that have release dates. The default implementation simply returns 0, which is appropriate for problems without release dates (i.e., problems in which all jobs are available for scheduling right at the start). You can use the hasReleaseDates() method to check whether release dates are present. .
        Parameters:
        j - The index of the job, which must be in the interval: [0, numberOfJobs()).
        Returns:
        the release date of job j.
        Throws:
        IndexOutOfBoundsException - if j < 0 or j ≥ numberOfJobs()
      • hasReleaseDates

        default boolean hasReleaseDates()
        Checks whether this single machine scheduling instance has release dates.
        Returns:
        true iff release dates are present.
      • getWeight

        default int getWeight​(int j)
        Gets the weight of a job, for weighted scheduling problems, where a job's weight indicates its importance or priority (higher weight implies higher priority). Many common scheduling problem cost functions use weights (e.g., weighted tardiness, weighted lateness, etc). The default implementation simply returns 1, which is appropriate for problems without weights (i.e., the unweighted variation of most scheduling cost functions is equivalent to the weighted version if all weights are 1). You can use the hasWeights() method to check whether weights are present.
        Parameters:
        j - The index of the job, which must be in the interval: [0, numberOfJobs()).
        Returns:
        the weight of job j.
        Throws:
        IndexOutOfBoundsException - if j < 0 or j ≥ numberOfJobs()
      • hasWeights

        default boolean hasWeights()
        Checks whether this single machine scheduling instance has weights.
        Returns:
        true iff weights are present.
      • getEarlyWeight

        default int getEarlyWeight​(int j)
        Gets the early weight of a job, for weighted scheduling problems that have early weights. For example, there are scheduling problems with a pair of weights for each job, where there is a different weight penalty for completing a job early as there is for completing it late. The default implementation simply returns 1 (i.e., the unweighted variation of cost functions involving early weights is equivalent to the weighted version if all early weights are 1). You can use the hasEarlyWeights() method to check whether early weights are present.
        Parameters:
        j - The index of the job, which must be in the interval: [0, numberOfJobs()).
        Returns:
        the early weight of job j.
        Throws:
        IndexOutOfBoundsException - if j < 0 or j ≥ numberOfJobs()
      • hasEarlyWeights

        default boolean hasEarlyWeights()
        Checks whether this single machine scheduling instance has early weights.
        Returns:
        true iff early weights are present.
      • getSetupTime

        default int getSetupTime​(int i,
                                 int j)
        Gets the setup time of a job if it was to immediately follow a specified job on the machine, for problems that have sequence dependent setups. The default simply returns 0, which is consistent with problems that don't have setup times (in those cases it is usually assumed rolled into the process time). You can use the hasSetupTimes() method to check whether setup times are present.
        Parameters:
        i - The index of the previous job in the schedule, which must be in the interval: [0, numberOfJobs()). Pass i = j for the setup time of job j if it is the first job in the schedule.
        j - The index of the job whose setup time you want, which must be in the interval: [0, numberOfJobs()).
        Returns:
        the setup time of job j if it immediately follows job i.
        Throws:
        IndexOutOfBoundsException - if j < 0 or j ≥ numberOfJobs() i < 0 or i ≥ numberOfJobs()
      • getSetupTime

        default int getSetupTime​(int j)
        Gets the setup time of a job if it is the first job processed on the machine. The default simply returns 0, which is consistent with problems that don't have setup times (in those cases it is usually assumed rolled into the process time). You can use the hasSetupTimes() method to check whether setup times are present.
        Parameters:
        j - The index of the job whose setup time you want, which must be in the interval: [0, numberOfJobs()).
        Returns:
        the setup time of job j if it is the first job processed by the machine
        Throws:
        IndexOutOfBoundsException - if j < 0 or j ≥ numberOfJobs()
      • hasSetupTimes

        default boolean hasSetupTimes()
        Checks whether this single machine scheduling instance has setup times.
        Returns:
        true iff setup times are present.