Tabu search : how to implement "employee working in pairs" constraint

Question

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

Answer 1

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.