The purpose of school bus services is to carry children from their homes to school and back. Scheduling and routing such services manually can be a long and tedious task, as it gives rise to complex combinatorial problems. To tackle those, we propose various heuristics in order to build good quality schedules of school bus routes for small and large size problems. The school bus routing and scheduling problem is modeled by introducing a performance measure corresponding to the service level provided to the children. This quality measure focusing on the children differs from previous approaches to the subject, in which the solution evaluation generally depends on the number of buses used or the lengths of the routes of the vehicles. In addition, our schedules allow the vehicles simultaneously to carry children going to different schools, which to our knowledge has only been treated once in the literature. Two problems are considered: one consisting in maximizing the average quality of children service level and another to maximize the quality of the worst service level provided to a child. These problems can be formulated as binary integer programs, but their size is too large to consider an exact resolution with current software and computers. A constructive method is proposed to obtain a feasible schedule which is optimized thereafter with various heuristics: simulated annealing, tabu search and variable neighborhood search. Let us note that, during optimization, the use of schedules violating the vehicle capacity is authorized. The heuristics employed, in their variant exploring infeasible solution set, are more effective than those that are confined to the feasible solution set. These methods also yield much higher quality schedules for real data sets than those actually used by the schools in question. An ideal schedule should allow to simultaneously optimize both objective functions mentioned above. In order to approach such a solution, a two phase method is proposed. The first phase consists in maximizing the minimum service level and the second in maximizing the average service level without reducing the minimum obtained during the first phase. We also developed an extension of our methods based on decomposition adapted to large scale problems. The proposed decomposition approach allows to considerably reduce computing time without giving up quality and is essential in order to solve problems with a large number of children. Let us finally note that a graphical user interface was developed, allowing to visualize, analyze and modify schedules generated by the heuristics. It is thus possible to integrate additional constraints that have not been modeled, or to adapt a solution in case of a small modification to the problem data.