In scheduled (timetabled) transport systems (for buses, trains, etc.) it is desirable at the planning stage to know what effect proposed or planned changes in the schedule may have on expected costs, expected lateness, and other measures of cost or reliability. We consider such effects here, taking account of the random deviations of actual times (or arrivals, departures, etc.) from the corresponding scheduled times. We also take account of various forms of interdependence (knock-on effects) between the timings (arrivals, departures, connections, lateness, etc.) of different transport units. We formulate a stochastic model of such a complex transport system. (For generality, the underlying deterministic version of the model is consistent with versions of various existing deterministic transport models). We show that expected costs, and various measures of reliability, behave well (are convex) with respect to any changes in the schedule. We derive this convexity, (a) without assuming any particular functional form for the probability distributions of any of the random variables (trip times, wait times, etc.), (b) assuming very general operating rules, (c) assuming a quite general transport network. These convexity properties assist transport planners and managers in predicting the effects of schedule changes. They also ensure that various search algorithms can be used to find improved or optimal schedules.