Road maintenance is essential to ensure a safe and efficient transportation system. In this paper we address two major limitations in current work zone optimization models. First, we relax the assumption of determinism and model vehicle arrivals as being stochastic. While previous work has shown that this relaxation is important in the quantification of user delay at work zones, to the best of the author’s knowledge, no model exists that explicitly accounts for stochasticity in the optimization of work zones. Second, unlike in previous work where rather idealized traffic flow modeling techniques were used, the proposed model is based on the traffic flow theory-based cell transmission model, yielding a more accurate and realistic representation of traffic flow dynamics. Numerical examples are presented and discussed.