Effective management of production uncertainties is becoming critical in the era of "time-based competition". The consideration of uncertainties, however, is difficult because of the combinatorial nature of the problem as well as the probabilistic nature of uncertain factors. This paper presents a novel approach for job-shop scheduling considering major uncertain characteristics, e.g., machine breakdowns and uncertain processing times. A separable problem formulation that balances modeling accuracy and solution time is presented with the objective to minimize expected part tardiness penalty. A solution methodology based on a combined Lagrangian relaxation, stochastic dynamic programming and "ordinal optimization" is developed. Initial numerical results supported by simulation demonstrate that the schedules generated have low expected penalties, a highly desirable property for achieving product delivery with short lead times.