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

Class WeightedStaticSchedulingWithSetups

java.lang.Object
org.cicirello.search.problems.scheduling.WeightedStaticSchedulingWithSetups
All Implemented Interfaces:
SingleMachineSchedulingProblemData
public final class WeightedStaticSchedulingWithSetups extends Object implements SingleMachineSchedulingProblemData
This class provides a representation of, and means of generating, instances of single machine scheduling problems involving weights, due dates, and sequence-dependent setup times, but without release dates (i.e., all jobs are released at the start of the problem at time 0, thus, the term "static" in the class name).

This class generates instances using a procedure largely based upon that which was used to generate the benchmark instances for weighted tardiness scheduling with sequence-dependent setups described in the following paper, and with instances now available at the following Harvard Dataverse site:

That approach was based on the description of generating instances for that scheduling problem described in the following paper:

  • Lee, Y. H., Bhaskaran, K., and Pinedo, M. A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Transactions, 29:45–52, 1997.

The Chips-n-Salsa library separates the representation of the scheduling problem instance data (e.g., processing times, setup times, etc) from the implementations of scheduling cost functions deliberately to enable defining additional problems (i.e., different cost functions to optimize) using the same scheduling problem generators. This is very much like what was suggested in the following paper:

This is a reimplementation of the above problem instance generator, using a more efficient random number generator, and a better estimator of makespan (which is used in determining the random due dates).

The constructors that generate random scheduling problem instances take four parameters: n, τ, r, and η. These parameters are defined as follows. The number of jobs in the instance is n. τ controls due date tightness, and r controls the due date range. η controls the severity of the setup times. The values of τ, r, and η are required to be in the interval [0.0, 1.0].

Instances are then generated randomly as follows. The processing time p[j] of job j is generated uniformly at random from: [50, 150]. The mean processing time is thus: p̄ = 100. The weight w[j] of job j is generated uniformly at random from: [0, 10]. To generate the random setup times, first define the mean setup time as: s̄ = ηp̄. The setup time s[i][j] of job j if it immediately follows job i on the machine is generated uniformly at random from: [0, 2s̄]. To generate the random due dates, first define the mean due date d̄ as d̄ = (1 - τ)Cmax, where Cmax is an estimate of makespan (see below). With probability τ, we generate the due date d[j] of job j uniformly at random from the interval: [d̄ - rd̄, d̄]; and with probability (1 - τ), we generate it uniformly at random from [d̄, d̄ + r(Cmax - d̄)]. The makespan, Cmax, is estimated based on Lee et al's (see references above) estimate: Cmax = n(p̄ + βs̄), where β ≤ 1.0. Lee et al's rationale for including the β factor is that the optimal schedule will tend to favor job transitions that involve lower than average setups. Lee et al's paper provided data on how β varies for a couple specific problem sizes n. They don't derive a general rule, however, an examination of the limited data in their paper shows that β appears to decrease logarithmically in n. We fit a curve to the couple data points available in Lee et al's paper and estimate: β = -0.097 ln(n) + 0.6876, but we don't allow β to fall below 0.2.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    AVERAGE_PROCESS_TIME
    Defines the average process time.
    static final int
    MAX_PROCESS_TIME
    Defines the maximum process times.
    static final int
    MAX_WEIGHT
    Defines the maximum weight.
    static final int
    MIN_PROCESS_TIME
    Defines the minimum process times.
    static final int
    MIN_WEIGHT
    Defines the minimum weight.

  • Constructor Summary

    Constructors
    Constructor
    Description
    WeightedStaticSchedulingWithSetups(int n, double tau, double r, double eta)
    Generates random single machine scheduling problem instances.
    WeightedStaticSchedulingWithSetups(int n, double tau, double r, double eta, long seed)
    Generates random single machine scheduling problem instances.
    WeightedStaticSchedulingWithSetups(String filename)
    Constructs a single machine scheduling problem instance by parsing an instance data file that follows the format specified in the following paper, with instances available at the following link: Vincent A.

  • 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.
    int
    getDueDate(int j)
    Gets the due date of a job, for scheduling problems that have due dates.
    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
    getSetupTime(int j)
    Gets the setup time of a job if it is the first job processed on the machine.
    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.
    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
    hasDueDates()
    Checks whether this single machine scheduling instance has due dates.
    boolean
    hasSetupTimes()
    Checks whether this single machine scheduling instance has setup times.
    boolean
    hasWeights()
    Checks whether this single machine scheduling instance has weights.
    int
    numberOfJobs()
    Gets the number of jobs of this scheduling problem instance.
    void
    toFile(String filename)
    Outputs a description of the instance data in the format based on that described in:
    void
    toFile(String filename, int instanceNumber)
    Outputs a description of the instance data in the format based on that described in:

    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

    getEarlyWeight, getReleaseDate, hasEarlyWeights, hasReleaseDates

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

    • AVERAGE_PROCESS_TIME

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

    • MIN_WEIGHT

      public static final int MIN_WEIGHT
      Defines the minimum weight. Weights are generated uniformly at random from the interval: [MIN_WEIGHT, MAX_WEIGHT]. This follows the instance generation described by Lee, et al, but has since been criticized since it implies some jobs are excluded from some cost functions (e.g., weighted tardiness), although those jobs can still be critical to the schedule due to how setup times are generated.
      See Also:

    • MAX_WEIGHT

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

  • Constructor Details

    • WeightedStaticSchedulingWithSetups

      public WeightedStaticSchedulingWithSetups(int n, double tau, double r, double eta, long seed)
      Generates random single machine scheduling problem instances.
      Parameters:
      n - The number of jobs in the instance, must be positive.
      tau - The due date tightness, in the interval [0.0, 1.0]. The higher the value of tau, the tighter are the due dates (e.g., if tau=1.0, then all due dates will be 0, i.e., at the start of the schedule).
      r - The due date range, in the interval [0.0, 1.0]. The higher the value of r, the wider the range of due dates. For example, if r=0, all due dates will be the same.
      eta - The setup time severity, in the interval [0.0, 1.0]. The higher the value of eta, the greater the impact of setup times on scheduling difficulty. For example, if eta=0, then all setup times are 0.
      seed - A seed for the random number generator, to enable easily generating the same problem instance. If all parameters, including the seed are the same, then the same instance will be generated.
      Throws:
      IllegalArgumentException - if n is not positive, or if any of tau, eta, or r are not in the interval [0.0, 1.0].

    • WeightedStaticSchedulingWithSetups

      public WeightedStaticSchedulingWithSetups(int n, double tau, double r, double eta)
      Generates random single machine scheduling problem instances.
      Parameters:
      n - The number of jobs in the instance, must be positive.
      tau - The due date tightness, in the interval [0.0, 1.0]. The higher the value of tau, the tighter are the due dates (e.g., if tau=1.0, then all due dates will be 0, i.e., at the start of the schedule).
      r - The due date range, in the interval [0.0, 1.0]. The higher the value of r, the wider the range of due dates. For example, if r=0, all due dates will be the same.
      eta - The setup time severity, in the interval [0.0, 1.0]. The higher the value of eta, the greater the impact of setup times on scheduling difficulty. For example, if eta=0, then all setup times are 0.
      Throws:
      IllegalArgumentException - if n is not positive, or if any of tau, eta, or r are not in the interval [0.0, 1.0].

    • WeightedStaticSchedulingWithSetups

      public WeightedStaticSchedulingWithSetups(String filename) throws FileNotFoundException
      Constructs a single machine scheduling problem instance by parsing an instance data file that follows the format specified in the following paper, with instances available at the following link:

      Note that the paper above describes a weighted tardiness scheduling problem, but the instance data (process and setup times, weights, duedates) can also be used with other scheduling objective functions

      Parameters:
      filename - The name of the data instance file, with path.
      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

  • Method Details

    • getCompletionTimes

      public int[] getCompletionTimes(Permutation schedule)
      Description copied from interface: SingleMachineSchedulingProblemData
      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.
      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.

    • getSetupTime

      public int getSetupTime(int i, int j)
      Description copied from interface: SingleMachineSchedulingProblemData
      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 SingleMachineSchedulingProblemData.hasSetupTimes() method to check whether setup times are present.
      Specified by:
      getSetupTime in interface SingleMachineSchedulingProblemData
      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.

    • getSetupTime

      public int getSetupTime(int j)
      Description copied from interface: SingleMachineSchedulingProblemData
      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 SingleMachineSchedulingProblemData.hasSetupTimes() method to check whether setup times are present.
      Specified by:
      getSetupTime in interface SingleMachineSchedulingProblemData
      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

    • hasSetupTimes

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

    • toFile

      public void toFile(String filename) throws FileNotFoundException
      Outputs a description of the instance data in the format based on that described in:

      Vincent A. Cicirello. Weighted Tardiness Scheduling with Sequence-Dependent Setups: A Benchmark Library. Technical Report, Intelligent Coordination and Logistics Laboratory, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, February 2003.

      The data as output by this method varies from that format in that it does not output the "Generator Parameters" section. Instead, it has the "Begin Generator Parameters" and the "End Generator Parameters" block markers, but an empty block. The constructor of this class that takes an instance data file as input can correctly parse both the original and this modified format.

      This method will output a -1 for the problem instance number. If you wish to have meaningful problem instance numbers, use the version of the method that includes a parameter for this.

      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

    • toFile

      public void toFile(String filename, int instanceNumber) throws FileNotFoundException
      Outputs a description of the instance data in the format based on that described in:

      Vincent A. Cicirello. Weighted Tardiness Scheduling with Sequence-Dependent Setups: A Benchmark Library. Technical Report, Intelligent Coordination and Logistics Laboratory, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, February 2003.

      The data as output by this method varies from that format in that it does not output the "Generator Parameters" section. Instead, it has the "Begin Generator Parameters" and the "End Generator Parameters" block markers, but an empty block. The constructor of this class that takes an instance data file as input can correctly parse both the original and this modified format.

      Parameters:
      filename - The name of a file for the output.
      instanceNumber - An id for the problem instance.
      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