This is written from the pragmatic point of view. Don't reinvent the wheel. You are better off learning and using a known piece of software than writing your own scheduling program that likely won't preform as well and will be 'fun' to maintain - both for you and the next guy.
Scheduling problems are hard... and not just hard, but they can often be NP-hard. The problem described is a modification of the nurse scheduling problem which is a classic one that has been studied for several decades because of its difficulty.
If one wants to try to code it oneself, there are a number of techniques. Those mentioned in the wikipedia article include decomposition, parallel computing, stochastic optimization, genetic algorithms, colony optimization, simulated annealing, Tabu search, and coordinated descent.
I should also point out that there is an entire industry of software programs around the nurse scheduling program. A search for nurse scheduling software turns up numerous results from different companies.
All of these fall into the area of constraint programming, and while one could sit down with prolog (or write your own), this tends to be the area where one would grab a rules engine appropriate to your platform and let it do the work. One such example is that of drools, which has an example of employe shift rostering using nurses (there are some other examples too including patient admission schedule, exam timetabling, and a traveling tournament problem).