The paper represents an enhanced new algorithm called FPSO-FJSSP, based on Particle Swarm Optimization (PSO) technique for the combinatorial flexible job shop scheduling problem (FJSSP). Five test examples from literature sources are tested by the new algorithm. In all cases the optimal solution has been found. The performance of the FPSO-FJSSP algorithm is illustrated on one of the test examples. The obtained results are encouraging. A variant of the new algorithm can be applied to solve multiple objective FJSSP.