Class CommonDuedateScheduling
 All Implemented Interfaces:
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 ORLibrary 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/schedulingbenchmarks

Field Summary
Modifier and TypeFieldDescriptionstatic final int
Defines the maximum earliness weight.static final int
Defines the maximum process times.static final int
Defines the maximum tardiness weight.static final int
Defines the minimum earliness weight.static final int
Defines the minimum process times.static final int
Defines the minimum tardiness weight. 
Constructor Summary
ConstructorDescriptionCommonDuedateScheduling
(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 ORLibrary.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 ORLibrary.CommonDuedateScheduling
(String filename, int instanceNumber, double h) Constructs a common duedate scheduling problem instance by parsing an instance data file that follows the format specified in the ORLibrary of J.E. 
Method Summary
Modifier and TypeMethodDescriptionint[]
getCompletionTimes
(Permutation schedule) Computes the completion times of all of the jobs if they were scheduled in the order defined by the specified Permutation.int
getDueDate
(int j) Gets the due date of a job, for scheduling problems that have due dates.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.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).boolean
Checks whether this single machine scheduling instance has due dates.boolean
Checks whether this single machine scheduling instance has early weights.boolean
Checks whether this single machine scheduling instance has weights.int
Gets the number of jobs of this scheduling problem instance.void
Outputs a description of the instance in the format described by the ORLibrary of J.E.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.cicirello.search.problems.scheduling.SingleMachineSchedulingProblemData
getReleaseDate, getSetupTime, getSetupTime, hasReleaseDates, hasSetupTimes

Field Details

MIN_PROCESS_TIME
public static final int MIN_PROCESS_TIMEDefines 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_TIMEDefines 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_WEIGHTDefines 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_WEIGHTDefines 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_WEIGHTDefines 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_WEIGHTDefines 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 ORLibrary. 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 ORLibrary. 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 ORLibrary of J.E. Beasley. The description, along with a set of benchmark instances, is mirrored in the following GitHub repository: https://github.com/cicirello/schedulingbenchmarks
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 ORLibrary assume values of h equal to 0.2, 0.4, 0.6, and 0.8 the ORLibrary 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
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 interfaceSingleMachineSchedulingProblemData
 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 interfaceSingleMachineSchedulingProblemData
 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 interfaceSingleMachineSchedulingProblemData
 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 interfaceSingleMachineSchedulingProblemData
 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 interfaceSingleMachineSchedulingProblemData
 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 theSingleMachineSchedulingProblemData.hasWeights()
method to check whether weights are present. Specified by:
getWeight
in interfaceSingleMachineSchedulingProblemData
 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 interfaceSingleMachineSchedulingProblemData
 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 theSingleMachineSchedulingProblemData.hasEarlyWeights()
method to check whether early weights are present. Specified by:
getEarlyWeight
in interfaceSingleMachineSchedulingProblemData
 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 interfaceSingleMachineSchedulingProblemData
 Returns:
 true iff early weights are present.

toFile
Outputs a description of the instance in the format described by the ORLibrary of J.E. Beasley. The description, along with a set of benchmark instances, is mirrored in the following GitHub repository: https://github.com/cicirello/schedulingbenchmarks
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 ORLibrary 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
