org.cicirello.search.problems.scheduling.WeightedStaticScheduling

All Implemented Interfaces:: SingleMachineSchedulingProblemData

public final class WeightedStaticScheduling extends Object implements SingleMachineSchedulingProblemData

This class provides a representation of, and means of generating, instances of single machine scheduling problems involving weights and due dates, 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 based on that used to generate the benchmark instances for weighted tardiness 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

The Chips-n-Salsa library separates the representation of the scheduling problem instance data (e.g., processing times, weights, 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:

Vincent A. Cicirello. The Challenge of Sequence-Dependent Setups: Proposal for a Scheduling Competition Track on One Machine Sequencing Problems. Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) Workshop on Scheduling a Scheduling Competition. AAAI Press, September 2007.

Field Summary

Fields

Modifier and Type

Field

Description

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

WeightedStaticScheduling(int n, double rdd, double tf)

Generates random single machine scheduling problem instances.

WeightedStaticScheduling(int n, double rdd, double tf, long seed)

Generates random single machine scheduling problem instances.

WeightedStaticScheduling(String filename, int n, int instanceNumber)

Constructs a single machine scheduling problem instance by parsing an instance data file that follows the format specified in the OR-Library of J.E.

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

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

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 described by the OR-Library 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
getEarlyWeight, getReleaseDate, getSetupTime, getSetupTime, hasEarlyWeights, hasReleaseDates, hasSetupTimes

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:
  
  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_WEIGHT
  
  public static final int MIN_WEIGHT
  
  Defines the minimum weight. Weights are generated uniformly at random from the interval: [MIN_WEIGHT, MAX_WEIGHT].
  See Also:
  
  Constant Field Values
- 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:
  
  Constant Field Values
Constructor Details
- WeightedStaticScheduling
  
  public WeightedStaticScheduling(int n, double rdd, double tf, long seed)
  
  Generates random single machine scheduling problem instances.
  
  Parameters:
  
  n - The number of jobs in the instance, must be positive.
  
  rdd - The relative range of duedates. See the links in the class comments for an explanation of this parameter. Must be in the interval (0.0, 1.0].
  
  tf - The tardiness factor. See the links in the class comments for an explanation of this parameter. Must be in the interval [0.0, 1.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 rdd ≤ 0 or rdd > 1 or tf < 0 or tf > 0.
- WeightedStaticScheduling
  
  public WeightedStaticScheduling(int n, double rdd, double tf)
  
  Generates random single machine scheduling problem instances.
  
  Parameters:
  
  n - The number of jobs in the instance, must be positive.
  
  rdd - The relative range of duedates. See the links in the class comments for an explanation of this parameter. Must be in the interval (0.0, 1.0].
  
  tf - The tardiness factor. See the links in the class comments for an explanation of this parameter. Must be in the interval [0.0, 1.0].
  
  Throws:
  
  IllegalArgumentException - if n is not positive, or rdd ≤ 0 or rdd > 1 or tf < 0 or tf > 0.
- WeightedStaticScheduling
  
  public WeightedStaticScheduling(String filename, int n, int instanceNumber) throws FileNotFoundException
  
  Constructs a single machine 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 format from the benchmark library is a bit unusual. Each file contains many instances. There is no labeling info, so you need to know the number of jobs, n, contained in the file. The first instance is listed first with n process times, followed by n weights, followed by n duedates. This is then followed by second instance (n process times, n weights, and then n duedates), etc, with no instance separators.
  
  Parameters:
  
  filename - The name of the file containing the instances, with path.
  
  n - The number of jobs in one instance. Behavior is undefined if n is inconsistent with the actual number of jobs of the instances contained in the file.
  
  instanceNumber - The number of the instance to parse, where the first instance is instance 0. Behavior is undefined if instanceNumber is too high.
  
  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.
- toFile
  
  public void toFile(String filename) throws FileNotFoundException
  
  Outputs a description of the instance data 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 only different with that format is that this stores only the one instance in the file. But for consistency with the original format, you do need to know the number of jobs for the instance (or you can determine this by counting number of integers in the file and dividing by 3.
  
  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

Class WeightedStaticScheduling

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface org.cicirello.search.problems.scheduling.SingleMachineSchedulingProblemData

Field Details

MIN_PROCESS_TIME

MAX_PROCESS_TIME

MIN_WEIGHT

MAX_WEIGHT

Constructor Details

WeightedStaticScheduling

WeightedStaticScheduling

WeightedStaticScheduling

Method Details

getCompletionTimes

numberOfJobs

getProcessingTime

getDueDate

hasDueDates

getWeight

hasWeights

toFile