Flexible job shop scheduling using genetic algorithm and heuristic rules

Abstract

Job shop scheduling with the availability of more than one machine to perform an operation, also known as the flexible job shop scheduling problem, is computationally NP-hard. An efficient scheduling method is proposed here, using a genetic algorithm that incorporates heuristic rules. The scheduler's goal is to minimize mean tardiness. There are two types of decision making required: job selection and machine selection. Combinations of five job selection and five machine selection heuristics are examined. Numerical experiments show that the combination of Yoda et al.'s (SL/RPN)+SPT rule for job selection and Eguchi et al.'s (WINQ+RPT+PT)×PT rule for machine selection provide the best performance under different shop conditions when incorporated into the genetic algorithm. It is also found that applying genetic algorithm only for either job selection or machine selection can generate good schedules, depending on conditions.

Keywords

• job shop scheduling
• optimization
• genetic algorithms
• heuristics