Generalized Min-Sum Scheduling Instance Library

Part of the project "Algorithms for Complex Scheduling Problems" [2]

within DFG Priority Programme 1307 "Algorithm Engineering" [3]

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.

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,σ²) means that the exponent is chosen according to normal distribution with mean 0 and standard deviation σ.

By plotting each job j as a point (p_j,w_j) ∈ R², 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.

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.

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.