A quantum behaved particle swarm optimization for flexible job shop scheduling

A flexible job shop scheduling problem (FJSP) is an extension of the classical job shop problem (JSP) where operations are allowed to be processed on any among a set of available machines at a facility. For such problems, it is not always possible to find optimal solution in a reasonable time. Hence, a large variety of heuristic procedures such as dispatching rules, local search, and meta-heuristic procedures are used to solve such problems and generate approximate solutions close to the optimum with considerably less computational time. PSO is an effective algorithm which gives quality solutions in a reasonable computational time and requires less number of parameters to be tuned in comparison to other evolutionary meta-heuristics. However, PSO has an inherent drawback of getting trapped at local optimum due to large reduction in velocity values as iteration proceeds and poses difficulty in reaching at best solution. This drawback can be effectively addressed using quantum-behaved particle swarm optimization (QPSO) due to its advanced global search ability. Mutation, a commonly used operator in genetic algorithm, has been introduced in QPSO so that premature convergence can be avoided. Logistic mapping is used to generate chaotic numbers in this paper. The performance of schedules is evaluated in terms of total completion time or makespan (C-max). The results are compared with different well-known algorithms used for the purpose from open literature. The results indicate that the proposed QPSO algorithm is quite effective in reducing makespan because small value of relative deviation is observed. (C) 2015 Elsevier Ltd. All rights reserved.