Is it not possible to limit your algorithm's maximum time change for each school? Say, capping the change at 1 hour, and finding the best result of that set of times. Even if it is not as good as the 100% optimized solution, it seems like more palatable while also being an improvement.

Presumably, you are already doing that, by limiting the start/end times from 7am-10am, or something similar. In this case, instead of a global time restraint, there would be a local time change restraint +-1 hour for each school.