A hard instances generator for the Open Shop Scheduling Problem

Algorithms For Business Resource Optimization

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 Pij and Pkl, 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{Pij, Pkl} − 1 (subtract 1 to avoid tasks of length 0).
    • v = (f · mv) + r, with r: a random value between 0 and f · mv.

The value subtracted from Pij and Pkl is added to Pil and Pkj to keep the sum of all rows equal to 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 × m2.
  • 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

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.