I'm convinced that part of it is easy. To do it optimally is NP-hard, but one doesn't need to find a perfect solution.
The problem is that solutions are always a little bit ill-defined and won't be 100% captured by any generic software model, and that they need to be amenable to further semi-manual tweaking.
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.
The problem is that solutions are always a little bit ill-defined and won't be 100% captured by any generic software model, and that they need to be amenable to further semi-manual tweaking.