This. I worked with a company that used this method to generate timetables for schools with way more variables and constraints. They often found working plans w

This. I worked with a company that used this method to generate timetables for schools with way more variables and constraints. They often found working plans when other solutions did not. Maybe a little overengineered for your problem though