I'm new in CPLEX Optminization and at the moment, I'm writing a model that should assign nurses to surgery cases that fit their competences, specialty…
Actually I thought that the model is working correctly, but when I am trying it, it assigns nurses to cases, in which they are not allowed to work.
I hope somebody here will make time to look at the model and can help me. So here is the existing model (very easy at the moment with 5 nurses and one case):
.mod:
// indices
tuple nurses {
key int number_nurses ;
string roles ;
string specialty ;
string compentency ;
int shift_start ;
int shift_end ;
}
tuple shifts {
int shift_start ;
int shift_end ;
}
{shifts} shift = ... ;
{nurses} nurse = ... ;
int j = ... ;
range available_ORs = 1..j ;
{string} roles = ... ;
{string} specialty = ... ;
tuple cases {
key int number_cases ;
int start_time ;
int end_time ;
int duration ;
int demand_RN ;
int demand_ST ;
int available_ORs ;
string specialty_needed ;
string competency_needed ;
}
{cases} case = ... ;
//{string} shifts = ... ;
{string} competency = ... ;
int h = ... ;
range time_intervals = 1..h ;
// parameters
int P1 [nurse][shift] = ... ;
int P2 [nurse][roles][specialty][competency] = ... ;
int P3 [case][available_ORs] = ... ;
int P4 [time_intervals][case][specialty][competency] = ... ; // Auf Complexity innerhalb des Cases zugreifen
int P5 [time_intervals][case][roles] = ... ;
int P6 [case][time_intervals] = ... ;
int P7 [case] = ... ;
int P8 [time_intervals][shift] = ...;
int M = ... ;
// decision variables
dvar boolean y [nurse][case][roles][time_intervals] in 0..1 ; // 1: Nurse is assigened to case to perform role in time interval, 0: otherwise
dvar boolean x [nurse][case][roles] in 0..1 ;
dvar int de [time_intervals][case][roles] in 0..1 ;
dvar int dev [time_intervals][nurse] in 0..1 ;
dvar int dev2 [nurse][time_intervals] in 0..1 ;
dvar int xdev [nurse][available_ORs] in 0..1 ;
dvar int nc [nurse][case] in 0..1 ;
dvar int cd [nurse][case] in 0..1 ;
// deviation variable
dvar int DE ;
dvar int DS ;
dvar int DF ;
dvar int XDEV ;
dvar int NCT ;
dvar int CDT ;
// Objective function
minimize (DE+DF+DS+XDEV+NCT+CDT) ;
// Hard Constraints
subject to {
forall (i in nurse, h in time_intervals)
cons_01: // each nurse is assigned to at most one case in each time interval and performs a single role
sum (c in case,k in roles) y[i][c][k][h] <= 1 ;
forall (i in nurse, c in case, k in roles, h in time_intervals)
cons_02: // in each shift, cases will be assigned to the nurses who are working during their regular or authorized overtime hours
y[i][c][k][h] <= sum (s in shift) ((P1[i][s])*P8[h][s]) ;
forall (i in nurse)
cons_03: //total working hours for a nurse each day must be less than his or her total regular and overtime working hours
sum (c in case, k in roles, h in time_intervals) y[i][c][k][h] <= sum (s in shift, h in time_intervals) ((P1[i][s])*P8[h][s]) ;
forall (i in nurse, c in case, k in roles, h in time_intervals)
cons_04: // assigned to a case only if their skill level is high enough to handle the specialty requirements and have sufficient competency to deal with its procedural complexities
y[i][c][k][h] <= P6[c][h]*sum (q in specialty, p in competency) (P4[h][c][q][p]*P2[i][k][q][p]) ;
forall (c in case, k in roles, h in time_intervals)
cons_05: // see cons_04
sum (i in nurse) y[i][c][k][h] >= P6[c][h] ;
forall (i in nurse, c in case, k in roles)
cons_06: //nurses perform the same role for the entire duration of a case
sum (h in time_intervals) y[i][c][k][h] <= M * x[i][c][k] ;
forall (i in nurse, c in case)
cons_07: // see cons_06
sum (k in roles) x[i][c][k] <= 1 ;
}
// soft constraints
subject to {
forall (c in case, k in roles, h in time_intervals)
cons_08: // permit undercoverage, preferred that nurses work continuously during their regular hours rather than having idle perijjjods
sum (i in nurse) y[i][c][k][h] * de[h][c][k] >= P5[h][c][k] * P6[c][h] ; //momentan zu viele nurses, daher zu viele Zuordnungen
forall (c in case, k in roles)
cons_09: // see cons_08
DE >= sum (h in time_intervals) de[h][c][k] ;
/*forall (i in nurse, h in time_intervals)
cons_10: // avoid idle times: maximum number of times that nurses work nonconsecutive hours will be minimized along with idle time hours during the shift
-dev[h][i] <= sum (c in case, k in roles) y[i][c][k][h+1] - sum (c in case, k in roles) y[i][c][k][h] <=dev[h][i] ;*/
forall (i in nurse)
cons_11: // see cons_10
DS >= sum (h in time_intervals) dev[h][i] ;
forall(i in nurse, j in available_ORs)
cons_12: // account for the preference that nurses work continuously in one operating room: maximum number of ORs is reduced as much as possible
sum (c in case, k in roles, h in time_intervals) (y[i][c][k][h] * P3[c][j]) <= M * xdev[i][j] ;
forall (i in nurse)
cons_13: // see cons_12
sum (j in available_ORs) xdev[i][j] <= XDEV ;
forall (i in nurse, h in time_intervals)
cons_14: // record overtime: maximum number of times a nurse is working during overtime is as low as possible
sum (s in shift) P1[i][s] * 1 * sum (c in case, k in roles) y [i][c][k][h] <= dev2[i][h] ;
forall (i in nurse)
cons_15: // see cons_14
DF >= sum (h in time_intervals) dev2[i][h] ;
forall (i in nurse, c in case)
cons_16: // if nurse assigned to surgery, (s)he will stay for entire duration of the case unless there is a greater need for that nurse elseway, limit the movement of nurses between cases
sum (k in roles, h in time_intervals) y[i][c][k][h] - P7[c] + M * cd[i][c] + M * (1 - nc[i][c]) >= 0 ;
forall (i in nurse, c in case)
cons_17: // see cons_16
sum (k in roles, h in time_intervals) y[i][c][k][h] <= M * nc[i][c] ;
forall (i in nurse)
cons_18: // see cons_16
sum (c in case) nc[i][c] <= NCT ;
forall (i in nurse)
cons_19: // see cons_16
sum (c in case) cd[i][c] <= CDT ;
}
dat.
nurse = {
< 1, "RN", "cardio", "high", 6, 14 > ,
< 2, "ST", "cardio", "high", 10, 18 > ,
< 3, "RN", "neuro", "high", 14, 22 > ,
< 4, "RN", "cardio", "intermediate", 14, 22 > ,
< 5, "RN", "cardio", "high", 22, 6 > ,
} ;
j = 2 ;
roles = { "RN" , "ST" } ; // RN can work as ST if necessary, but a ST can not work as RN
specialty = { "ortho", "neuro", "cardio" } ;
case = {
< 1, 8, 15, 7, 1, 0, 1, "cardio", "intermediate" > ,
} ;
shift = { < 6, 14 > < 10, 18 > < 14, 22 > < 22, 6 >} ;
competency = { "low", "intermediate", "high" } ;
h = 24 ;
// Parameter
P1 = [
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 1 0]
[0 0 0 1]
] ;
P2 = [
[[[1 1 1][0 0 0][0 0 0]][[1 1 1][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]][[1 1 1][0 0 0][0 0 0]]]
[[[0 0 0][1 1 1][0 0 0]][[0 0 0][1 1 1][0 0 0]]]
[[[1 1 0][0 0 0][0 0 0]][[1 1 0][0 0 0][0 0 0]]]
[[[1 1 1][0 0 0][0 0 0]][[1 1 1][0 0 0][0 0 0]]]
] ;
P3 = [
[1 0]
] ;
P4 = [
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 1 0][0 0 0][0 0 0]]]
[[[0 1 0][0 0 0][0 0 0]]]
[[[0 1 0][0 0 0][0 0 0]]]
[[[0 1 0][0 0 0][0 0 0]]]
[[[0 1 0][0 0 0][0 0 0]]]
[[[0 1 0][0 0 0][0 0 0]]]
[[[0 1 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
[[[0 0 0][0 0 0][0 0 0]]]
] ;
P5 = [
[[0 0]]
[[0 0]]
[[0 0]]
[[0 0]]
[[0 0]]
[[0 0]]
[[0 0]]
[[1 0]]
[[1 0]]
[[1 0]]
[[1 0]]
[[1 0]]
[[1 0]]
[[1 0]]
[[0 0]]
[[0 0]]
[[0 0]]
[[0 0]]
[[0 0]]
[[0 0]]
[[0 0]]
[[0 0]]
[[0 0]]
[[0 0]]
] ;
P6 = [
[0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 ]
] ;
P7 = [7] ;
P8 = [
[0 0 0 1]
[0 0 0 1]
[0 0 0 1]
[0 0 0 1]
[0 0 0 1]
[1 0 0 0]
[1 0 0 0]
[1 0 0 0]
[1 0 0 0]
[1 1 0 0]
[1 1 0 0]
[1 1 0 0]
[1 1 0 0]
[0 1 1 0]
[0 1 1 0]
[0 1 1 0]
[0 1 1 0]
[0 0 1 0]
[0 0 1 0]
[0 0 1 0]
[0 0 1 0]
[0 0 0 1]
[0 0 0 1]
[0 0 0 1]
] ;
M = 10 ;
When I run it, it assigns the second nurse to the case, but actually the nurse 2 is not allowed to work in this case because a RN is needed. I already tried different possibilities to write it, but I don't find the reason why…
At the moment, nurse 1 and nurse 4 are assigned as RN (which is right) and additionally also Nurse 2.
Can anybody give me some tipps or help to solve the optimization problem correctly? I would be very grateful, thank you in advance.
Your model is not feasible and CPLEX relaxed it. It relaxed some labeled constraints and gave you the relaxed solution. Having a look at the relaxed solution will help you debug your model.
In cplex documentation you could have a look at:
IDE and OPL > CPLEX Studio IDE > IDE Tutorials
Relaxing infeasible models