I have been a middle school/ high school teacher for 15 years, and I have watched countless hours spent on inefficient approaches to scheduling. I have also recognized that it is not a trivial problem to solve. I started writing a program to help with the problem years ago, but didn't make the time to see it through, as I wasn't the one doing scheduling.

I think an overall approach would be to present a number of schedules that could work, and expect the user to do some manual adjustments. Perhaps present a schedule that could work, user checks off which classes to keep, and program shuffles other classes. Repeat until done. I think that's basically the approach people use when they do it manually.