Early in his career, it was done by hand, with large sheets of paper and moving cards around until all the pieces fit. Later, a couple of software companies came around, and they had this service where he would show up at an office, discuss the constraints with an operator, and choose among a handful options for the final schedule.
However, the crux of the problem was never the scheduling itself, but the accommodating of constraints which, given that teachers are in-class for 18-20h a week, but school is open for 30h/w, can get complicated pretty quickly. Some examples:
- Every teacher wanted to have one day with very light load, 1-2h max, so they could run other chores at home. Some people were very specific about this (i.e. they needed early Tuesday off), while others didn't care that much. - Nobody could just have a no-class day, due to administrative and legal reasons. - Having a gap hour without class was a big NO, because it adds to the time requirements without delivering actual teaching, so it was to be avoided at all costs. - All things equal, senior teachers outranked their junior peers in terms of choosing class levels, lab vs lecture, etc. - Some teachers had their own children attend the same school, and nobody wanted to teach their own kids (nor would the kids)
All in all, no matter how much time and effort he sunk into scheduling to everyone's liking, there was no perfect solution, and every single year there were aggravated teachers who would raise hell. He was called inhumane by someone who claimed the right to a free hour every morning to drop off her own kid, but only got her wish 4 days out of 5. He had peers stop talking to him over class level choices. The only reason he kept doing it was because the director was his close friend, and he asked my dad repeatedly. But he didn't wish that job on his worst enemy.