Recently population-based meta-heuristics under the cover of swarm intelligence have gained prominence. This includes particle swarm optimization (PSO), where the search strategy draws ideas from the social behavior of organisms. While PSO has been reported as an effective search method in several papers, we are interested in the critical success factors of PSO for solving combinatorial optimization problems. In particular, we examine the application of PSO with different crossover operators and hybridization with variable neighborhood descent as an embedded local search procedure. Computational results are reported for the continuous (nowait) flow-shop scheduling problem. The findings demonstrate the importance of local search as an element of the applied PSO procedures. We report new best solutions for a number of problem instances from the literature.