I'm developping an automated employee scheduling app, using Tabu search with constraints.
I've already got a lot of constraints working (minimum hours for employees, number of employees required per shifts, employees who must not work together,...).
The automated planner tries different moves each iteration (adding/removing/swapping employees), evaluates the constraints for all generated solutions (1 solution per move) and picks the solution with the smallest penalty.
I'm now trying to implement a constraint such as "if employee A is scheduled on the shift, then employee B must also be scheduled on that same shift".
My problem is that I don't know how to implement this.
Say the current move is to schedule employee A on an unstaffed shift S. If the constraint I'm trying to create is evaluated, then that solution will get a penalty straight away because employee A is scheduled on S without employee B. Consequently, this solution might never be selected even though it's a good one and neither employee A or B will get to work.
Does anybody have any idea?
Thanks
Some suggestions:
The penalty for unstaffed shift should be bigger than the penalty for unpaired friends.
You can have simulated annealing - so that momentary increases in penalty would be accepted sometimes.
You can have a different kind of move - a move that adds/removes more people, and prefers to move "friends" together.