A modified genetic algorithm with fuzzy roulette wheel selection for job-shop scheduling problems
Authors:
- 3 December 2014
- journal article
- research article
- Published by Taylor & Francis in International Journal of General Systems
- Vol. 44 (4) , 499-518
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
This publication has 17 references indexed in Scilit:
- An agent-based parallel approach for the job shop scheduling problem with genetic algorithmsMathematical and Computer Modelling, 2010
- Memetic algorithms for solving job-shop scheduling problemsMemetic Computing, 2008
- Clonal Selection Based Memetic Algorithm for Job Shop Scheduling ProblemsJournal of Bionic Engineering, 2008
- A branch-and-bound-based local search method for the flow shop problemJournal of the Operational Research Society, 2003
- An improvement of the Lagrangean relaxation approach for job shop scheduling: a dynamic programming methodIEEE Transactions on Robotics and Automation, 1998
- A branch and bound algorithm for the job-shop scheduling problemDiscrete Applied Mathematics, 1994
- The “molecular” traveling salesmanBiological Cybernetics, 1990
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990
- Optimization by Simulated AnnealingScience, 1983
- Fuzzy setsInformation and Control, 1965