Heuristic constructive algorithms for open shop scheduling to minimize mean flow time

What is it about?

We consider the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. For this strongly NP-hard problem, we develop and discuss different constructive heuristic algorithms. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. We observed that the recommendation of an appropriate constructive algorithm strongly depends on the ratio n/m.

Featured Image