direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Generalized Min-Sum Scheduling Instance Library

Lupe [1]

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

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

Problem

The provided instances are generated for computational experiments on the problem 1||∑j wj g(Cj): Given a set of n jobs with processing times pj and weight wj for j=1, ..., n, one aims for a sequence of the jobs minimizing ∑j wj g(Cj) where g is some non-decreasing cost function and Cj 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
  • pmax    maximum processing time
  • σ > 0  –  represents the computational difficulty of the instance

The processing time pj of a job j is chosen as a uniform random integer between 1 and pmax. 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 wj is then calculated from pj as

wj := pj ⋅ 2N(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 (pj,wj) ∈ R2, 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 wi > wj and pi < pj, 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.

Three instances generated for parameters sigma = 0.2, 0.4, and 0.8.
Lupe [4]

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 pmax 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.

Parameters of data sets

set

n


σ
#inst./
fixed
n or σ

total
#inst.
Sσ,B
20
0.100, 0.101, ..., 1.000
3
2703
[zip] [5]
Sσ,T
25
0.100, 0.101, ..., 1.000
3
2703
[zip] [6]
Sσ,Q
10
0.100, 0.101, ..., 1.000
3
2703
[zip] [7]
Sσ,S
25
0.100, 0.105, ..., 1.000
1
181
[zip] [8]
Sn
1, ..., 35
0.5
10
350
[zip] [9]

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.

Reference

Höhn, Wiebke and Jacobs, Tobias
An experimental and analytical study of order constraints for single machine scheduling with quadratic cost [10].
In Proc. of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 103-117, SIAM, 2012.  [pdf] [11]


------ Links: ------

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

Copyright TU Berlin 2008