Page Content
Part of the project "Algorithms for Complex Scheduling Problems"
Problem
The provided instances are generated for computational experiments on the problem 1||∑_{j} w_{j} g(C_{j}): Given a set of n jobs with processing times p_{j} and weight w_{j} for j=1, ..., n, one aims for a sequence of the jobs minimizing ∑_{j} w_{j} g(C_{j}) where g is some non-decreasing cost function and C_{j} denotes the completion time of job j.
Concept of generating instances
Our instances have been randomly generated using a combination of uniform and normal distribution. The random instance generator is configured by the three parameters
- n – number of jobs in the instance
- p_{max }–_{ }maximum processing time
- σ > 0 – represents the computational difficulty of the instance
The processing time p_{j} of a job j is chosen as a uniform random integer between 1 and p_{max}. Assuming the minimum processing time to be 1 is without loss of generality if considering monomial cost functions. In this case, the problem is invariant to processing time scaling.
The weight w_{j} is then calculated from p_{j} as
w_{j} := p_{j} ⋅ 2^{N(0, σ⋅σ}^{)},
where N(0,σ^{2}) means that the exponent is chosen according to normal distribution with mean 0 and standard deviation σ.
Computational difficulty of the instances
By plotting each job j as a point (p_{j},w_{j}) ∈ R^{2}, the figure below gives an impression on how instances generated with respect to different values of σ look like. The larger the σ-value the more the jobs are spread around the angle bisector.
Observing that a job i appears before a job j in any optimal schedule if w_{i }> w_{j} and p_{i} < p_{j}, one gets an intuition why σ may be an important characteristic for the difficulty of an instance: If all jobs lie close to the angle bisector, then, for a fixed job, most of the other jobs are not comparable with respect to the observation (comparable are those jobs that either lie to the top left or the bottom right of the fixed job). In contrast, if the jobs are evenly spread over the plane, the constraints will fix the relative order of many more job pairs, and by this, they allow to heavily prune the search space.
Data sets
For the purpose of analyzing different characteristics of different algorithms, individual data sets were used. The parameters of the data sets are stated below. The maximum processing time p_{max} is set to 100 in all settings. The first four sets are generated to analyze the behavior depending on the correlation parameter σ while the last set is made to analyze the behavior with increasing instance size. Further details can be found in the referenced paper below.
set | n | σ | #inst./ fixed n or σ | total #inst. | |
---|---|---|---|---|---|
S_{σ,B} | 20 | 0.100, 0.101, ..., 1.000 | 3 | 2703 | [zip] |
S_{σ,T} | 25 | 0.100, 0.101, ..., 1.000 | 3 | 2703 | [zip] |
S_{σ,Q} | 10 | 0.100, 0.101, ..., 1.000 | 3 | 2703 | [zip] |
S_{σ,S} | 25 | 0.100, 0.105, ..., 1.000 | 1 | 181 | [zip] |
S_{n} | 1, ..., 35 | 0.5 | 10 | 350 | [zip] |
Organization of instance files
Files start with a comment block containing information according to which parameters the instances in this file were generated: the number of generated instances for the particular pair of σ and n (referred to as instances), n (referred to as jobs per inst), σ (referred to as std. deviation), and the minimum and maximum processing times (referred to as min p and max p, respectively).
To keep the weights integral while not loosing accuracy, the resolution was introduced. The actual weights are given by the integral weights in the file divided by the resolution value (100 for all files provided).
The comment block is followed by the actual instances. Each line contains one instance in square brackets. The jobs are listed as integral (processing time, weight)-pairs separated by commas.