Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time

摘要

Job shop scheduling problem is a NP-hard problem. The processing time for each job is often imprecise in many real-world applications and the imprecision in the data is critical for the scheduling procedures. Therefore, job shop scheduling problem with fuzzy processing time is addressed in the paper. The processing time is described by triangular fuzzy numbers. The objective is to find a job sequence that minimizes the makespan and the uncertainty of the makespan by using an approach for ranking fuzzy numbers. The particle swarm optimization (PSO) is a randomized, population-based optimization method that was inspired by the flocking behavior of birds and human social interactions. PSO has been successfully applied to various real-world applications, but there is a little literature reported regarding application to scheduling problems as it was unsuitable for them. In this paper, PSO is redefined and modified by introducing genetic operators such as crossover and mutation operator to update the particles. We call this particle swarm optimization combined with genetic operators (GPSO). This is successfully employed to solve the formulated problem. Ten benchmarks with fuzzy processing time are used to test GPSO. The feasibility, as well as the efficiency of the proposed method, is assessed in comparison with genetic algorithm (GA).