Goal programming. An approach to solving the physician scheduling problem

Bachelor Thesis, 2018
58 Pages, Grade: 1,0


Table of contents

1. Introduction

2. Literature Review on Personnel Scheduling Problems in the Health Care Sector
2.1 Classification by Solution Approach
2.2 Classification by Consideration of Individual Preferences
2.3 Further Classification Approaches

3. Analysis of the Goal Programming Model by Gharbi et al.
3.1 Model Description
3.1.1 Objective Function
3.1.2 Hard constraints
3.1.3 Soft Constraints
3.2 Integration of the Model into the Literature Scheme
3.3 Implementation with CPLEX
3.3.1 Data Generation
3.3.2 Computational Results
3.4 Model Evaluation
3.4.1 Scenario 1: Reduction of the Staff Size
3.4.2 Scenario 2: Allowing Slack
3.4.3 Comparison of the Proposed Scenarios
3.4.4 Summary and Discussion of the Findings

4. Conclusion and Recommendations for Further Research

5. References

Table of Figures

Figure 1: Correlation between IDOFF and OS (tot.) 27

List of Tables

Table 1: Notation of input data

Table 2: Notation of decision variables

Table 3: Demand distribution

Table 4: Attributes of the months the model was tested in

Table 5: Theoretical overstaffing

Table 6: Average computational results with original data

Table 7: Minimum and maximum criteria expressions of the original data set

Table 8: Comparison between manual and optimized schedule with varying data

Table 9: Correlation between model attributes for the original data set

Table 10: Average computational results with reduced staff size

Table 11: Correlation between model attributes for scenario 1

Table 12: Average computational results with integrated slack

Table 13: Correlation between model attributes for scenario 2

Table 14: Standard deviations of the runtime


Abbildung in dieser Leseprobe nicht enthalten


Planning physicians properly is a crucial task for a medical facility since physicians have an outstanding role in the staff due to their specialized education and the high responsibility for patients’ health. This leads to them having a lot of power when negotiating individual labor contracts, which results in favorable working conditions for the physicians. The medical facility, however, has to deal with these conditions. Since e.g. an Emergency Department (ED) provides 24 hours of continuous service throughout each day, it is highly dependent on their staff being sufficiently satisfied. Therefore, it has to comply with physicians’ requests. Another reason for the importance of physician scheduling is that personnel costs are the dominant budget component in the health care industry (Brunner, 2010, p. 1). Assigning too many physicians to a shift causes overstaffing, which leads to undesirable utilization of the medical staff and unnecessary high personnel costs (Erhard, Schoenfelder, Fügener, & Brunner, 2018, p. 1). Understaffing on the contrary could lead to a decreased service quality and longer waiting times for the patients as well as to dissatisfied staff and in return an even higher workload (Erhard et al., 2018, p. 1). This higher workload for medical staff can lead to a decrease in a medical facility’s reputation since it is believed by the public that too many working hours and sleep deprivation reduce the quality of patient treatment (Ozkarahan, 1994, p. 252).

The consistently growing and highly volatile demand for medical services stresses the relevance of physician scheduling. A state of the art in physician scheduling is provided by Erhard et al. (2018) who discovered physician and resident scheduling receiving increasing attention in recent years. Simultaneously, research lacks behind at the creation of schedules that include break assignment and/or consider a stochastic demand pattern. This concludes in a deficit in research regarding the assignment of physicians on a short-term basis as well as the coverage of unanticipated peaks in demand for medical services (Erhard et al., 2018, p. 13).

One approach to solving the physician scheduling problem (PSP) at an ED in Saudi Arabia to optimality, more precisely at the King Khalid University Hospital (KKUH), is provided by Gharbi, Louly, and Azaiez (2017). Their model optimizes the monthly rosters at the mentioned facility considering three aspects: isolated days on, isolated days off, and night blocks (which means trying to assign all night shifts in only one block per physician). I will evaluate the effectivity of their approach in order to get insights on the extent to which it can contribute to research in the field of physician scheduling. The model is to be examined considering performance in general, stability, and overstaffing. Furthermore, relations between model attributes are analyzed and the model is evaluated using an original data set as well as two scenarios with a reduced staff size. Drawing a conclusion, the model performs well considering the goals stated in the objective function as well as stability and runtime but reveals a deficit considering the appropriate staff size for the medical facility.

In order to evaluate the effectivity of the mentioned model, this thesis is built up as follows: Firstly, an insight on important approaches to personnel scheduling problems in the health care sector in literature is provided in section 2 in order to get a sense of the variety of existing approaches on physician scheduling. After introducing the model, it will be classified in the existing literature in section 3. The implementation using a software and the computational results of the model executions are provided in section 3.3. After implementing the model with the original staff size, two scenarios and their computational results are introduced in sections 3.4.1 and 3.4.2 in order to get more insights into the model’s performance. In a first scenario, the staff size is reduced. In the second scenario, additional slack constraints and variables are added to the model. The comparison of their results follows. In section 3.4.4, the findings are summarized, interpreted, and discussed. The evaluation is concluded in section 4 in order to give recommendations for further research.

2. Literature Reviewon Personnel Scheduling Problems in the Health Care Sector

PSPs are specifications of personnel scheduling problems, which again are specifications of general scheduling problems. In the following, I will focus on personnel scheduling in medical facilities. These problems can be categorized into three subcategories according to the kind of personnel addressed by the problem. Firstly, there are nurse scheduling problems (NSPs), which have received most attention in the beginning of research on personnel scheduling in medical facilities (Ernst, Jiang, Krishnamoorthy, & Sier, 2004, p. 9). Resident scheduling problems (RSPs) focus on scheduling students in medical training. The problem, which now receives more and more attention by the public, is the physician scheduling problem (PSP) (Güler, İdin, & Yilmaz Güler, 2013, p. 2118). In the following, I will mainly concentrate on PSPs, but will also mention concepts for RSPs. An approach to classify PSPs further is to consider the strategical level of the scheduling problem (Erhard et al., 2018, p. 3). According to Erhard et al. (2018), there are three main categories in the field of physician scheduling: “Staffing problems focus on the strategic decision of determining the required size and composition of a workforce. These planning problems typically involve a long term (e.g. annual) planning horizon” (p. 3). Rostering, however, focuses on generating (repeating) shift rosters, where the planning horizon typically reaches from weeks to a few months. Modifying already existing working schedules on a short-term basis is termed re-planning. It handles problems that occur when e.g. a physician is not available on a very short notice due to illness (Erhard et al., 2018, p. 3). For more detailed information on re-planning and a real-life case study, I refer to Gross, Fügener, and Brunner (2018).

The model by Gharbi et al. (2017) to be analyzed covers a planning horizon of one month and focuses on the tactical assignment of shifts to physicians over this fixed time horizon. That is the reason why this model falls under the category of rostering . This literature review will therefore concentrate on rostering problems subsequently.

2.1 Classification by Solution Approach

In the following, I will describe the relevant solution approaches to PSPs and provide details on the modelling techniques used. All the mentioned concepts are models, which means they are an abstracted form of reality and the findings in these models can then be implemented as actual schedules in real life.

Firstly, there are the exact solution approaches, which focus on giving optimal solutions for rostering problems, regardless of the time the execution of the model requires. An example for an exact solution procedure is provided by Gunawan and Lau (2013), who created weekly rosters for a surgery department of a local government hospital. They used a bi-objective approach, which means the goal was to simultaneously maximize physicians’ preferences and satisfy duty requirements. Bard, Shu, and Leykum (2013) generated a model for the medical interns and residents at the Internal Medicine (IM) based on real life data provided by the University of Texas Health Science Center at San Antonio (UTHSCSA). In the objective function, twelve goals are incorporated and weighted by their relative importance and the violation of these goals are penalized by aiming at minimizing these violations. The model by Shamia, Aboushaqrah, and Bayoumy (2015) focuses on scheduling physicians’ on-call-duties for two departments (hematology and oncology) and two different physician groups (specialists and consultants). The goal is to create bimonthly schedules with an optimal “distribution of number of weekend and weekday on-call shift among fellows in a month taking into consideration all other constraints” (Shamia et al., 2015, p. 4). One of the first exact modeling approaches for residents creates weekly schedules while simultaneously considering eight constraints. Their deviations from predefined target levels are minimized in the target function (Ozkarahan, 1994). The exact models by Elomri, Elthlatiny, and Mohamed (2015), Güler et al. (2013), and Topaloglu (2006) have in common that they consider multiple objectives simultaneously as well as focusing on medical students’ duties being scheduled over a fixed time horizon. Furthermore, the objective functions of all three models contain deviations from soft constraints being violated. Differences can be identified when it comes to the planning horizon: The former one creates bimonthly schedules, whereas the latter two generate monthly rosters (Elomri et al., 2015; Güler et al., 2013; Topaloglu, 2006). Exact solution approaches can be classified further when regarding the modelling method. Methods in this category include among others, but not limited to Goal Programming (GP), Integer Programming (IP), Linear Programming (LP), or Mixed-Integer Programming (MIP). However, this classification step would exceed the scope, therefore it will not be part of this particular thesis.

Secondly, there are also approaches, which focus more on getting a feasible solution in less time, even if there is still a possibility of a better, an optimal solution. These solution approaches are also called heuristics. Silva, Burke, and Petrovic (2004, pp. 116–117) provide information on multi-objective metaheuristics, which describe a theoretical concept for generating heuristics for personnel scheduling problems. More specific approaches are the heuristics used by Carter and Lapierre (2001) and van Huele and Vanhoucke (2015). The former created a generic method after analyzing six different medical facilities in Canada that generates rosters with a three-month planning horizon. The method used is based on a tabu search algorithm (Carter & Lapierre, 2001). The other example is based on three decomposition heuristics and the goal is to generate physician rosters with a maximum of physicians’ preferences satisfied (van Huele & Vanhoucke, 2015).

Models which combine heuristics and exact solution methods exist as well. Beaulieu, Ferland, Gendron, and Michelon (2000) constructed monthly schedules for an Emergency Room (ER) with approximately 20 physicians in a hospital in the Montréal region using an iterative approach with three steps, which are repeated until the method cannot create any feasible schedule. These steps are: “(1) identify the rules that are violated in the current schedule; (2) add the corresponding constraints to the model; (3) use the branch-and-bound method to identify a new schedule, which […] improves over the previous one” (Beaulieu et al., 2000, p. 198). A slightly different approach is the one by Brunner (2010), who plans physicians over a fixed time horizon but with an implicit construction of shifts. This means not having predefined starting times and lengths of physicians’ shifts but working periods that can start at an arbitrary time each day. This is done by firstly decomposing the problem by week and then applying a branch-and-price algorithm to generate optimal, cost-effective schedules. Stolletz and Brunner (2012), who created a fortnightly schedule for a German hospital, give another example for this idea. In the first step, termed preprocessing, all possible shift types are predetermined according to hospital regulations. Then, the rosters are created using an LP model. This concept might perform better when it comes to optimal utilization of medical staff and meeting demand more flexibly, although physicians’ satisfaction with the proposed schedules might decrease by these flexible starting times of their shifts.

Lastly, simulations are another approach to PSPs. For this category, so far only one paper covers a rostering problem (Erhard et al., 2018). In the conference paper, a simulation model is provided that creates weekly schedules for the physicians of the ED at the University of Virginia Medical Center using a computer simulation software (Rossetti, Trzcinski, & Syverud, 1999). This was done by “considering patient load as a function of hour of the day and day of the week” (Rossetti et al., 1999, p. 1532).

In conclusion, it can be seen that most of the research is done using an exact solution approach (Erhard et al., 2018). A reason for that could be the increasing computing power nowadays, since this leads to model instances taking less time to find the optimal schedule taking into account all rules and constraints. Therefore, even the models considering a very large number of variables and constraints can be solved to optimality in a relatively short duration. However, the fact that so many different approaches to the same problem exist stresses the importance for further research in this area since not one approach can cover the variety of medical facilities with its individual preferences and regulations.

2.2 Classification by Consideration of Individual Preferences

My second classification characteristic is to examine whether the model considers individual preferences of the physicians or not. This cannot be answered easily because the consideration of individual preferences can happen by multiple model attributes. In this section I will focus on the models which are classified as exact solution approaches in section 2.1.

Güler et al. (2013) consider individual preferences by including “social groups” into their model. Speaking of these groups, they state that “their request is to be assigned to the same shift […] so that they can share their spare time (if any) during the shift” (Güler et al., 2013, p. 2121). Another concept is given by Ozkarahan with “special requests” by the residents for shifts “carried over from the previous scheduling period” (1994, p. 259). The model tackling a PSP presented by Gunawan and Lau (2013) allows physicians to request days or individual shifts of a day off. These requests have to be met compulsory, therefore this model considers individual preferences highly and is an addition to only allowing vacation requests for whole days off. Topaloglu (2006) as well as Elomri et al. (2015) respect residents’ preferences by assigning weekends off, although their models do not consider the individual preferences of each physician. Bard et al. (2013) respected the staff’s preferences by assigning shifts on the same days of the week for each resident or intern. However, due to the size of the model, no personal preferences of single individuals could be considered. A similar approach is to generate “individual schedules with few changes over time”, which are preferred over schedules with a high volatility of starting times (Shamia et al., 2015, p. 3).

In summary, a variety of ideas and concepts can be observed when researchers tackle the problem of staff’s individual preferences. Often, these preferences exceed the scope of a model or the medical facility ignores these preferences in order to increase fairness between physicians or residents.

2.3 Further Classification Approaches

Apart from the already presented classification, existing literature on PSPs and RSPs might be classified considering numerous model attributes. For instance, one idea could be to classify models regarding the financial nature of the objective: There are models, such as the one constructed by Brunner (2010), where the major goal is to minimize personnel costs for the medical facility considering a variety of constraints. A different approach would be not to focus on costs but more on creating a feasible schedule, which performs best considering factors such as fairness between physicians, or patient care. Furthermore, literature on rostering problems could be divided regarding cyclicality, meaning the schedules being generated for one fixed planning horizon and those schedules being repeated over and over. Acyclic rosters are created for each planning horizon individually. Besides that, existing models can be classified regarding consideration of previous schedules, e.g. a physician is compensated with fewer/better shifts in one planning horizon when they were assigned to more than the requested number of shifts in the previous planning period. For further differentiation approaches as well as a thorough analysis of existing literature on physician scheduling, I refer to Erhard et al. (2018). A different classification has been done by Ernst et al. (2004), who clustered existing literature on staff scheduling in general into six distinct modules. These modules are demand modelling, days off modelling, shift scheduling, line of work construction, task assignment, and staff assignment.

In conclusion, the variety of approaches to rostering problems stresses the unclarity of health care research society on the major goal of a schedule as well as on the method how to achieve this goal. A multitude of different approaches are provided in literature and not two models consider exactly the same constraints and assign the same relative significance of these constraints. Since each medical facility is different, management is responsible for creating optimal schedules for their individual staff considering numerous preferences and requests as well as improving patient care. The provided approaches in literature can be regarded as a base for executives so that they can expand or customize existing models in order to fit perfectly to the medical facility’s individual needs. Following, the model by Gharbi et al. (2017) is introduced and described. Based on that, it will be categorized in literature considering the mentioned classification approaches.

3. Analysis of the Goal Programming Model by Gharbi et al.

The three researchers Anis Gharbi, Mohamed Aly Louly (both King Saud University, Saudi Arabia), and Naceur Azaiez (Université de Tunis, Tunisia) constructed the model at hand for the ED at KKUH in Riyadh, an 850-bed facility. Their approach was presented at the 4th International Conference on Control, Decision and Information Technologies (CoDIT) in Barcelona, Spain, in April 2017. The ED offers 24 hours of continuous service and it is assumed that all physicians can provide all services required for patient treatment (Gharbi et al., 2017, p. 922). According to the authors, “the schedule should also be fair enough to everyone and not disruptive to physicians’ health, families or social lives” (Gharbi et al., 2017, p. 922). The model was created since the current monthly schedules had been produced manually by one physician with an Excel sheet, who spends “one entire week each month to build the schedule” (Gharbi et al., 2017, p. 923). Hence, the model was created in order to create monthly schedules that comply to all hospital regulations and perform better considering physicians’ preferences in less time.

3.1 Model Description

In the statement of the model at hand, I will make use of the notation as seen in tables 1 and 2. This notation is also used by the authors of the original model. For further detail I refer to the conference paper (Gharbi et al., 2017, pp. 923–924).

Abbildung in dieser Leseprobe nicht enthalten

Table 1: Notation of input data (own figure)

The staff of the ED at KKUH consists of 23 physicians, therefore I is set to 23. Furthermore, the staff is divided into two classes: physicians of type 1 work exactly 12 shifts (96 hours) per month and physicians of type 2 work 13 to 15 shifts (104 to 120 hours) per month. This means the range for Dutyi is between 12 and 15 for each physician. Furthermore, it is specified that the monthly number of afternoon or night shifts for each physician might not exceed five duties (Gharbi et al., 2017, p. 923). Therefore, the sum of Duty_Ai and Duty_Ni equals 5 for each physician i. The parameters in table 1 can be considered static, since they are defined prior to the generation of the schedule.

Abbildung in dieser Leseprobe nicht enthalten

Table 2: Notation of decision variables (own figure)

Table 2 provides information on the required decision variables. These are the variables the model assigns exact values to while it generates an optimal solution. Note that the number of decision variables changes when increasing or decreasing the number of days per planning horizon as well as changing the staff size. All decision variables are matrices of the size I x D. The binary decision variables fulfill the function of creating matrices containing only the values 0 and 1, which represent the attributes stated in table 2. These values are interpreted as stated in table 2. The continuous decision variables could also be called deviation variables since these are denoted as being a deviation from predefined target levels. Decision variables can be called dynamic since their values are assigned dynamically within the optimization process and are not predefined in contrast to parameters.

The demand for physicians is assumed to be deterministic according to Gharbi et al. (2017, p. 923) and is summarized in table 3. The assumption of a non-stochastic demand distribution, however, is crude since demand peaks are not considered in the model. In order to receive more detailed information on patient arrival times, this particular ED has to be examined. After this examination, the next step is to evaluate patient arrival times and stay lengths and find indications on the underlying statistical distribution.1

Abbildung in dieser Leseprobe nicht enthalten

Table 3: Demand distribution (own figure)

Following, the target function is introduced, afterwards hard constraints are stated and explained, and lastly soft constraints are provided. The model assigns values to the decision variables as seen in table 2 according to the objective function, which is subject to hard and soft constraints.

3.1.1 Objective Function

After introducing the required notation for the model, I will now concentrate on the model itself. Following, the target function as created by Gharbi et al. (2017, p. 924) can be seen:

Abbildung in dieser Leseprobe nicht enthalten

The objective function aims at minimizing three goals at the same time. Firstly, it focuses on the blocks of night shifts per physician. In more detail, the goal is to assign only one block of night shifts per month per physician. In other words, there should be no morning or afternoon shifts between two night shifts throughout the whole planning horizon (Gharbi et al., 2017, p. 924). This part of the target function will be discussed in more detail in the evaluation. The second part of the target function minimizes the sum of positive deviations of the isolated days on constraints and the third part minimizes the sum of positive deviations of the isolated days off constraints. The first part of the target function leads to the solution value of the model not being interpretable since days and physicians are multiplied with each other. According to the authors, “all targets to be met are considered as of comparable levels of importance. Hence, the importance weights are all set to 1” (Gharbi et al., 2017, p. 924). This feature of the model will be discussed later in the evaluation of the model.

3.1.2 Hard constraints

The objective function is subject to the following compulsory constraints. These constraints are also called hard because they cannot be violated under any circumstances. Constraints (2) to (20) make use of the notation as stated in tables 1 and 2 and were introduced in the conference paper by Gharbi et al. (2017, p. 924).

Constraints (2) to (4) guarantee assigning exactly the required staff for each shift type of each day:

Abbildung in dieser Leseprobe nicht enthalten

Constraint (5) guarantees full resource utilization for each physician, meaning each physician works exactly the number of duties as stated prior to the creation of the roster:

Abbildung in dieser Leseprobe nicht enthalten

Constraints (6) and (7) state that the maximum number of afternoon shifts might not be exceeded but at least one shift less than this upper bound must be worked by each physician:

Abbildung in dieser Leseprobe nicht enthalten

Constraints (8) and (9) state that the maximum number of night shifts might not be exceeded but at least one shift less than this upper bound must be worked by each physician:

Abbildung in dieser Leseprobe nicht enthalten

Constraints (10) to (12) guarantee not more than one shift being assigned to each physician for a period of 24 hours throughout the planning horizon:

Abbildung in dieser Leseprobe nicht enthalten

Constraints (13) and (14) have the function that each physician has at least two weekends off a month, whereas a weekend in this case consists of Friday and Saturday:

Abbildung in dieser Leseprobe nicht enthalten

Constraint (15) states that no more than three consecutive days on are assigned to each physician during the planning period:

Abbildung in dieser Leseprobe nicht enthalten

Constraints (16) and (17) denote that not two different shift types in consecutive days to each physician are assigned. This means no abrupt changes between shift types are allowed:

Abbildung in dieser Leseprobe nicht enthalten

Constraint (18) considers requested vacation and states that each physician must have a day off when they asked for it beforehand:

Abbildung in dieser Leseprobe nicht enthalten

The mentioned hard constraints are general or hospital-related regulations and therefore have to be met by the GP model in contrast to soft constraints, which now are to be explained in further detail.

3.1.3 Soft Constraints

Since the following constraints are not compulsory, they are called soft constraints. The positive deviations , of the targeted goals are in this model penalized in the objective function, which makes these deviations undesirable. This type of constraints is characteristic for GP models.

Constraint (19) focuses on isolated days on being assigned. The model should not assign more than two isolated days on to each physician throughout the planning horizon:

Abbildung in dieser Leseprobe nicht enthalten

Constraint (20) states that the model should not assign more than two isolated days off to each physician throughout the planning horizon:

Abbildung in dieser Leseprobe nicht enthalten

Note that only the positive deviations from the mentioned soft constraints are part of the target function (1). This indicates that less than two isolated days on respectively off are rated indifferently by KKUH management.

3.2 Integration of the Model into the Literature Scheme

After describing the model briefly, I now will classify it according to the aspects with which solution approach the model was constructed and whether it considers individual preferences.

Considering the first aspect, the model can be classified into the exact solution approaches. It proposes a GP solution for a PSP and its features are similar to the models by Güler et al. (2013) and Topaloglu (2006), although these models were built for RSPs. Since the present model makes no use of a heuristic algorithm in order to decrease runtime but aims at finding a globally optimal solution exactly for the introduced PSP at KKUH, it is not to be categorized as a heuristic approach. It cannot be regarded as a simulation, either. Since no computer simulation was created, but rather a complex situation in a hospital is described through mathematical modelling, the attempt by Gharbi et al. (2017) is considered as an exact solution approach.


1 Typical statistical demand distributions over a day are the Poisson-distribution or the Gauss-distribution.

Excerpt out of 58 pages


Goal programming. An approach to solving the physician scheduling problem
University of Augsburg
Catalog Number
ISBN (eBook)
ISBN (Book)
physician scheduling, goal programming, zielprogrammierung, ärzteplanung, emergency department, personnel scheduling, personalplanung
Quote paper
Léon Gerardo Kreis (Author), 2018, Goal programming. An approach to solving the physician scheduling problem, Munich, GRIN Verlag, https://www.grin.com/document/453352


  • No comments yet.
Read the ebook
Title: Goal programming. An approach to solving the physician scheduling problem

Upload papers

Your term paper / thesis:

- Publication as eBook and book
- High royalties for the sales
- Completely free - with ISBN
- It only takes five minutes
- Every paper finds readers

Publish now - it's free