Record number :
1595788
Title of article :
Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop
Author/Authors :
Andresen، نويسنده , , Michael and Brنsel، نويسنده , , Heidemarie and Mِrig، نويسنده , , Marc and Tusch، نويسنده , , Jan and Werner، نويسنده , , Frank and Willenius، نويسنده , , Per، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2008
Pages :
15
From page :
1279
To page :
1293
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. It continues recent work by Brنsel et al. [H. Brنsel, A. Herms, M. Mِrig, T. Tautenhahn, T. Tusch, F. Werner, Heuristic constructive algorithms for open shop scheduling to minmize mean flow time, European J. Oper. Res., in press (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. For the simulated annealing algorithm, several neighborhoods are suggested and tested together with the control parameters of the algorithm. 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 algorithms are compared relative to each other, and the quality of the results is also estimated partially 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 30 000 generated solutions for each algorithm. 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 , genetic algorithm
Journal title :
Mathematical and Computer Modelling
Serial Year :
2008
Link To Document :
بازگشت