An Instance Generator for the Project Scheduling Problem
Introduction
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.
Description
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 |
| task.number |
| task.cost |
| task.skill |
| employee.number |
| employee.salary |
| employee.skill |
| graph.e-v-rate |
| skill.number |
|
| 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
task.cost.parameter.distribution.parameter.mu = 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
graph.e-v-rate.parameter.mu = 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
employee.salary.parameter.mu = 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 |
|
|
| Rounding constructor |
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:
- int-gen-30-10.conf:
generates instances with 30 tasks and between 10 and 20 employees uniformly distributed.
- int-gen-20-15.conf:
generates instances with 20 tasks and exactly 15 employees.
- int-gen-20-15-t6-7.conf:
generates instances with 20 tasks, exactly 15 employees, and 6 or 7 required skills per task.
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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Download
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