Proceedings of the International Conference on Industrial & Mechanical Engineering and Operations Management
Dhaka, Bangladesh, December 26-27, 2020
A Linear Programming Problem Analysis for Improving the
Process and Quality of Nurse Rostering in the Covid-19 Unit
of a City Hospital
Tasnia Biswas and Afifa Sumaya
Department of Industrial and Production Engineering (IPE)
Bangladesh University of Engineering and Technology (BUET)
Dhaka, Bangladesh
tasniabiswas@gmail.com, eyantitushi19@gmail.com
Abstract
The COVID-19 pandemic has resulted in dedicated Covid-19 units in hospitals due to a surge in the number of patients
who require isolated intensive care. Optimizing the number of nurses in each shift to meet up with this seasonal peak
of the required service has been a great concern in the domain of healthcare as there is less availability of nurses who
are willing to work in Covid-19 units at the stake of their lives. Thus, it has become progressively important to present
an optimized nurse schedule that can be implemented with careful decision support systems in a cost-effective manner
while satisfying customer demand as well as other requirements such as a flexible workplace. This paper drives a
linear programming problem intended to improve both the process and the quality of nurse scheduling which
maximizes the fairness of the resulting schedule. A mathematical model is formulated and solved using big M simplex
algorithm to minimize the required number of nurses, in conjunction with a linear optimization of the scheduling
process. The data was collected from four distinct hospitals for checking statistical consistency and subsequently, a
case study from a major hospital is used throughout to illustrate the methodology and the optimal solution is
determined. Therefore, an optimized schedule has been proposed in which the required number of nurses is minimized
by balancing the trade-off between increasing demands and decreasing workforce.
Keywords
Linear Programming Problem (LPP), Hospital Management, COVID-19, Nurse Scheduling Problem (NSP),
Minimization
1. Introduction
In the Covid-19 pandemic there has been a surge in the number of patients who require isolated intensive care. There
are also shortages of beds and ICUs in the hospitals to cope up with the increasing quantities of Covid-19 positive
patients. At the same time, it is getting harder for the hospital authorities to recruit nurses for these wards as there is
less availability of nurses who are willing to work in Covid-19 units at the stake of their lives. Thus, the hospital
management must strategically plan to adapt quickly to the rapidly changing business environment in order to ensure
sustainable success. As a result, there has been a mounting pressure on the healthcare industry to develop an efficient
scheduling algorithm that seeks to satisfy the demand coverage and at the same time ensures team balance while
maximizing the nurses’ preferences.
Manual solution of the scheduling problem is usually limited to finding a feasible solution and is very time consuming,
with little focus on optimization, due to the complexity of collective agreement rules. Collective agreement rules are
requirements that help to define acceptable schedules for individual nurses in terms of workload, seniority, holidays,
weekends off and consecutive assignments including days off and possibly rotations. An assignment is the
specification of the shift that a given nurse must work on a given day. A shift is characterized by fixed starting and
ending times and has a daily label such as “day”, “evening” or “night”. A day is subdivided into several demand
periods characterized by fixed starting and ending times, which are identical for all days but do not necessarily coincide
with those of the shifts. A shift may, indeed, count for one or several demand periods.
To solve this trade-off between the increasing demand and decreasing workforce, it has become progressively
important to present an optimized nurse schedule that can be implemented with careful decision support systems in a
© IEOM Society International
Proceedings of the International Conference on Industrial & Mechanical Engineering and Operations Management
Dhaka, Bangladesh, December 26-27, 2020
cost-effective manner while satisfying customer demand as well as other requirements such as a flexible workplace.
This paper proposes a shift sequence for nurse rostering using linear programming problem to solve the nurse
scheduling problem where the objective is to maximize the fairness of the schedule, and to ensure that it can be easily
implemented in these hospitals at no added extra cost.
The terms are described by employing linearization method. The model is converted to a mixed linear programming
which can be efficiently solved using simplex method. The rest of this paper is organized as follows: in section 2,
literature review is described. In section 3, methodology and the mathematical programming formulation are
introduced. In section 4, all necessary data needed to formulate the optimization problem are listed. In section 5, there
are result and discussion on the formulation of the model in the form of linear programming. Section 6 ends with
conclusion. And at last, there are references.
1.1 Objectives
The objective of this study is to formulate a resource constrained linear programming problem and solve it to generate
a configuration of individual schedules while minimizing the number of nurses and maximizing nurses’ preferences
as well as care quality.
2. Literature Review
The paper attempts to investigate a nurse rostering methodology to improve the process and quality of nurse scheduling
that the hospital management can implement without extra hassles in order to meet the demand coverage form the
added amounts of patients who are covid-19 positive. It illustrates a suitable method for linear programming to solve
an instance of the nurse scheduling problem met in real city hospital, that guarantees a high level of fairness between
the nurses. The demand for nurses is relatively constant over a shift and nurses work standard 8-hours or 12-hours
shifts, with little or no variability in their starting times. In the service industry, some of the most studied applications
of personnel scheduling include call centre staffing, airline crew pairing, nurse rostering, and postal worker tour
construction. Literature on nurse rostering and scheduling is extensive. Several studies have employed optimization
methods to solve the NSP, like linear, integer or mixed integer programming, goal programming or constraint
programming. Many of more recent paper tackle the NSP with met heuristic methods such as genetic algorithms, tab
search or simulation.
Several very recent and complementary bibliographic surveys have been published and give a good overview of the
problem modelling and the various approaches (Cheang et al., 2003; Burke et al., 2004; Ernst et al., 2004). In the
literature, two types of scheduling can be found: cyclical and non-cyclical scheduling. A popular approach is to
construct cyclical schedules, where the same schedule is repeated as long as the requirements do not change. These
kinds of schedules are easy to build but may be very rigid, and may adapt difficulty to changes. In a non-cyclical
scheduling process, a new schedule is generated for each scheduling period. This process is more time- consuming
but is much more flexible to changes such as the variability of demand (Valouxis and Housos, 2000). Several studies
have employed optimization methods to solve the NSP, like linear, integer or mixed integer programming (Jaumard
et al., 1998), goal programming (Berrada et al., 1996) or constraint programming (Adbennadher and Schlenker, 1999).
Many of more recent papers tackle the NSP with metaheuristic methods such as genetic algorithms (Aickelin and
Dowsland, 2004), tab search (Berrada et al., 1996; Valouxis and Housos, 2000; Aickelin and Dowsland, 2004) or
simulated annealing (Brusco and Jacobs, 1995). We believe that resolution techniques involving the use of solvers are
more easily transferable to hospitals services. Other approaches, like heuristics or meta-heuristics are less accessible,
and could be time-consuming (Guinet, 1995). Hence contribution, related to existing approaches, is focused on the
linear programming problem, which seeks to satisfy the demand coverage while minimizing the salary cost and
maximizing the nurses’ preferences as well as team balance.
3. Methods
The problem is to determine the minimum number of nurses to meet all shifts requirements. Nurse scheduling aim is
to minimize changes to be original schedule while minimizing costs, to solve this trade-off between the increasing
demand and decreasing workforce in the Covid-19 unit of a city hospital.
3.1 Problem identification
Currently there is less availability of nurses who are willing to work in the covid-19 units. To meet the excess demand,
the paper proposes a 12-hours shift scheduling for the nurses instead of the 8-hours shift to get optimum number of
© IEOM Society International
Proceedings of the International Conference on Industrial & Mechanical Engineering and Operations Management
Dhaka, Bangladesh, December 26-27, 2020
total nurses. In this problem we must search for a solution satisfying as many wishes as possible while not
compromising the needs of the hospital. Some examples of constraints are:
A nurse does not work the day shift, night shift and late-night shift on the same day.
A nurse may go on a holiday and will not work shifts during this time.
A nurse does not do a late-night shift followed by a day shift the next day.
Constraints are usually divided into two groups: hard and soft constraints, which vary significantly with respect to
legal regulations and individual preferences, depending on individual institutions and countries. Hard constraints must
be satisfied to obtain feasible solutions. Soft constraints are desirable but not obligatory, and thus, can be violated. In
real nurse rostering settings, we noticed that the problems are nearly always over constrained. It is therefore quite
common to express the quality of solutions in terms of soft constraint violations. All the feasible weekly shift patterns
were pre-defined and associated with costs concerning preferences, requests, the number of successive days, etc. These
shift patterns were then used to construct nurse rosters by employing different heuristic decoders within a genetic
algorithm to schedule both shifts and patterns for the best permutations of nurses. The idea of permuting the nurses to
be scheduled is similar to the method presented in this paper.
3.2 Linear Programming model
The general structure of the Linear Programming model essentially consists of three components.
i) The activities (variables) and their relationships
ii) The objective function and
iii) The constraints
The activities are represented by 𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 , …, 𝑥𝑥 𝑛𝑛
These are known as decision variables.
The objective function of an LPP (Linear Programming Problem) is a mathematical representation of the objective in
terms of a measurable quantity such as profit, cost, revenue, etc.
Optimize (Maximize or Minimize) 𝑍𝑍 = 𝑐𝑐 1 𝑥𝑥 1 + 𝑐𝑐 2 𝑥𝑥 2 + 𝑐𝑐 3 𝑥𝑥 3 + ⋯ 𝑐𝑐 𝑛𝑛 𝑥𝑥 𝑛𝑛
Where, 𝑍𝑍 is the measure of performance variable,
𝑐𝑐 1 𝑥𝑥 1 + 𝑐𝑐 2 𝑥𝑥 2 + 𝑐𝑐 3 𝑥𝑥 3 + ⋯ 𝑐𝑐 𝑛𝑛 𝑥𝑥 𝑛𝑛 are the decision variables and 𝑐𝑐 1 , 𝑐𝑐 2 , 𝑐𝑐 3 , ⋯, 𝑐𝑐 𝑛𝑛 are the parameters that give contribution
to decision variables.
The constraints are the set of linear inequalities and/or equalities which impose restriction of the limited resources.
Assumptions
Certainty:
In all LP models it is assumed that, all the model parameters such as availability of resources, profit (or cost)
contribution of a unit of decision variable and consumption of resources by a unit of decision variable must be known
and constant.
Divisibility (Continuity):
The solution values of decision variables and resources are assumed to have either whole numbers (integers) or mixed
numbers (integer or fractional). However, if only integer variables are desired, then Integer programming method may
be employed.
Additivity:
The value of the objective function for the given value of decision variables and the total sum of resources used, must
be equal to the sum of the contributions (Profit or Cost) earned from each decision variable and sum of the resources
used by each decision variable respectively. The objective function is the direct sum of the individual contributions of
the different variables.
Linearity:
All relationships in the LP model (i.e. in both objective function and constraints) must be linear.
3.3 Nurse scheduling mathematical model
Decision Variables of the problem
Decision variables are the economic or physical quantities which can be controlled by the decision maker. The optimal
values can be found by manipulating these variables. In an optimization model for nurse scheduling, the number of
nurses to employ during a shift represents the decision variable.
Objective function
To minimize the total number of nurses needed to meet all shift requirements. We have
© IEOM Society International
Proceedings of the International Conference on Industrial & Mechanical Engineering and Operations Management
Dhaka, Bangladesh, December 26-27, 2020
Minimize Z = x 1 +x 2 +….+x n
Here, x 1 +x 2 +….+x n are the decision variables.
Constraints
Each shift must have at least the minimum number of nurses
x 1 +x 2 ≥ D 1
x 2 +x 3 ≥ D 2
……………….
x i +x i+1 ≥ D i
…………………
x n +x 1 ≥ D n
x 1 ,x 2 ,…,x n ≤ a 1 , a 2 ,…,a n
Non-negativity constraints:
x 1 ≥ 0, x 2 ≥0, x 3 ≥ 0, x 4 ≥ 0
Here, i = 1,2….,n
D 1 , D 2 ,…, D n = Total demands in the respective two slots
a 1 , a 2 ,…,a n = Available nurses per shift
4. Data Collection
To solve the problem of shortage of nurses, the paper proposes that nurses report at the hospital at the beginning of
each period and work for 12 consecutive hours instead of 8 hours. The minimal number of nurses to be employed is
determined so that there will be a sufficient number of nurses available for each period to meet all requirements.
Figure 1: Shift Type
Table 1: Daily requirements for nurses
Minimum number of nurses
Time slot (shift) Duty time
required
1 6:00 am-12:00 pm 25
2 12:00 pm-6:00 pm 38
3 6:00 pm-12:00 am 35
4 12:00 am-6:00 am 22
We need to develop a linear program for this problem that will determine the number of nurses that should be
scheduled to begin the 12-hours shifts at each of four times (6:00 am, 12:00 pm, 6:00 pm, and 12:00 am) in order to
minimize the total number of nurses required.
To solve this linear problem, we need four decision variables which are demonstrated here:
x 1 = the number of nurses who begin work in slot 1 and work shifts (6:00 am - 12:00 pm)
and (12:00 pm - 6:00 pm)
© IEOM Society International
Proceedings of the International Conference on Industrial & Mechanical Engineering and Operations Management
Dhaka, Bangladesh, December 26-27, 2020
x 2 = the number of nurses who begin work in slot 2 and work shifts (12:00 pm - 6:00 pm)
and (6:00 pm - 12:00 am)
x 3 = the number of nurses who begin work in slot 3 and work shifts (6:00 pm - 12:00 am)
and (12:00 am - 6:00 am)
x 4 = the number of nurses who begin work in slot 4 and work shifts (12:00 am - 6:00 am)
and (6:00 am - 12:00 pm)
Table 3: Available nurses willing to start in the respective shift
Shift Available nurses willing to start
Morning 10
Day 25
Evening 25
Night 12
5. Results and Discussion
The solution found by the linear programming algorithm uses the minimum number of 60 nurses to meet the schedule.
The optimal number of scheduled nurses for different time slots are given in the below figure.
25
20
15
23
10
15
10 12
5
0
Slot 1 Slot 2 Slot 3 Slot 4
No of Minimum Scheduled Nurses
Figure 2: Optimal number of scheduled nurses for different time slots
The maximum number of scheduled nurses is found to be in the day and evening shift. In a developing country like
Bangladesh, most of the nurses are female. They are not willing to start in the night or early morning shift concerning
about their safety. So, the number of nurses willing to start in the night shift and early morning shift were the lowest.
In our problem formulation, we took this concern and formulated the problem in such a way that the number of nurses
who start their working shift in these two slots were minimum. To fulfill the requirements during these slots, the nurses
from the previous shift are also scheduled in these shifts.
6. Conclusion
Optimizing the number of nurses in each shift to meet up with this seasonal peak of the required service in Covid-19
units has been a great concern in the domain of healthcare as there is less availability of nurses who are willing to
work in Covid-19 units at the stake of their lives. Thus, it has become progressively important to present an optimized
nurse schedule that can be implemented with careful decision support systems in a cost-effective manner while
satisfying customer demand as well as other requirements such as a flexible workplace. The aim of this paper is to
maximize the fairness of the schedule with respect to all the constraints. Nurse rostering is a complex scheduling
problem that affects hospital personnel on a daily basis. For the problem solved in this paper, the resulting nurse
schedule will efficiently utilize the time and effort to balance the workload more effectively and since the minimum
© IEOM Society International
Proceedings of the International Conference on Industrial & Mechanical Engineering and Operations Management
Dhaka, Bangladesh, December 26-27, 2020
number of nurses has been calculated, using this nurse rostering it is possible to meet the shortages of nurses present
at this moment.
Arising from this analysis of extant literature, it is possible to identify future research topics such as to take an
integrated approach that allows for flexible start times, variable shift lengths, break inclusion, overtime and on-call
service, shift spill-over from one day to the next, and various individual preferences and constraints in the nurse
scheduling. Further study can be conducted in more depth to find the motivational factors which encourage the hospital
management to design nurse schedules and how nurse scheduling may be used to capture the problems experienced.
References
Abdennadher, S., & Schlenker, H. (1999, July). Nurse scheduling using constraint logic programming.
In AAAI/IAAI (pp. 838-843).
Aickelin, U., & Dowsland, K. A. (2004). An indirect genetic algorithm for a nurse-scheduling problem. Computers
& operations research, 31(5), 761-778.
Berrada, I., Ferland, J. A., & Michelon, P. (1996). A multi-objective approach to nurse scheduling with both hard
and soft constraints. Socio-economic planning sciences, 30(3), 183-193.
Brusco, M. J., & Jacobs, L. W. (1995). Cost analysis of alternative formulations for personnel scheduling in
continuously operating organizations. European Journal of Operational Research, 86(2), 249-261.
Cheang, B., Li, H., Lim, A., & Rodrigues, B. (2003). Nurse rostering problems––a bibliographic survey. European
journal of operational research, 151(3), 447-460.
Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). Staff scheduling and rostering: A review of
applications, methods and models. European journal of operational research, 153(1), 3-27.
Guinet, A. (1995). Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria. Journal
of Intelligent Manufacturing, 6(2), 95-103.
Jaumard, B., Semet, F., & Vovor, T. (1998). A generalized linear programming model for nurse
scheduling. European journal of operational research, 107(1), 1-18.
Valouxis, C., & Housos, E. (2000). Hybrid optimization techniques for the workshift and rest assignment of nursing
personnel. Artificial Intelligence in Medicine, 20(2), 155-175.
Biographies
Tasnia Biswas is a novice researcher and final year undergraduate student in the Department of Industrial &
Production Engineering (IPE), BUET. Her research interest includes supply chain management, total quality
management and operations research.
Afifa Sumaya is a novice researcher and final year undergraduate student in the Department of Industrial &
Production Engineering (IPE), BUET. Her research interest includes operations research, reliability analysis, supply
chain management, machine learning and data science.
© IEOM Society International
