The purpose of this study is to develop a systematic scheduling model that will help ready mixed concrete (RMC) carriers/suppliers with effective scheduling adjustment after temporary breakdown of mixers under stochastic travel times. The model is formulated as a mixed integer network flow problem with side constraints that is characterized as NP-hard. The authors employ problem decomposition and relaxation techniques, with a mathematical programing solver, to develop an algorithm that is capable of efficiently solving the problem. A simulation-based evaluation method is also proposed to evaluate the model, joined with a deterministic model, as well as the method currently used in actual operations. Finally, a case study is performed using real operating data from a Taiwan RMC firm. The preliminary results demonstrate that the stochastic model and the solution algorithm could be useful to reduce system cost for the RMC carrier in actual operations.