A novel hybrid genetic algorithm for the open shop scheduling problem

作者：Ahmadizar Fardin^*; Farahani Mehdi Hosseinabadi

来源：International Journal of Advanced Manufacturing Technology, 2012, 62(5-8): 775-787.

DOI：10.1007/s00170-011-3825-1

• Open shop scheduling
• Genetic algorithm
• Heuristic algorithm

In this paper, a hybrid genetic algorithm is proposed for the open shop scheduling problem with the objective of minimizing the makespan. In the proposed algorithm, a specialized crossover operator is used that preserves the relative order of jobs on machines and a strategy is applied to prevent from searching redundant solutions in the mutation operator. Moreover, an iterative optimization heuristic is employed which uses the concept of randomized active schedules, a dispatching index based on the longest remaining processing time rule and a lower bound to further decrease the search space. Computational results show that the proposed algorithm outperforms other genetic algorithms and is very competitive with well-known metaheuristics available in the literature.

• 出版日期2012-9