  This paper proposes a new formulation for the school bus scheduling problem
(SBSP) which optimizes school start times and bus operation times to minimize
transportation cost. Our goal is to minimize the number of buses to serve all
bus routes such that each route arrives in a time window before school starts.
We present a new time-indexed integer linear programming (ILP) formulation for
this problem. Based on a strengthened version of the linear relaxation of the
ILP, we develop a dependent randomized rounding algorithm that yields
near-optimal solutions for large-scale problem instances. We also generalize
our methodologies to solve a robust version of the SBSP.
