I was going to post exactly this. I always solve scheduling problems with GAs and get great results. It's easy to do and does not require any domain knowledge. It would probably take just a few hours to solve this using a GA, maybe even less.