For problems like employee scheduling where there are a lot of constraints on the solution, I prefer approaches that never violate any constraints, or as near as possible. (Some approaches such as genetic crossover will violate constraints and then perform additional operations to fix the solution - this is also a valid approach, but you need to beware of going down a blind alley.)
Two approaches are based on using a greedy algorithm.
The first is to use a semi random greedy algorithm; if you have two choices then ordinarily you would always select the locally optimal choice, but with a semi random greedy approach you introduce the possibility of selecting the choice that isn't locally optimal. For example choice one has a weight of 5 and choice two has a weight of 2; ordinarily you would select choice one, but in this case you would use a random number generator and select choice one if rand(5 + 2) is less than 5, else select choice two. Now run the algorithm several times and take the "best" solution.
The second option is to start with a greedy or semi random greedy solution, and to use a local search algorithm to reassign employee slots in an attempt to improve the solution. For example, if an employee has fewer than their desired hours then bump an employee occupying a slot that's legal for the sub optimal employee and assign the sub optimal emoloyee to it, continuing the search to reassign the bumped employee if need be. Unlike the first solution, this one may not terminate if you're not careful.
The two approaches can be combined, generating several solutions with the semi random greedy approach and then conducting local searches to improve the best results.
