Module org.cicirello.chips_n_salsa
Package org.cicirello.search.problems.scheduling

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

    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 Details

    • 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.