A flow shop with no-wait schedules jobs continuously through all machines without any wait at consecutive machines. This scheduling problem is combinatorial optimization problem and observed as NP-hard as appropriate sequence of jobs for scheduling from all possible combination of sequences is to be determined for reducing total completion time (makespan). This paper presents an effective hybrid Particle Swarm Optimization algorithm for solving no wait flow shop scheduling problem with the objective of minimization of makespan. This Proposed Hybrid Particle Swarm Optimization Makespan (PHPSOM) algorithm represents discrete job permutation by converting the continuous position information values of particles with random key representation rule. The proposed algorithm balances global exploration and local exploitation with evolutionary search guided by the mechanism of PSO, and local search by the mechanism of Simulated Annealing (SA) along with efficient population initialization with Nawaz-Enscore-Ham (NEH) heuristic. The effectiveness of the proposed method is validated by extensive computational experiments based on Taillards benchmark suite. Computational results and comparisons with best known solutions for makespan confirm that the proposed algorithms performance is better than the existing methods in terms of searching quality and robustness. Statistical tests of significance validate the improvement in the solution quality.
展开▼
