Algorithms For Business Resource Optimization

Random generator of Open Shop Scheduling Problems

We present a hard instances generator for the Open Shop Scheduling Problems inspired from [1].

The random instances generator takes the number of jobs n and the number of machines m as input and requires three parameters.

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

The value subtracted from Pij and Pkl is added to Pil and Pkj to keep the sum of all rows equal to k. This is done to ensure that workload is equal to 1.

For n = m, we add k mod m to 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.

The code is available on github.


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

0 0 votes
Article Rating
Notify of

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

Inline Feedbacks
View all comments
Would love your thoughts, please comment.x