A modified genetic algorithm with fuzzy roulette wheel selection for job-shop scheduling problems |
| |
Authors: | Arit Thammano Wannaporn Teekeng |
| |
Affiliation: | Computational Intelligence Laboratory, Faculty of Information Technology, King Mongkut’s Institute of Technology Ladkrabang, Bangkok, Thailand |
| |
Abstract: | The job-shop scheduling problem is one of the most difficult production planning problems. Since it is in the NP-hard class, a recent trend in solving the job-shop scheduling problem is shifting towards the use of heuristic and metaheuristic algorithms. This paper proposes a novel metaheuristic algorithm, which is a modification of the genetic algorithm. This proposed algorithm introduces two new concepts to the standard genetic algorithm: (1) fuzzy roulette wheel selection and (2) the mutation operation with tabu list. The proposed algorithm has been evaluated and compared with several state-of-the-art algorithms in the literature. The experimental results on 53 JSSPs show that the proposed algorithm is very effective in solving the combinatorial optimization problems. It outperforms all state-of-the-art algorithms on all benchmark problems in terms of the ability to achieve the optimal solution and the computational time. |
| |
Keywords: | genetic algorithm tabu search fuzzy roulette wheel selection job-shop scheduling problem |
|