Sie sind hier

# Generalized Min-Sum Scheduling Instance Library

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

Citation key HoehnJacobs2012a Höhn, Wiebke and Jacobs, Tobias Proc. of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX) 103-117 2012 SIAM We consider the problem of scheduling jobs on a single machine. Given a quadratic cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is defined as the cost function value at the job's completion time. Throughout the past decades, great effort has been made to develop fast exact algorithms for the case of quadratic costs. The efficiency of these methods heavily depends on the utilization of structural properties of optimal schedules such as order constraints, i.e., sufficient conditions for pairs of jobs to appear in a certain order. A considerable number of different kinds of such constraints have been proposed. In this work we enhance the map of known order constraints by proving an extended version of a constraint that has been conjectured by Mondal and Sen more than a decade ago. Besides proving this conjecture, our main contribution is an extensive experimental study where the influence of different kinds order constraints on the performance of exact algorithms is systematically evaluated. In addition to a best-first graph search algorithm, we test a Quadratic Integer Programming formulation that admits to add order constraints as additional linear constraints. We also evaluate the optimality gap of well known Smith's rule for different monomial cost functions. Our experiments are based on sets of problem instances that have been generated using a new method which allows us to adjust a certain degree of difficulty of the instances.