A hybrid estimition of distribution algorithm(HEDA) is proposed to solve the stochastic Job shop scheduling problem with earliness/tardiness penalty. To enhance the population diversity of the HEDA, the inherit rate of the operations in parent chromosome is defined and a new recombination method is proposed base on it. This recombination method not only can make the offspring inherit the excellent characteristics of the parent effectively, but also can avoid infeasible solution. To improve the precision of the individual evaluation, the optimal computing budget allocation is adopted in the phase of individual selection. Simulation results show the effectiveness and robustness of HEDA.