06-48
Metaheuristic Algorithms for Open Shop Scheduling to Minimize Mean Flow Time
by Andresen, M.; Bräsel, H.; Mörig, M.; Tusch, J.; Werner, F.; Willenius, P.
Preprint series: 06-48, Preprints
The paper is published: Mathematical and Computer Modelling, Vol. 48, 2008, 1279 - 1293 (under the title: Simulated Annealing and Genetic Algorithms for Minimizing Mean Flow Time in an Open Shop)
Abstract: This paper considers 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 and continues recent work by Bräsel et al. (2005) on constructive algorithms. For this strongly NP-hard problem, we compare different iterative metaheuristic algorithms, namely simulated annealing, tabu search and genetic algorithms. For the first two types of algorithms, a number of different neighborhoods are suggested and tested together with their control parameters. For the genetic algorithm, new genetic operators are suggested based on the representation of a solution by the rank matrix describing the job and machine orders. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The quality of the solutions is estimated by a lower bound for the corresponding preemptive open shop problem. For most of the problems, the genetic algorithm is superior when fixing the same number of 30000 generated solutions. However, 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.
Keywords: Open shop scheduling, mean flow time, metaheuristic algorithms, simulated annealing, tabu search, genetic algorithm
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.