Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop

What is it about?

This paper considers the problem of scheduling nn jobs on mm machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. It continues recent work by Bräsel et al. in European J. Oper. Res. (doi.10.1016/j.ejor.2007.02.057)] on constructive algorithms. For this strongly NP-hard problem, we present two iterative algorithms, namely a simulated annealing and a genetic algorithm.

Featured Image

Why is it important?

In contrast to makespan minimization problems, where the focus is on problems with an equal number of jobs and machines, it turns out that problems with a larger number of jobs than machines are the hardest problems.