Abstract: This paper proposes a new hybrid optimization algorithm for solving stochastic job shop scheduling problems, which integrates the idea of ordinal optimization into the framework of nested partitions (NP) algorithm. Ordinal comparison method is used to perform local search of NP and its exponential convergence rate improves the efficiency of local search and thereby the efficiency of global search greatly. And the optimal computing budget allocation technique further improves the convergence rate and reliability of the optimization result. The new algorithm retains the feature of global search of nested partitions and fast convergence of ordinal optimization. The algorithm is used to solve job shop scheduling benchmark problems. The results of numerical simulations, which are compared with those of other well-known algorithms, show better performance of the proposed algorithm.