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

Class CommonDuedateScheduling

java.lang.Object
org.cicirello.search.problems.scheduling.CommonDuedateScheduling
All Implemented Interfaces:
SingleMachineSchedulingProblemData
public final class CommonDuedateScheduling extends Object implements SingleMachineSchedulingProblemData
This class represents and generates instances of a common duedate scheduling problem, in which all jobs have both an earliness weight and a tardiness weight, and share a common duedate. The library treats scheduling cost functions independently from the job data, however, the only commonly used cost function that really makes sense with this combination of job characteristics is the sum of weighted earliness plus weighted tardiness, implemented in the class WeightedEarlinessTardiness. Consult the documentation of that class for details. There is nothing to prevent you, however, from defining a scheduling problem involving the CommonDuedateScheduling job characteristics with a different scheduling cost function. However, be aware that the getCompletionTimes(org.cicirello.permutations.Permutation) method is implemented to assume the WeightedEarlinessTardiness cost function, in that it computes the optimal delay to the start of the schedule relative to the permutation it is passed as a parameter. That delay is likely inappropriate for other cost functions.

This class generates instances using a procedure based on that used to generate the benchmark instances for common duedate scheduling that are available in the OR-Library of J.E. Beasley. Note that this is NOT the implementation that generated those instances. Rather, this implementation is based on the description of that generator. That description, along with a set of benchmark instances, is mirrored in the following GitHub repository: https://github.com/cicirello/scheduling-benchmarks

  • Field Details

    • MIN_PROCESS_TIME

      public static final int MIN_PROCESS_TIME
      Defines the minimum process times. Process times are generated uniformly at random from the interval: [MIN_PROCESS_TIME, MAX_PROCESS_TIME].
      See Also:

    • MAX_PROCESS_TIME

      public static final int MAX_PROCESS_TIME
      Defines the maximum process times. Process times are generated uniformly at random from the interval: [MIN_PROCESS_TIME, MAX_PROCESS_TIME].
      See Also:

    • MIN_EARLINESS_WEIGHT

      public static final int MIN_EARLINESS_WEIGHT
      Defines the minimum earliness weight. Weights are generated uniformly at random from the interval: [MIN_EARLINESS_WEIGHT, MAX_EARLINESS_WEIGHT].
      See Also:

    • MAX_EARLINESS_WEIGHT

      public static final int MAX_EARLINESS_WEIGHT
      Defines the maximum earliness weight. Weights are generated uniformly at random from the interval: [MIN_EARLINESS_WEIGHT, MAX_EARLINESS_WEIGHT].
      See Also:

    • MIN_TARDINESS_WEIGHT

      public static final int MIN_TARDINESS_WEIGHT
      Defines the minimum tardiness weight. Weights are generated uniformly at random from the interval: [MIN_TARDINESS_WEIGHT, MAX_TARDINESS_WEIGHT].
      See Also:

    • MAX_TARDINESS_WEIGHT

      public static final int MAX_TARDINESS_WEIGHT
      Defines the maximum tardiness weight. Weights are generated uniformly at random from the interval: [MIN_TARDINESS_WEIGHT, MAX_TARDINESS_WEIGHT].
      See Also:

  • Constructor Details

    • CommonDuedateScheduling

      public CommonDuedateScheduling(int n, double h)
      Constructs a random instance of common duedate scheduling using an implementation of a process based on that approach used to generate the instances from the OR-Library. The process times, earliness weights, and tardiness weights are generated uniformly at random in the intervals defined by the class constants. The common duedate is determined based on the parameter h. Specifically, the common duedate for the instance is set to: floor(h * SumOfP), where SumOfP is the sum of the processing times of the jobs.
      Parameters:
      n - The number of jobs for the instance, n ≥ 0.
      h - Controls the tightness of the common duedate for the instance, as a percentage of the sum of process times, 0.0 ≤ h ≤ 1.0.
      Throws:
      IllegalArgumentException - if n < 0 or h < 0 or h > 1

    • CommonDuedateScheduling

      public CommonDuedateScheduling(int n, double h, long seed)
      Constructs a random instance of common duedate scheduling using an implementation of a process based on that approach used to generate the instances from the OR-Library. The process times, earliness weights, and tardiness weights are generated uniformly at random in the intervals defined by the class constants. The common duedate is determined based on the parameter h. Specifically, the common duedate for the instance is set to: floor(h * SumOfP), where SumOfP is the sum of the processing times of the jobs.
      Parameters:
      n - The number of jobs for the instance, n ≥ 0.
      h - Controls the tightness of the common duedate for the instance, as a percentage of the sum of process times, 0.0 ≤ h ≤ 1.0.
      seed - The seed for the random number generator. Specifying a seed enables generating the same instance (e.g., same combination of n, h, and seed will lead to the same problem instance).
      Throws:
      IllegalArgumentException - if n < 0 or h < 0 or h > 1

    • CommonDuedateScheduling

      public CommonDuedateScheduling(String filename, int instanceNumber, double h) throws FileNotFoundException
      Constructs a common duedate scheduling problem instance by parsing an instance data file that follows the format specified in the OR-Library of J.E. Beasley. The description, along with a set of benchmark instances, is mirrored in the following GitHub repository: https://github.com/cicirello/scheduling-benchmarks

      The first line of the file has the number of instances in the file. This is then followed by the data for each instance in the following form. Number of jobs, n, for the instance on a line by itself. This is then followed by n lines, one for each job, where the line consists of 3 integers: process time, earliness weight, and tardiness weight. These are separated by whitespace. Don't assume any specific number of whitespace characters. This seems to vary. Lines may also begin with whitespace.

      The h parameter (see documentation of constructors that generate instances) is not specified in the file, and each instance in a file can be used to specify multiple benchmark instances with varying degrees of duedate tightness. The instances in the OR-Library assume values of h equal to 0.2, 0.4, 0.6, and 0.8 the OR-Library provides bounds on optimal solutions for those values of h), but you can potentially define additional instances using additional values of h. The only constraint on h is: 0.0 ≤ h ≤ 1.0. It is used to define the common duedate for the instance as a percentage of the sum of process times.

      Parameters:
      filename - The name of the file containing the instances, with path.
      instanceNumber - The number of the instance to parse, where the first instance is instance 0. The instanceNumber must be less than the number of instances indicated by the first line of the file.
      h - Controls the tightness of the common duedate for the instance, as a percentage of the sum of process times, 0.0 ≤ h ≤ 1.0.
      Throws:
      FileNotFoundException - if the named file does not exist, is a directory rather than a regular file, or for some other reason cannot be opened for reading.
      IllegalArgumentException - if instanceNumber is negative or greater than or equal to the number of instances in the file.
      IllegalArgumentException - if h < 0 or h > 1

  • Method Details

    • getCompletionTimes

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

      This implementation assumes that the cost function for the problem is sum of weighted earliness and weighted tardiness (reasonable assumption since instances have both early and tardy weights, and this is the cost function of the generator this is based upon). The reason this assumption is important is that when computing completion times, this implementation does not necessarily start the first job in the permutation at time 0. Instead, it delays the start of the schedule to minimize the cost function weighted earliness plus weighted tardiness. This delay is easy to compute for any fixed ordering of the jobs, such as specified by a given permutation.

      Specified by:
      getCompletionTimes in interface SingleMachineSchedulingProblemData
      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 SingleMachineSchedulingProblemData.getProcessingTime(int) method, and other related methods of this interface.

    • numberOfJobs

      public int numberOfJobs()
      Description copied from interface: SingleMachineSchedulingProblemData
      Gets the number of jobs of this scheduling problem instance.
      Specified by:
      numberOfJobs in interface SingleMachineSchedulingProblemData
      Returns:
      the number of jobs

    • getProcessingTime

      public int getProcessingTime(int j)
      Description copied from interface: SingleMachineSchedulingProblemData
      Gets the processing time of a job, which is the amount of time required by the machine to process the job.
      Specified by:
      getProcessingTime in interface SingleMachineSchedulingProblemData
      Parameters:
      j - The index of the job, which must be in the interval: [0, numberOfJobs()).
      Returns:
      the processing time of job j.

    • getDueDate

      public int getDueDate(int j)
      Description copied from interface: SingleMachineSchedulingProblemData
      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. .
      Specified by:
      getDueDate in interface SingleMachineSchedulingProblemData
      Parameters:
      j - The index of the job, which must be in the interval: [0, numberOfJobs()).
      Returns:
      the due date of job j.

    • hasDueDates

      public boolean hasDueDates()
      Description copied from interface: SingleMachineSchedulingProblemData
      Checks whether this single machine scheduling instance has due dates.
      Specified by:
      hasDueDates in interface SingleMachineSchedulingProblemData
      Returns:
      true iff due dates are present.

    • getWeight

      public int getWeight(int j)
      Description copied from interface: SingleMachineSchedulingProblemData
      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 SingleMachineSchedulingProblemData.hasWeights() method to check whether weights are present.
      Specified by:
      getWeight in interface SingleMachineSchedulingProblemData
      Parameters:
      j - The index of the job, which must be in the interval: [0, numberOfJobs()).
      Returns:
      the weight of job j.

    • hasWeights

      public boolean hasWeights()
      Description copied from interface: SingleMachineSchedulingProblemData
      Checks whether this single machine scheduling instance has weights.
      Specified by:
      hasWeights in interface SingleMachineSchedulingProblemData
      Returns:
      true iff weights are present.

    • getEarlyWeight

      public int getEarlyWeight(int j)
      Description copied from interface: SingleMachineSchedulingProblemData
      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 SingleMachineSchedulingProblemData.hasEarlyWeights() method to check whether early weights are present.
      Specified by:
      getEarlyWeight in interface SingleMachineSchedulingProblemData
      Parameters:
      j - The index of the job, which must be in the interval: [0, numberOfJobs()).
      Returns:
      the early weight of job j.

    • hasEarlyWeights

      public boolean hasEarlyWeights()
      Description copied from interface: SingleMachineSchedulingProblemData
      Checks whether this single machine scheduling instance has early weights.
      Specified by:
      hasEarlyWeights in interface SingleMachineSchedulingProblemData
      Returns:
      true iff early weights are present.

    • toFile

      public void toFile(String filename) throws FileNotFoundException
      Outputs a description of the instance in the format described by the OR-Library of J.E. Beasley. The description, along with a set of benchmark instances, is mirrored in the following GitHub repository: https://github.com/cicirello/scheduling-benchmarks

      The first line of the file that this produces has the number of instances in the file, which will be equal to 1 since this only outputs a single instance. Although this may seem unnecessary, it is included to enable using the same parser for the files from the OR-Library as well as for those generated by this method. The second line indicates the number of jobs n. This is then followed by n lines, one for each job, where the line consists of 3 integers: process time, earliness weight, and tardiness weight. These are separated by whitespace.

      Parameters:
      filename - The name of a file for the output.
      Throws:
      FileNotFoundException - If the given string does not denote an existing, writable regular file and a new regular file of that name cannot be created, or if some other error occurs while opening or creating the file