A client wishes to simplify the nurse scheduling problem to 'bypass' the NP-complete nature of this problem.
He is hoping to do so by removing the requirement that there are any constraints for any of the nurses in terms of availability. (Also, assume there is only one shift type.)
Specifically:
- Given no minimum shift requirement for any nurse (0 hours is fine)
- Given complete availability of every nurse for every shift
- Given uniform shift lengths (but shifts CAN overlap)
... is the problem still NP-complete?
If not, then presumably it becomes NP-complete by adding one or more of the following constraints:
- There are a MAXIMUM number of shifts per nurse
- The shift lengths can vary
... are one and/or the other of the above sufficient for the problem to become NP-complete? Or does the following constraint need to be added:
- Nurses have certain shifts they cannot work (i.e., complete availability of every nurse for every shift no longer applies)
With all of the above constraints in place, I am fairly confident that the conditions are satisfied for the problem to be NP-complete (but I would appreciate confirmation even of that!).
What are the minimum hard constraints for the nurse scheduling problem to be NP-complete?