1.8. The Nurse Scheduling Problem#
Imagine you are responsible for scheduling the shifts for the nurses in your hospital department for this week. There are three shifts in a day – morning, afternoon, and night – and for each shift, you need to assign one or more of the eight nurses that work in your department. If this sounds like a simple task, take a look at the list of relevant hospital rules:
A nurse is not allowed to work two consecutive shifts.
A nurse is not allowed to work more than five shifts per week.
The number of nurses per shift in your department should fall within the following limits:
Morning shift: 2–3 nurses
Afternoon shift: 2–4 nurses
Night shift: 1–2 nurses
In addition, each nurse can have shift preferences. For example, one nurse prefers to only work morning shifts, another nurse prefers to not work afternoon shifts, and so on. This task is an example of the nurse scheduling problem (NSP), which can have many variants. Possible variations may include different specialties for different nurses, the ability to work on cover shifts (overtime), or even different types of shifts – such as 8-hour shifts and 12-hour shifts.
By now, it probably looks like a good idea to write a program that will do the scheduling for you. Why not apply our knowledge of genetic algorithms to implement such a program? As usual, we will start by representing the solution to the problem
1.8.1. Create The Nurse Scheduling Problem#
Create a class called NurseSchedulingProblem that will represent the nurse scheduling problem with the following methods:
__init__(self, penality): Initializes the class with the given hardConstraintPenalty value. This value will be used to calculate the total cost of the violations in the schedule.The class uses the following method to convert the given schedule into a dictionary with a separate schedule for each nurse:
getNurseShifts(schedule)
The following methods are used to count the various types of violations:
countConsecutiveShiftViolations(nurseShiftsDict)
countShiftsPerWeekViolations(nurseShiftsDict)
countNursesPerShiftViolations(nurseShiftsDict)
countShiftPreferenceViolations(nurseShiftsDict)
getCost(schedule): Calculates the total cost of the various violations in the given schedule. This method uses the value of the hardConstraintPenalty variable.printScheduleInfo(schedule): Prints the schedule and violations details.
Should allow the following sample implementation
nurses = NurseSchedulingProblem(10)
randomSolution = np.random.randint(2, size=len(nurses))
print("Random Solution = ")
print(randomSolution)
print()
nurses.printScheduleInfo(randomSolution)
print("Total Cost = ", nurses.getCost(randomSolution))
Schedule for each nurse:
A : [0 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 1 1 1 1 0]
B : [0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 1 1 0 0]
C : [0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0 0 0 0 0]
D : [0 1 1 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0]
E : [1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1]
F : [1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1]
G : [0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1]
H : [1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0]
consecutive shift violations = 39
weekly Shifts = [12, 8, 9, 10, 8, 15, 10, 7]
Shifts Per Week Violations = 39
Nurses Per Shift = [3, 5, 4, 5, 3, 3, 5, 3, 3, 4, 3, 3, 5, 3, 3, 4, 3, 4, 5, 5, 3]
Nurses Per Shift Violations = 21
Shift Preference Violations = 30
Total Cost = 1020
1.8.1.1. Bas Code#
import numpy as np
class NurseSchedulingProblem:
"""This class encapsulates the Nurse Scheduling problem
"""
def __init__(self, hardConstraintPenalty):
"""
:param hardConstraintPenalty: the penalty factor for a hard-constraint violation
"""
self.hardConstraintPenalty = hardConstraintPenalty
# list of nurses:
self.nurses = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
# nurses' respective shift preferences - morning, evening, night:
self.shiftPreference = [[1, 0, 0], [1, 1, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 1, 1], [1, 1, 1]]
# min and max number of nurses allowed for each shift - morning, evening, night:
self.shiftMin = [2, 2, 1]
self.shiftMax = [3, 4, 2]
# max shifts per week allowed for each nurse
self.maxShiftsPerWeek = 5
# number of weeks we create a schedule for:
self.weeks = 1
# useful values:
self.shiftPerDay = len(self.shiftMin)
self.shiftsPerWeek = 7 * self.shiftPerDay
def __len__(self):
"""
:return: the number of shifts in the schedule
Used to generate the size of the individual array representation.
"""
return len(self.nurses) * self.shiftsPerWeek * self.weeks
def getCost(self, schedule):
"""
Calculates the total cost of the various violations in the given schedule
...
:param schedule: a list of binary values describing the given schedule
:return: the calculated cost
"""
if len(schedule) != self.__len__():
raise ValueError("size of schedule list should be equal to ", self.__len__())
# convert entire schedule into a dictionary with a separate schedule for each nurse:
nurseShiftsDict = self.getNurseShifts(schedule)
# count the various violations:
consecutiveShiftViolations = self.countConsecutiveShiftViolations(nurseShiftsDict)
shiftsPerWeekViolations = self.countShiftsPerWeekViolations(nurseShiftsDict)[1]
nursesPerShiftViolations = self.countNursesPerShiftViolations(nurseShiftsDict)[1]
shiftPreferenceViolations = self.countShiftPreferenceViolations(nurseShiftsDict)
# calculate the cost of the violations:
hardContstraintViolations = consecutiveShiftViolations + nursesPerShiftViolations + shiftsPerWeekViolations
softContstraintViolations = shiftPreferenceViolations
return self.hardConstraintPenalty * hardContstraintViolations + softContstraintViolations
def getNurseShifts(self, schedule) -> dict[str: list[int]]:
"""
Converts the entire schedule into a dictionary with a separate schedule for each nurse
:param schedule: a list of binary values describing the given schedule
:return: a dictionary with each nurse as a key and the corresponding shifts as the value
"""
shiftsPerNurse = self.__len__() // len(self.nurses)
nurseShiftsDict = {}
shiftIndex = 0
for nurse in self.nurses:
nurseShiftsDict[nurse] = schedule[shiftIndex:shiftIndex + shiftsPerNurse]
shiftIndex += shiftsPerNurse
return nurseShiftsDict
def countConsecutiveShiftViolations(self, nurseShiftsDict) -> int:
"""
Counts the consecutive shift violations in the schedule
:param nurseShiftsDict: a dictionary with a separate schedule for each nurse
:return: count of violations found
"""
violations = 0
# TODO iterate over the shifts of each nurse:
return violations
def countShiftsPerWeekViolations(self, nurseShiftsDict) -> set[int:int]:
"""
Counts the max-shifts-per-week violations in the schedule
:param nurseShiftsDict: a dictionary with a separate schedule for each nurse
:return: count of violations found
"""
violations = 0
weeklyShiftsList = []
# TODO iterate over the shifts of each nurse:
return weeklyShiftsList, violations
def countNursesPerShiftViolations(self, nurseShiftsDict) -> set[int:int]:
"""
Counts the number-of-nurses-per-shift violations in the schedule
:param nurseShiftsDict: a dictionary with a separate schedule for each nurse
:return: count of violations found
"""
# sum the shifts over all nurses:
totalPerShiftList = [sum(shift) for shift in zip(*nurseShiftsDict.values())]
violations = 0
# TODO iterate over all shifts and count violations:
return totalPerShiftList, violations
def countShiftPreferenceViolations(self, nurseShiftsDict) -> int:
"""
Counts the nurse-preferences violations in the schedule
:param nurseShiftsDict: a dictionary with a separate schedule for each nurse
:return: count of violations found
"""
violations = 0
# TOOD Complete
return violations
def printScheduleInfo(self, schedule):
"""
Prints the schedule and violations details
:param schedule: a list of binary values describing the given schedule
"""
pass
nurses = NurseSchedulingProblem(10)
randomSolution = np.random.randint(2, size=len(nurses))
print("Random Solution = ")
print(randomSolution)
print()
nurses.printScheduleInfo(randomSolution)
print("Total Cost = ", nurses.getCost(randomSolution))
Random Solution =
[0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1
0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1
0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1
1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1
0 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 1 0]
Total Cost = 0
1.8.2. Implement the Genetic Algorithm Solution#
1.8.2.1. Base Code#
from deap import base
from deap import creator
from deap import tools
import random
import numpy
import matplotlib.pyplot as plt
import seaborn as sns
import elitism
# problem constants:
# the penalty factor for a hard-constraint violation
# Genetic Algorithm constants:
POPULATION_SIZE = 300
P_CROSSOVER = 0.9 # probability for crossover
P_MUTATION = 0.1 # probability for mutating an individual
MAX_GENERATIONS = 200
HALL_OF_FAME_SIZE = 30
# set the random seed:
RANDOM_SEED = 42
random.seed(RANDOM_SEED)
toolbox = base.Toolbox()
# TODO Complete the operators below.
# create the nurse scheduling problem instance to be used:
# define a single objective, maximizing fitness strategy:
# create the Individual class based on list:
# create an operator that randomly returns 0 or 1:
# create the individual operator to fill up an Individual instance:
# create the population operator to generate a list of individuals:
# fitness calculation
def getCost(individual):
#TODO Complete
toolbox.register("evaluate", getCost)
# genetic operators:
toolbox.register("select", tools.selTournament, tournsize=2)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=1.0/len(nsp))
## TODO Complete the code below
# create initial population (generation 0):
population = toolbox.populationCreator(n=POPULATION_SIZE)
# TODO prepare the statistics object: define Statistics Fitness values + (min, avg)
# define the hall-of-fame object:
hof = tools.HallOfFame(HALL_OF_FAME_SIZE)
# perform the Genetic Algorithm flow with hof feature added:
population, logbook = elitism.eaSimpleWithElitism(population, toolbox, cxpb=P_CROSSOVER, mutpb=P_MUTATION,
ngen=MAX_GENERATIONS, stats=stats, halloffame=hof, verbose=True)
# TODO print best solution found:
# extract statistics:
minFitnessValues, meanFitnessValues = logbook.select("min", "avg")
# TODO plot statistics:
1.8.2.2. Solution#
from deap import base
from deap import creator
from deap import tools
import random
import numpy
import matplotlib.pyplot as plt
import seaborn as sns
import elitism
# problem constants:
HARD_CONSTRAINT_PENALTY = 10 # the penalty factor for a hard-constraint violation
# Genetic Algorithm constants:
POPULATION_SIZE = 300
P_CROSSOVER = 0.9 # probability for crossover
P_MUTATION = 0.1 # probability for mutating an individual
MAX_GENERATIONS = 200
HALL_OF_FAME_SIZE = 30
# set the random seed:
RANDOM_SEED = 42
random.seed(RANDOM_SEED)
toolbox = base.Toolbox()
# create the nurse scheduling problem instance to be used:
nsp = NurseSchedulingProblem(HARD_CONSTRAINT_PENALTY)
# define a single objective, maximizing fitness strategy:
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
# create the Individual class based on list:
creator.create("Individual", list, fitness=creator.FitnessMin)
# create an operator that randomly returns 0 or 1:
toolbox.register("zeroOrOne", random.randint, 0, 1)
# create the individual operator to fill up an Individual instance:
toolbox.register("individualCreator", tools.initRepeat, creator.Individual, toolbox.zeroOrOne, len(nsp))
# create the population operator to generate a list of individuals:
toolbox.register("populationCreator", tools.initRepeat, list, toolbox.individualCreator)
# fitness calculation
def getCost(individual):
return nsp.getCost(individual), # return a tuple
toolbox.register("evaluate", getCost)
# genetic operators:
toolbox.register("select", tools.selTournament, tournsize=2)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=1.0/len(nsp))
# create initial population (generation 0):
population = toolbox.populationCreator(n=POPULATION_SIZE)
# prepare the statistics object:
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min", numpy.min)
stats.register("avg", numpy.mean)
# define the hall-of-fame object:
hof = tools.HallOfFame(HALL_OF_FAME_SIZE)
# perform the Genetic Algorithm flow with hof feature added:
population, logbook = elitism.eaSimpleWithElitism(population, toolbox, cxpb=P_CROSSOVER, mutpb=P_MUTATION,
ngen=MAX_GENERATIONS, stats=stats, halloffame=hof, verbose=True)
# print best solution found:
best = hof.items[0]
print("-- Best Individual = ", best)
print("-- Best Fitness = ", best.fitness.values[0])
print()
print("-- Schedule = ")
nsp.printScheduleInfo(best)
# extract statistics:
minFitnessValues, meanFitnessValues = logbook.select("min", "avg")
# plot statistics:
sns.set_style("whitegrid")
plt.plot(minFitnessValues, color='red')
plt.plot(meanFitnessValues, color='green')
plt.xlabel('Generation')
plt.ylabel('Min / Average Fitness')
plt.title('Min and Average fitness over Generations')
plt.show()
gen nevals min avg
0 300 0 0
1 245 0 0
2 239 0 0
3 229 0 0
4 247 0 0
5 239 0 0
6 250 0 0
7 252 0 0
8 249 0 0
9 250 0 0
10 245 0 0
11 255 0 0
12 246 0 0
13 237 0 0
14 248 0 0
15 249 0 0
16 248 0 0
17 248 0 0
18 240 0 0
19 240 0 0
20 246 0 0
21 242 0 0
22 245 0 0
23 239 0 0
24 238 0 0
25 248 0 0
26 245 0 0
27 248 0 0
28 241 0 0
29 233 0 0
30 242 0 0
31 257 0 0
32 247 0 0
33 248 0 0
34 241 0 0
35 247 0 0
36 251 0 0
37 249 0 0
38 252 0 0
39 253 0 0
40 255 0 0
41 254 0 0
42 243 0 0
43 234 0 0
44 241 0 0
45 249 0 0
46 238 0 0
47 247 0 0
48 249 0 0
49 248 0 0
50 240 0 0
51 252 0 0
52 260 0 0
53 243 0 0
54 256 0 0
55 240 0 0
56 241 0 0
57 248 0 0
58 249 0 0
59 251 0 0
60 239 0 0
61 247 0 0
62 234 0 0
63 247 0 0
64 242 0 0
65 250 0 0
66 236 0 0
67 232 0 0
68 248 0 0
69 246 0 0
70 249 0 0
71 246 0 0
72 248 0 0
73 246 0 0
74 249 0 0
75 246 0 0
76 238 0 0
77 263 0 0
78 250 0 0
79 250 0 0
80 236 0 0
81 245 0 0
82 230 0 0
83 250 0 0
84 247 0 0
85 250 0 0
86 252 0 0
87 247 0 0
88 245 0 0
89 255 0 0
90 251 0 0
91 239 0 0
92 253 0 0
93 250 0 0
94 253 0 0
95 240 0 0
96 243 0 0
97 246 0 0
98 246 0 0
99 252 0 0
100 246 0 0
101 246 0 0
102 245 0 0
103 254 0 0
104 246 0 0
105 253 0 0
106 251 0 0
107 245 0 0
108 235 0 0
109 248 0 0
110 239 0 0
111 244 0 0
112 248 0 0
113 234 0 0
114 233 0 0
115 241 0 0
116 242 0 0
117 247 0 0
118 247 0 0
119 246 0 0
120 256 0 0
121 232 0 0
122 240 0 0
123 246 0 0
124 252 0 0
125 262 0 0
126 242 0 0
127 242 0 0
128 243 0 0
129 249 0 0
130 237 0 0
131 244 0 0
132 241 0 0
133 245 0 0
134 248 0 0
135 246 0 0
136 246 0 0
137 245 0 0
138 258 0 0
139 240 0 0
140 249 0 0
141 249 0 0
142 243 0 0
143 251 0 0
144 242 0 0
145 246 0 0
146 243 0 0
147 248 0 0
148 245 0 0
149 245 0 0
150 247 0 0
151 252 0 0
152 246 0 0
153 249 0 0
154 253 0 0
155 241 0 0
156 247 0 0
157 248 0 0
158 255 0 0
159 254 0 0
160 238 0 0
161 241 0 0
162 247 0 0
163 245 0 0
164 246 0 0
165 248 0 0
166 238 0 0
167 242 0 0
168 243 0 0
169 252 0 0
170 255 0 0
171 256 0 0
172 250 0 0
173 250 0 0
174 248 0 0
175 264 0 0
176 255 0 0
177 250 0 0
178 254 0 0
179 250 0 0
180 244 0 0
181 247 0 0
182 243 0 0
183 248 0 0
184 234 0 0
185 246 0 0
186 244 0 0
187 245 0 0
188 234 0 0
189 260 0 0
190 243 0 0
191 250 0 0
192 253 0 0
193 251 0 0
194 250 0 0
195 248 0 0
196 248 0 0
197 252 0 0
198 257 0 0
199 248 0 0
200 232 0 0
-- Best Individual = [1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0]
-- Best Fitness = 0.0
-- Schedule =
