An Instance Generator for the Project Scheduling Problem


An instance generator is an easily parameterizable program which derive automatically instances for a problem. Using a problem generator removes the opportunity to hand-tune algorithms to a particular instance, therefore allowing a larger fairness when comparing algorithms. The predictive power of the results for the problem class as a whole is increased.

This page describes an instance generator developed in Java for the Project Scheduling Problem defined here. We must set several parameters such as the number of tasks, the number of employees, etc in order to generate a new instance.

The following sections deal with different aspects of the instance generator. First, we detail the operation of the generator. Then, we define the syntax of the configuration files. Next, we present some instructions to work with the generator and some sample configuration files. Finally, we show the download instructions.


The components of an instance of the PSP are: employees, tasks, skills, and the task precedence graph (TPG). Each of these components have several parameters that the instance generator has to decide. Specifically, with respect to the skills, the generator has to decide how many different skills has the instance. With respect to the employees it must propose the number of them, and for each employee the salary and the possesed skills. Finally, concerning the tasks, the generator must propose the number of them, the TPG, and for each one the cost and the required skills to perform it.

As we observe, there are two kinds of values to be generated: single numeric values and sets (the TPG can be considered a set, the set of edges). For the numeric values the generator samples a probability distribution given by the user. In the case of sets, the user provides a probability distribution for the cardinality (a numeric value) and then, the elements of the set are randomly chosen from its superset (the probability of an element of being chosen is similar for all the elements of the superset). Therefore, all the values are reduced to numeric values, so the user has only to give probability distributions to sample these numbers.

The set of edges of the TPG is a special case: we do not specify a distribution for the cardinality directly, but for the ratio edges/vertices, that is, the generated numeric value is multiplied by the number of tasks to get the number of edges of the TPG.

The maximum dedication of the employees is not part of the instance itself, but a part of the optimization problem. For this reason the values for this parameter are not generated.

All the probability distributions are specified in a configuration file. This file is a plain text file (whose format will be defined in the next section) containing attribute-value pairs. The instance generator reads the configuration file and then generates the skills, the tasks, the TPG, and the employees, in that order. For each task it generates the effort value and the required skill set. For each employee it generates the salary and the possessed skill set. The pseudocode of the instance generator is shown in Figure 1.

Figure 1. Pseudocode of the instance generator.

Configuration file syntax

The configuration file is composed of attribute-value pairs separated by an equal symbol (=). We can also include comment lines by beginning the line with a sharp (#) symbol. This file is parsed by the load method of the Properties class in the java.util package, so you can get more information about the format of the file in the Java web page. In the next paragraphs we explain the different attributes that can appear in a configuration file and the possible values for each of them.

Each parameter of the instance has a key name in the configuration file that we can see in the Table 1. The value of a key name is the name of a probability distribution (used to generate the value of the parameter). The probability distributions have parameters that are specified with additional key-value pairs with the form: <key-name>.parameter.<param> = <value>. We can see a sample file in Figure 2. The attributes begining with employee.skill in the sample file refer to the possesed skills of the employees. The probability distribution used to generate de values is UniformInt and it has two parameters: minvalue (set to 6) and maxvalue (set to 7). When this distribution is sampled it generates an integer number in the interval [6,7], that is, it chooses between 6 and 7 with probability 0.5, so the number of skills of the employees is 6 or 7. These skills are choosen from the set of ten different skills available (see attributes with prefix skill.number).

Key name Parameter
Number of tasks
Effort of the tasks
Required skills
Number of employees
Salary of the employees
Possesed skills
Ratio edges/vertices of the TPG
Number of skills
Table 1. Key names of the configuration file and their associated parameter.

# Config File for the Instance Generator

task.number = UniformInt
task.number.parameter.minvalue = 30
task.number.parameter.maxvalue = 30

task.cost = Round
task.cost.parameter.distribution = Normal = 10
task.cost.parameter.distribution.parameter.sigma = 5

task.skill = UniformInt
task.skill.parameter.minvalue = 2
task.skill.parameter.maxvalue = 3

graph.e-v-rate = Normal = 1.5
graph.e-v-rate.parameter.sigma = 0.5

employee.number = UniformInt
employee.number.parameter.minvalue = 15
employee.number.parameter.maxvalue = 15

employee.salary = Normal = 10000
employee.salary.parameter.sigma = 1000

employee.skill = UniformInt
employee.skill.parameter.minvalue = 6
employee.skill.parameter.maxvalue = 7

skill.number = UniformInt
skill.number.parameter.minvalue = 10
skill.number.parameter.maxvalue = 10
Figure 2. A sample input configuration file for the instance generator.

To end the description of the configuration file syntax we have to specify the probability distributions that can be employed and their parameters. This information is summarized in Table 2.

Distribution Name Parameters Description
Uniform (integers) UniformInt
Minimum value
Maximum value
Uniform (reals) Uniform
Minimum value
Maximum value
Normal Normal
Standard deviation
Rounding constructor Round
Distribution to round
Table 2. Probability distributions.

The difference between UniformInt and Uniform is the set where the distribution is defined. In the first case the sampling generates an integer number between minvalue and maxvalue and in the second the result is a real number in the same interval. The last distribution in the table is not really a distribution, it is a round function. It has only one parameter: a probability distribution (whose parameters are specified as in the sample file). After sampling this probability distribution it rounds the result. For this reason, the Round "distribution" can be thought as a distribution constructor: an operation over a random variable.

Working with the generator

The command to execute the instance generator is:

> java pfc.ingsw.ProblemGenerator <configuration file> <output file>

The instance generated can be invalid, that is, it can not be foud a solution for it. The first line of the output file is a comment line that indicates whether the instance is valid or not.

Sample configuraton files

The following are some configuration files:

Next, we present 36 instances created to study the influence of some parameters on the difficulty of the instances.

Employee skills
4-5 skills 6-7 skills
employees employees
Global skills
5 skills 10 skills
employees employees
5 10 15
5 10 15
5 10 15
5 10 15
conf conf conf
conf conf conf
conf conf conf
conf conf conf
conf conf conf
conf conf conf
conf conf conf
conf conf conf
conf conf conf
conf conf conf
conf conf conf
conf conf conf


To download the jar file with the instance generator click here. You must add the jar file to the classpath in order to use the generator.

Page updated on April 1st of 2005