## A hard instances generator for the Open Shop Scheduling Problem

In this paper, we present a hard instances Open Shop Problems generator inspired from [1].

## The generator

The random instances generator takes the number of jobs *n *and the number of machines *m *as input and requires three parameters *k*, *p *and *f *.

*k*: integer number, such that the sum of each line of*P*is equal to*k*. The value*k*mod*m*is added to the diagonal of*P*.*p*: number of perturbations, such that for each perturbation, two task’s processing times*P*and_{ij}*P*,_{kl}*i <>k*and*j <> l*, are randomly selected from*P*, from which is subtracted the value of*v*.*f*=*{f ∈*R*|*0*< f <*1*}*, such that:*mv*= max*{P*1 (subtract 1 to avoid tasks of length 0)._{ij}, P_{kl}} −*v*= (*f · mv*) +*r*, with*r*: a random value between 0 and*f · mv*.

The value subtracted from *P _{ij} *and

*P*is added to

_{kl}*P*and

_{il}*P*to keep the sum of all rows equal to

_{kj}*k*.

For numerous generated instances the parameters *k*, *p *and *f *are randomly generated as follows:

*k*: random value between*n × m*and*n × m ×*100.*p*: random value between*n × m*and*n × m*^{2}.*f*: random value between 0 and 1.

Note that in the case of *n *= *m*, *k *mod *m *is added the diagonal of top-down square sub-matrices of size min *n, m *of *P*. The main diagonal is used on the remaining rectangle ensuring the sum of all rows of *P *are equal to *k.*

## Usage

Open shop instance problem format is the following:

// a comment line # also a comment line // jobs machines 3 3 // processing times 3 8 49 52 12 5 20 25 13

Generating problem instances with `hossp`

hossp: Generate hard random instances of the open shop problem Usage: hossp [OPTION...] -h, --help This help message and exit -n, --jobs arg number of jobs (default: 4) -m, --machines arg number of machines (default: 4) -k arg the k value, =rand(n*m,n*m*100) if 0 (default: 0) -f, --fix arg fixed percentage, =rand(0,1) if 0 (default: 0) -p, --pert arg number of perturbations, =rand(n*m,n*m^2) if 0 (default: 0) -g, --generate arg number of instances to generate (default: 1) -o, --out Enable stdout -d, --dir arg Output directory (default: "")

The following command generates 5 random instances, of 5 jobs and 5 machines and outputs the instances to stdout (-o).

./build/bin/hossp.exe -n 5 -m 5 -g 2 -o // k = 491, pert = 83, fix = 0.627064, seed = 634927729, lb = 491 5 5 11 249 153 3 75 222 13 212 35 9 2 14 118 231 126 1 173 5 187 125 255 42 3 35 156 // k = 644, pert = 82, fix = 0.0872524, seed = 931827985, lb = 644 5 5 151 86 368 12 27 65 176 267 39 97 266 1 5 251 121 91 1 2 341 209 71 380 2 1 190

The code is available on github.

## Reference

[1] Guéret, C., & Prins, C. (1999). A new lower bound for the open-shop problem. Annals of Operations Research, 92, 165–183.https://doi.org/10.1023/A:1018930613891.2