A hybrid particle swarm optimization algorithm for bi-criteria flexible job-shop scheduling problem

This paper presents a hybrid particle swarm optimization algorithm (HPSO) for solving the bi-criteria flexible job shop scheduling problem. Two minimization objectives- the maximum completion time (makespan) and the total workload of all machines are considered simultaneously. In this study, a novel discrete particle swarm optimization (PSO) algorithm was proposed, which incorporates well-designed crossover and mutation operators concurrently. Then, an external Parteo archive was developed to memory the Pareto optimal solutions found so far. In addition, to improve the efficiency of the scheduling algorithm, a speed-up method was devised to decide the domination status of a solution with the archive set. Experimental results on two well-known benchmarks show the efficiency of the proposed hybrid algorithm. It is concluded that the HPSO algorithm is superior to the existing present algorithms in term of both search quality and computational efficiency.