FWIW, this is a classic genre of problem to tackle with integer programming - usually in the specific form of nurse rostering, for some reason:

https://pdfs.semanticscholar.org/9d0b/5eb5749a6699a4c43bf808...

It's entirely possible that your particular case has constraints you can't easily express as a linear program. But if you can, go ahead and use the nuclear option!