komputerwiz
commented
8 years ago Ruby appears to be Turing-complete. Therefore, so long as a problem is tractable, I'm sure there's a way to solve it in Ruby. :smiley:
I was unfamiliar with the nurse scheduling problem prior to this, but after a bit of research, here's my two cents on the problem:
First, this library is not built to handle soft constraints; only hard constraints. There are a few algorithms dedicated to "constrained optimization" problems, the general case of this problem, but we can still attempt to solve this problem by treating all constraints as hard constraints.
The problem as I understand it is as follows:
- There are three shifts each day: day, evening, and night.
- Nurses are assigned to work one shift each day and not two consecutive shifts
- Nurses can request holidays on which they are not scheduled to work
- There must be "enough" nurses to care for patients (let's generalize this by saying that there should be at least n nurses on staff during each shift.
To build a constraint satisfaction problem (CSP) from this set of information, we need to choose variables, a set of constraints among sets of these variables, and assignable domain values for each variable. The CSP solver will do the rest by returning an assignment that does not violate any constraints.
Let's make a 2-day schedule (6 shifts), and there have to be 2 nurses on staff for each. Thus I'll choose to create two variables for each shift (each variable representing a position to be filled) for a total of 12 variables. I'll use the naming convention "day #, shift, position #" for my variable names:
d1_day_1d1_day_2d1_evening_1d1_evening_2d1_night_1d1_night_2d2_day_1d2_day_2d2_evening_1d2_evening_2d2_night_1d2_night_2
Naturally, this would mean that the available nurses to fill positions are our domain values for these variables. If a nurse requests a holiday for day 2, then that person should not be in the domain of those variables. Suppose we have 8 nurses, A through H. Clever names, I know, but bear with me.
Now for our constraints. I'll use a globbing shorthand to keep it concise:
- a nurse may work no more than one shift each day:
all_different(d1_*),all_different(d2_*) - a nurse may not work two consecutive shifts. The only cases not covered by the above conditions are the day 1 night shifts to the day 2 day shifts:
constrain(d1_night*, d2_day*) { |a,b| a != b }
That should be all of the information needed to solve the problem. Let me know if any part of this was unclear.
retorquere
mooreniemi
nurettin
I know I can in principle do this with OptaPlanner, but ruby is my language of preference, so if it can be done in ruby that would be really nice.