nurses.py¶
This example solves the problem of finding an optimal assignment of nurses to shifts.
1# --------------------------------------------------------------------------
2# Source file provided under Apache License, Version 2.0, January 2004,
3# http://www.apache.org/licenses/
4# (c) Copyright IBM Corp. 2015, 2018
5# --------------------------------------------------------------------------
6
7from collections import namedtuple
8
9from docplex.mp.model import Model
10from docplex.util.environment import get_environment
11
12# ----------------------------------------------------------------------------
13# Initialize the problem data
14# ----------------------------------------------------------------------------
15
16# utility to convert a weekday string to an index in 0..6
17_all_days = ["monday",
18 "tuesday",
19 "wednesday",
20 "thursday",
21 "friday",
22 "saturday",
23 "sunday"]
24
25
26def day_to_day_week(day):
27 day_map = {day: d for d, day in enumerate(_all_days)}
28 return day_map[day.lower()]
29
30
31TWorkRules = namedtuple("TWorkRules", ["work_time_max"])
32TVacation = namedtuple("TVacation", ["nurse", "day"])
33TNursePair = namedtuple("TNursePair", ["firstNurse", "secondNurse"])
34TSkillRequirement = namedtuple("TSkillRequirement", ["department", "skill", "required"])
35
36
37NURSES = [("Anne", 11, 1, 25),
38 ("Bethanie", 4, 5, 28),
39 ("Betsy", 2, 2, 17),
40 ("Cathy", 2, 2, 17),
41 ("Cecilia", 9, 5, 38),
42 ("Chris", 11, 4, 38),
43 ("Cindy", 5, 2, 21),
44 ("David", 1, 2, 15),
45 ("Debbie", 7, 2, 24),
46 ("Dee", 3, 3, 21),
47 ("Gloria", 8, 2, 25),
48 ("Isabelle", 3, 1, 16),
49 ("Jane", 3, 4, 23),
50 ("Janelle", 4, 3, 22),
51 ("Janice", 2, 2, 17),
52 ("Jemma", 2, 4, 22),
53 ("Joan", 5, 3, 24),
54 ("Joyce", 8, 3, 29),
55 ("Jude", 4, 3, 22),
56 ("Julie", 6, 2, 22),
57 ("Juliet", 7, 4, 31),
58 ("Kate", 5, 3, 24),
59 ("Nancy", 8, 4, 32),
60 ("Nathalie", 9, 5, 38),
61 ("Nicole", 0, 2, 14),
62 ("Patricia", 1, 1, 13),
63 ("Patrick", 6, 1, 19),
64 ("Roberta", 3, 5, 26),
65 ("Suzanne", 5, 1, 18),
66 ("Vickie", 7, 1, 20),
67 ("Wendie", 5, 2, 21),
68 ("Zoe", 8, 3, 29)
69 ]
70
71SHIFTS = [("Emergency", "monday", 2, 8, 3, 5),
72 ("Emergency", "monday", 8, 12, 4, 7),
73 ("Emergency", "monday", 12, 18, 2, 5),
74 ("Emergency", "monday", 18, 2, 3, 7),
75 ("Consultation", "monday", 8, 12, 10, 13),
76 ("Consultation", "monday", 12, 18, 8, 12),
77 ("Cardiac_Care", "monday", 8, 12, 10, 13),
78 ("Cardiac_Care", "monday", 12, 18, 8, 12),
79 ("Emergency", "tuesday", 8, 12, 4, 7),
80 ("Emergency", "tuesday", 12, 18, 2, 5),
81 ("Emergency", "tuesday", 18, 2, 3, 7),
82 ("Consultation", "tuesday", 8, 12, 10, 13),
83 ("Consultation", "tuesday", 12, 18, 8, 12),
84 ("Cardiac_Care", "tuesday", 8, 12, 4, 7),
85 ("Cardiac_Care", "tuesday", 12, 18, 2, 5),
86 ("Cardiac_Care", "tuesday", 18, 2, 3, 7),
87 ("Emergency", "wednesday", 2, 8, 3, 5),
88 ("Emergency", "wednesday", 8, 12, 4, 7),
89 ("Emergency", "wednesday", 12, 18, 2, 5),
90 ("Emergency", "wednesday", 18, 2, 3, 7),
91 ("Consultation", "wednesday", 8, 12, 10, 13),
92 ("Consultation", "wednesday", 12, 18, 8, 12),
93 ("Emergency", "thursday", 2, 8, 3, 5),
94 ("Emergency", "thursday", 8, 12, 4, 7),
95 ("Emergency", "thursday", 12, 18, 2, 5),
96 ("Emergency", "thursday", 18, 2, 3, 7),
97 ("Consultation", "thursday", 8, 12, 10, 13),
98 ("Consultation", "thursday", 12, 18, 8, 12),
99 ("Emergency", "friday", 2, 8, 3, 5),
100 ("Emergency", "friday", 8, 12, 4, 7),
101 ("Emergency", "friday", 12, 18, 2, 5),
102 ("Emergency", "friday", 18, 2, 3, 7),
103 ("Consultation", "friday", 8, 12, 10, 13),
104 ("Consultation", "friday", 12, 18, 8, 12),
105 ("Emergency", "saturday", 2, 12, 5, 7),
106 ("Emergency", "saturday", 12, 20, 7, 9),
107 ("Emergency", "saturday", 20, 2, 12, 12),
108 ("Emergency", "sunday", 2, 12, 5, 7),
109 ("Emergency", "sunday", 12, 20, 7, 9),
110 ("Emergency", "sunday", 20, 2, 12, 12),
111 ("Geriatrics", "sunday", 8, 10, 2, 5)]
112
113NURSE_SKILLS = {"Anne": ["Anaesthesiology", "Oncology", "Pediatrics"],
114 "Betsy": ["Cardiac_Care"],
115 "Cathy": ["Anaesthesiology"],
116 "Cecilia": ["Anaesthesiology", "Oncology", "Pediatrics"],
117 "Chris": ["Cardiac_Care", "Oncology", "Geriatrics"],
118 "Gloria": ["Pediatrics"], "Jemma": ["Cardiac_Care"],
119 "Joyce": ["Anaesthesiology", "Pediatrics"],
120 "Julie": ["Geriatrics"], "Juliet": ["Pediatrics"],
121 "Kate": ["Pediatrics"], "Nancy": ["Cardiac_Care"],
122 "Nathalie": ["Anaesthesiology", "Geriatrics"],
123 "Patrick": ["Oncology"], "Suzanne": ["Pediatrics"],
124 "Wendie": ["Geriatrics"],
125 "Zoe": ["Cardiac_Care"]
126 }
127
128VACATIONS = [("Anne", "friday"),
129 ("Anne", "sunday"),
130 ("Cathy", "thursday"),
131 ("Cathy", "tuesday"),
132 ("Joan", "thursday"),
133 ("Joan", "saturday"),
134 ("Juliet", "monday"),
135 ("Juliet", "tuesday"),
136 ("Juliet", "thursday"),
137 ("Nathalie", "sunday"),
138 ("Nathalie", "thursday"),
139 ("Isabelle", "monday"),
140 ("Isabelle", "thursday"),
141 ("Patricia", "saturday"),
142 ("Patricia", "wednesday"),
143 ("Nicole", "friday"),
144 ("Nicole", "wednesday"),
145 ("Jude", "tuesday"),
146 ("Jude", "friday"),
147 ("Debbie", "saturday"),
148 ("Debbie", "wednesday"),
149 ("Joyce", "sunday"),
150 ("Joyce", "thursday"),
151 ("Chris", "thursday"),
152 ("Chris", "tuesday"),
153 ("Cecilia", "friday"),
154 ("Cecilia", "wednesday"),
155 ("Patrick", "saturday"),
156 ("Patrick", "sunday"),
157 ("Cindy", "sunday"),
158 ("Dee", "tuesday"),
159 ("Dee", "friday"),
160 ("Jemma", "friday"),
161 ("Jemma", "wednesday"),
162 ("Bethanie", "wednesday"),
163 ("Bethanie", "tuesday"),
164 ("Betsy", "monday"),
165 ("Betsy", "thursday"),
166 ("David", "monday"),
167 ("Gloria", "monday"),
168 ("Jane", "saturday"),
169 ("Jane", "sunday"),
170 ("Janelle", "wednesday"),
171 ("Janelle", "friday"),
172 ("Julie", "sunday"),
173 ("Kate", "tuesday"),
174 ("Kate", "monday"),
175 ("Nancy", "sunday"),
176 ("Roberta", "friday"),
177 ("Roberta", "saturday"),
178 ("Janice", "tuesday"),
179 ("Janice", "friday"),
180 ("Suzanne", "monday"),
181 ("Vickie", "wednesday"),
182 ("Vickie", "friday"),
183 ("Wendie", "thursday"),
184 ("Wendie", "saturday"),
185 ("Zoe", "saturday"),
186 ("Zoe", "sunday")]
187
188NURSE_ASSOCIATIONS = [("Isabelle", "Dee"),
189 ("Anne", "Patrick")]
190
191NURSE_INCOMPATIBILITIES = [("Patricia", "Patrick"),
192 ("Janice", "Wendie"),
193 ("Suzanne", "Betsy"),
194 ("Janelle", "Jane"),
195 ("Gloria", "David"),
196 ("Dee", "Jemma"),
197 ("Bethanie", "Dee"),
198 ("Roberta", "Zoe"),
199 ("Nicole", "Patricia"),
200 ("Vickie", "Dee"),
201 ("Joan", "Anne")
202 ]
203
204SKILL_REQUIREMENTS = [("Emergency", "Cardiac_Care", 1)]
205
206DEFAULT_WORK_RULES = TWorkRules(40)
207
208
209# ----------------------------------------------------------------------------
210# Prepare the data for modeling
211# ----------------------------------------------------------------------------
212# subclass the namedtuple to refine the str() method as the nurse's name
213class TNurse(namedtuple("TNurse1", ["name", "seniority", "qualification", "pay_rate"])):
214 def __str__(self):
215 return self.name
216
217
218# specialized namedtuple to redefine its str() method
219class TShift(namedtuple("TShift",
220 ["department", "day", "start_time", "end_time", "min_requirement", "max_requirement"])):
221
222 def __str__(self):
223 # keep first two characters in department, uppercase
224 dept2 = self.department[0:4].upper()
225 # keep 3 days of weekday
226 dayname = self.day[0:3]
227 return '{}_{}_{:02d}'.format(dept2, dayname, self.start_time).replace(" ", "_")
228
229
230class ShiftActivity(object):
231 @staticmethod
232 def to_abstime(day_index, time_of_day):
233 """ Convert a pair (day_index, time) into a number of hours since Monday 00:00
234
235 :param day_index: The index of the day from 1 to 7 (Monday is 1).
236 :param time_of_day: An integer number of hours.
237
238 :return:
239 """
240 time = 24 * (day_index - 1)
241 time += time_of_day
242 return time
243
244 def __init__(self, weekday, start_time_of_day, end_time_of_day):
245 assert (start_time_of_day >= 0)
246 assert (start_time_of_day <= 24)
247 assert (end_time_of_day >= 0)
248 assert (end_time_of_day <= 24)
249
250 self._weekday = weekday
251 self._start_time_of_day = start_time_of_day
252 self._end_time_of_day = end_time_of_day
253 # conversion to absolute time.
254 start_day_index = day_to_day_week(self._weekday)
255 self.start_time = self.to_abstime(start_day_index, start_time_of_day)
256 end_day_index = start_day_index if end_time_of_day > start_time_of_day else start_day_index + 1
257 self.end_time = self.to_abstime(end_day_index, end_time_of_day)
258 assert self.end_time > self.start_time
259
260 @property
261 def duration(self):
262 return self.end_time - self.start_time
263
264 def overlaps(self, other_shift):
265 if not isinstance(other_shift, ShiftActivity):
266 return False
267 else:
268 return other_shift.end_time > self.start_time and other_shift.start_time < self.end_time
269
270
271def solve(model, **kwargs):
272 # Here, we set the number of threads for CPLEX to 2 and set the time limit to 2mins.
273 model.parameters.threads = 2
274 model.parameters.timelimit = 120 # nurse should not take more than that !
275 sol = model.solve(log_output=True, **kwargs)
276 if sol is not None:
277 print("solution for a cost of {}".format(model.objective_value))
278 print_information(model)
279 print_solution(model)
280 return model.objective_value
281 else:
282 print("* model is infeasible")
283 return None
284
285
286def load_data(model, shifts_, nurses_, nurse_skills, vacations_=None,
287 nurse_associations_=None, nurse_imcompatibilities_=None, verbose=True):
288 """ Usage: load_data(shifts, nurses, nurse_skills, vacations) """
289 model.number_of_overlaps = 0
290 model.work_rules = DEFAULT_WORK_RULES
291 model.shifts = [TShift(*shift_row) for shift_row in shifts_]
292 model.nurses = [TNurse(*nurse_row) for nurse_row in nurses_]
293 model.skill_requirements = SKILL_REQUIREMENTS
294 model.nurse_skills = nurse_skills
295 # transactional data
296 model.vacations = [TVacation(*vacation_row) for vacation_row in vacations_] if vacations_ else []
297 model.nurse_associations = [TNursePair(*npr) for npr in nurse_associations_]\
298 if nurse_associations_ else []
299 model.nurse_incompatibilities = [TNursePair(*npr) for npr in nurse_imcompatibilities_]\
300 if nurse_imcompatibilities_ else []
301
302 # computed
303 model.departments = set(sh.department for sh in model.shifts)
304
305 if verbose:
306 print('#nurses: {0}'.format(len(model.nurses)))
307 print('#shifts: {0}'.format(len(model.shifts)))
308 print('#vacations: {0}'.format(len(model.vacations)))
309 print("#associations=%d" % len(model.nurse_associations))
310 print("#incompatibilities=%d" % len(model.nurse_incompatibilities))
311
312
313def setup_data(model):
314 """ compute internal data """
315 # compute shift activities (start, end duration) and stor ethem in a dict indexed by shifts
316 model.shift_activities = {s: ShiftActivity(s.day, s.start_time, s.end_time) for s in model.shifts}
317 # map from nurse names to nurse tuples.
318 model.nurses_by_id = {n.name: n for n in model.nurses}
319
320
321def setup_variables(model):
322 all_nurses, all_shifts = model.nurses, model.shifts
323 # one binary variable for each pair (nurse, shift) equal to 1 iff nurse n is assigned to shift s
324 model.nurse_assignment_vars = model.binary_var_matrix(all_nurses, all_shifts, 'NurseAssigned')
325 # for each nurse, allocate one variable for work time
326 model.nurse_work_time_vars = model.continuous_var_dict(all_nurses, lb=0, name='NurseWorkTime')
327 # and two variables for over_average and under-average work time
328 model.nurse_over_average_time_vars = model.continuous_var_dict(all_nurses, lb=0,
329 name='NurseOverAverageWorkTime')
330 model.nurse_under_average_time_vars = model.continuous_var_dict(all_nurses, lb=0,
331 name='NurseUnderAverageWorkTime')
332 # finally the global average work time
333 model.average_nurse_work_time = model.continuous_var(lb=0, name='AverageWorkTime')
334
335
336def setup_constraints(model):
337 all_nurses = model.nurses
338 all_shifts = model.shifts
339 nurse_assigned = model.nurse_assignment_vars
340 nurse_work_time = model.nurse_work_time_vars
341 shift_activities = model.shift_activities
342 nurses_by_id = model.nurses_by_id
343 max_work_time = model.work_rules.work_time_max
344
345 # define average
346 model.add_constraint(
347 len(all_nurses) * model.average_nurse_work_time == model.sum(nurse_work_time[n] for n in all_nurses), "average")
348
349 # compute nurse work time , average and under, over
350 for n in all_nurses:
351 work_time_var = nurse_work_time[n]
352 model.add_constraint(
353 work_time_var == model.sum(nurse_assigned[n, s] * shift_activities[s].duration for s in all_shifts),
354 "work_time_{0!s}".format(n))
355
356 # relate over/under average worktime variables to the worktime variables
357 # the trick here is that variables have zero lower bound
358 # however, thse variables are not completely defined by this constraint,
359 # only their difference is.
360 # if these variables are part of the objective, CPLEX wil naturally minimize their value,
361 # as expected
362 model.add_constraint(
363 work_time_var == model.average_nurse_work_time
364 + model.nurse_over_average_time_vars[n]
365 - model.nurse_under_average_time_vars[n],
366 "average_work_time_{0!s}".format(n))
367
368 # state the maximum work time as a constraint, so that is can be relaxed,
369 # should the problem become infeasible.
370 model.add_constraint(work_time_var <= max_work_time, "max_time_{0!s}".format(n))
371
372 # vacations
373 v = 0
374 for vac_nurse_id, vac_day in model.vacations:
375 vac_n = nurses_by_id[vac_nurse_id]
376 for shift in (s for s in all_shifts if s.day == vac_day):
377 v += 1
378 model.add_constraint(nurse_assigned[vac_n, shift] == 0,
379 "medium_vacations_{0!s}_{1!s}_{2!s}".format(vac_n, vac_day, shift))
380 #print('#vacation cts: {0}'.format(v))
381
382 # a nurse cannot be assigned overlapping shifts
383 # post only one constraint per couple(s1, s2)
384 number_of_overlaps = 0
385 nb_shifts = len(all_shifts)
386 for i1 in range(nb_shifts):
387 for i2 in range(i1 + 1, nb_shifts):
388 s1 = all_shifts[i1]
389 s2 = all_shifts[i2]
390 if shift_activities[s1].overlaps(shift_activities[s2]):
391 number_of_overlaps += 1
392 for n in all_nurses:
393 model.add_constraint(nurse_assigned[n, s1] + nurse_assigned[n, s2] <= 1,
394 "high_overlapping_{0!s}_{1!s}_{2!s}".format(s1, s2, n))
395 #print('# overlapping cts: {0}'.format(number_of_overlaps))
396
397 for s in all_shifts:
398 demand_min = s.min_requirement
399 demand_max = s.max_requirement
400 total_assigned = model.sum(nurse_assigned[n, s] for n in model.nurses)
401 model.add_constraint(total_assigned >= demand_min,
402 "high_req_min_{0!s}_{1}".format(s, demand_min))
403 model.add_constraint(total_assigned <= demand_max,
404 "medium_req_max_{0!s}_{1}".format(s, demand_max))
405 model.add_constraint(total_assigned >= 1, "mandatory_presence_{0!s}".format(s))
406
407 for (dept, skill, required) in model.skill_requirements:
408 if required > 0:
409 for dsh in (s for s in all_shifts if dept == s.department):
410 model.add_constraint(model.sum(nurse_assigned[skilled_nurse, dsh] for skilled_nurse in
411 (n for n in all_nurses if
412 n.name in model.nurse_skills.keys() and skill in model.nurse_skills[
413 n.name])) >= required,
414 "high_required_{0!s}_{1!s}_{2!s}_{3!s}".format(dept, skill, required, dsh))
415
416 # nurse-nurse associations
417 # for each pair of associated nurses, their assignment variables are equal
418 # over all shifts.
419 c = 0
420 for (nurse_id1, nurse_id2) in model.nurse_associations:
421 if nurse_id1 in nurses_by_id and nurse_id2 in nurses_by_id:
422 nurse1 = nurses_by_id[nurse_id1]
423 nurse2 = nurses_by_id[nurse_id2]
424 for s in all_shifts:
425 c += 1
426 ctname = 'medium_ct_nurse_assoc_{0!s}_{1!s}_{2:d}'.format(nurse_id1, nurse_id2, c)
427 model.add_constraint(nurse_assigned[nurse1, s] == nurse_assigned[nurse2, s], ctname)
428
429 # nurse-nurse incompatibilities
430 # for each pair of incompatible nurses, the sum of assigned variables is less than one
431 # in other terms, both nurses can never be assigned to the same shift
432 c = 0
433 for (nurse_id1, nurse_id2) in model.nurse_incompatibilities:
434 if nurse_id1 in nurses_by_id and nurse_id2 in nurses_by_id:
435 nurse1 = nurses_by_id[nurse_id1]
436 nurse2 = nurses_by_id[nurse_id2]
437 for s in all_shifts:
438 c += 1
439 ctname = 'medium_ct_nurse_incompat_{0!s}_{1!s}_{2:d}'.format(nurse_id1, nurse_id2, c)
440 model.add_constraint(nurse_assigned[nurse1, s] + nurse_assigned[nurse2, s] <= 1, ctname)
441
442 model.total_number_of_assignments = model.sum(nurse_assigned[n, s] for n in all_nurses for s in all_shifts)
443 # model.nurse_costs = [model.nurse_assignment_vars[n, s] * n.pay_rate * model.shift_activities[s].duration
444 # for n in model.nurses for s in model.shifts]
445
446 def assignment_cost_f(ns):
447 n, s = ns
448 return n.pay_rate * model.shift_activities[s].duration
449
450 model.nurse_costs = model.scal_prod_f(nurse_assigned, assignment_cost_f)
451 model.total_salary_cost = model.sum(model.nurse_costs)
452
453
454def setup_objective(model):
455 model.add_kpi(model.total_salary_cost, "Total salary cost")
456 model.add_kpi(model.total_number_of_assignments, "Total number of assignments")
457 model.add_kpi(model.average_nurse_work_time, "average work time")
458
459 total_over_average_worktime = model.sum(model.nurse_over_average_time_vars[n] for n in model.nurses)
460 total_under_average_worktime = model.sum(model.nurse_under_average_time_vars[n] for n in model.nurses)
461 model.add_kpi(total_over_average_worktime, "Total over-average worktime")
462 model.add_kpi(total_under_average_worktime, "Total under-average worktime")
463 total_fairness = total_over_average_worktime + total_under_average_worktime
464 model.add_kpi(total_fairness, "Total fairness")
465
466 model.minimize(model.total_salary_cost + total_fairness + model.total_number_of_assignments)
467
468
469def print_information(model):
470 print("#shifts=%d" % len(model.shifts))
471 print("#nurses=%d" % len(model.nurses))
472 print("#vacations=%d" % len(model.vacations))
473 print("#nurse skills=%d" % len(model.nurse_skills))
474 print("#nurse associations=%d" % len(model.nurse_associations))
475 print("#incompatibilities=%d" % len(model.nurse_incompatibilities))
476 model.print_information()
477 model.report_kpis()
478
479
480def print_solution(model):
481 print("*************************** Solution ***************************")
482 print("Allocation By Department:")
483 for d in model.departments:
484 print("\t{}: {}".format(d, sum(
485 model.nurse_assignment_vars[n, s].solution_value for n in model.nurses for s in model.shifts if
486 s.department == d)))
487 print("Cost By Department:")
488 for d in model.departments:
489 cost = sum(
490 model.nurse_assignment_vars[n, s].solution_value * n.pay_rate * model.shift_activities[s].duration for n in
491 model.nurses for s in model.shifts if s.department == d)
492 print("\t{}: {}".format(d, cost))
493 print("Nurses Assignments")
494 for n in sorted(model.nurses):
495 total_hours = sum(
496 model.nurse_assignment_vars[n, s].solution_value * model.shift_activities[s].duration for s in model.shifts)
497 print("\t{}: total hours:{}".format(n.name, total_hours))
498 for s in model.shifts:
499 if model.nurse_assignment_vars[n, s].solution_value == 1:
500 print("\t\t{}: {} {}-{}".format(s.day, s.department, s.start_time, s.end_time))
501
502
503# ----------------------------------------------------------------------------
504# Build the model
505# ----------------------------------------------------------------------------
506
507def build(context=None, verbose=False, **kwargs):
508 mdl = Model("Nurses", context=context, **kwargs)
509 load_data(mdl, SHIFTS, NURSES, NURSE_SKILLS, VACATIONS, NURSE_ASSOCIATIONS,
510 NURSE_INCOMPATIBILITIES, verbose=verbose)
511 setup_data(mdl)
512 setup_variables(mdl)
513 setup_constraints(mdl)
514 setup_objective(mdl)
515 return mdl
516
517
518# ----------------------------------------------------------------------------
519# Solve the model and display the result
520# ----------------------------------------------------------------------------
521
522if __name__ == '__main__':
523 # Build model
524 model = build()
525
526 # Solve the model and print solution
527 solve(model)
528
529 # Save the CPLEX solution as "solution.json" program output
530 with get_environment().get_output_stream("solution.json") as fp:
531 model.solution.export(fp, "json")
532 model.end()