The classical Job Shop Scheduling Problem (JSSP) is NP-hard problem in the strong sense. For this reason, different metaheuristic algorithms have been developed for solving the JSSP in recent years. The Particle Swarm Optimization (PSO), as a new metaheuristic algorithm, has applied to a few special classes of the problem. In this paper, a new PSO algorithm is developed for JSSP. First, a preference list of the generated solutions is prepared to obtain the feasibility. Then, a new method using factorial base numeral system, called factoradic approach, is developed to satisfy the validity of the generated solutions. This approach permits a one to one mapping of a solution in discrete space to a PSO particle position in continuous space. Since PSO is an evolutionary approach, some modifications are implemented to the algorithm. For examples, a simple greedy algorithm is developed to generate relatively good initial population or every solution obtained by PSO is also improved by a local search operator. To avoid trapping into local optima, a new velocity updating equation is considered. Furthermore, a Simulated Annealing (SA) approach is applied to the final solution obtained by PSO to improve it. Finally, the proposed hybrid algorithm is tested by some job shop benchmark problems. The results indicate the efficiency of the proposed hybrid PSO with respect to other algorithms exist in the literature for the considered problem.