Class 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 Detail

      • 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:
        Constant Field Values
      • 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:
        Constant Field Values
      • 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:
        Constant Field Values
      • 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:
        Constant Field Values
      • 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:
        Constant Field Values
      • 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:
        Constant Field Values
    • Constructor Detail

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

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