# Personnel Scheduling Problem under Hierarchical Management Based on Intelligent Algorithm

Authors: Li Huang; Chunming Ye; Jie Gao; Po-Chou Shih; Franley Mngumi; Xun Mei
Journal: Complexity
 (2021)

---

## Abstract

This paper studies a special scheduling problem under hierarchical management in nurse staff. This is a more complex rostering problem than traditional nurse scheduling. The first is that the rostering requirements of charge nurses and general nurses are different under hierarchical management. The second is that nurses are preferable for relative fair rather than absolute fair under hierarchical management. The model aims at allocating the required workload to meet the operational requirements, weekend rostering preferences, and relative fairness preferences. Two hybrid heuristic algorithms based on multiobjective grey wolf optimizer (MOGWO) and three corresponding single heuristic algorithms are employed to solve this problem. The experimental results based on real cases from the Third People’s Hospital, Panzhihua, China, show that MOGWO does not as good as it does on other engineering optimization. However, the hybrid algorithms based on MOGWO are better than corresponding single algorithms on generational distance (GD) and spacing (SP) of Pareto solutions. Furthermore, for relative fair rostering objective, NSGAII-MOGWO has more power to find the optimal solution in the dimension of relative fairness.


---

## Body

## 1. Introduction

The shortage of nurses has become a serious problem that most hospitals have to face in personnel scheduling. In order to improve the utilization efficiency of nursing personnel resources, it is necessary to carry out management innovation and put forward a highly prepared roster so as to bring more contented and thus more effective nursing services [1]. A wide variety of research studies about nurse rostering problem (NRP) has been conducted. Burke et al. [1] and Van den Bergh et al. [2] reviewed 144 and 293 influential articles, respectively, from 1960s to 2012, mainly concentrating on nurse rostering problem descriptions, modeling, and solution approaches. However, the complexities in legal regulations, hospital policies and requirements, nurse requests, and preferences bring various difficulties to modeling. A good model structure can help us build models more completely and faster. De Causmaecker and Vanden Berghe [3] and Smet et al. [4] developed a structured model for nurse rostering problem, based on the notation of α|β|γ, which made model more general and rich. However, the structure of the model is not easy to grasp for hospital administrators due to the lack of simple and clear induction of some trivial elements. In order to make the induction of trivial elements more simple and clear, we have reconstructed the model structure of NRP, including premodeling condition settings, objectives, and constraints, which is close resemblance to the above structure of α|β|γ, as shown in Table 1.Table 1
Construction of model for nurse rostering problem.
ComponentsElementsDetail descriptionsα: premodeling condition settingsS: shift characterTwo-shift/three-shift/four-shift/multiple shiftC: cycle characterCycle schedule/uncycled schedule/semicyclic schedule/schedule horizonD: demand characterCertain demand/uncertain demandN: nurse characterNumbers/only full-time/full-time and part-timeSkill level/roles of job/hierarchical managementβ: objectivesSO: single-objectiveHospital objective/nurses’ preferenceMO: multiobjectiveγ: constraintsH: hard constraintsLaws and regulations/hospital regulations/ergonomics/operational requirements/nurses’ preferencesS: soft constraintsPremodeling condition setting (α) is described as external framework or boundary description of modeling, which can be further subdivided into shift character (S), cycle character (C), demand character (D), and nurse character (N). Objective (β) is expressed as the pursuit of desired results of the model, which can be further subdivided into single-objective (SO) and multiobjective (MO). Constraint (γ) is presented as internal framework or search space boundary description of modeling, which can be further subdivided into hard constraints (H) and soft constraints (S). Hard constraints decide the feasibility of the roster, while soft constraints determine the quality of the feasible roster. An ideal objective is to find a feasible roster with good enough quality.Management innovation of “hierarchical management” is another effective way to improve the utilization efficiency of nursing human resources. The hierarchical management of nurses is to classify nurses into different levels based on comprehensive consideration of their educational background, professional ranks, skills, and length of employment. The most common way of nurse hierarchical management is to divide nurses into three levels, namely, head nurse, charge nurse, and general nurse. The head nurse is responsible for the running of the nursing work of the whole department. The charge nurse is responsible for coordinating the nursing work in the responsible zone. The general nurse is responsible for the nursing treatment of some patients in the responsible zone. Different levels of nursing personal have both independence and cooperation. Because the hierarchical management clearly defines the position responsibilities of nurses at all levels, it ensures the effectiveness of nursing service and makes nursing more responsible and careful. Therefore, hierarchical management contributes to solving the weakness in nonadministrative nursing quality management and becomes one of the trends of nursing professional development.Hierarchical management ensures the quality of hospital nursing but puts forward higher requirements for nurse scheduling, especially in the fairness of nurse rostering. Due to the different job responsibilities and requirements of nurses at different levels, it is impossible to arrange the same number of shifts for all nurses, but it is possible to assign the same number of shifts for the nurses at the same hierarchy. Therefore, for nurse rostering with hierarchical management, we no longer pursue the absolute fairness for all nurses but pursue the relative fairness of nurse rostering among different levels and absolute fairness of nurse rostering within the hierarchy.This paper studied a special kind of multilevel nurse rostering problem (MLNRP). Nurses are divided into three levels: head nurse, charge nurse, and general nurse. At the same time, according to their skill qualifications, these nurses are classified into three categories: A, B, and C, where nurse C is the lowest one. In MLNRP, there are two characteristics different from general NRP. One is the rostering requirements of nurses at different levels. As the routine affairs are mainly dealt with during the daytime, the head nurse is assigned for day shift from Monday to Friday, while at least one charge nurse is assigned for day shift on Saturday and Sunday. The other is fairness preferences, which is to pursue absolute fairness in the same level and accept relative fairness among different levels. Literature research on fair rostering mainly focuses on the following aspects: (1) fair workload allocation [5], (2) fair shifts assignment [6–8], (3) fair distribution of contractual violations [9], and (4) fair allocation of special time, such as vacations [10], weekends, and nights [11]. The research on fair rostering has acquired rich achievements but mainly focused on the absolute fairness for all nurses. It is difficult to achieve absolute fairness for multilevel nurses because of the differences in work requirements. Therefore, the relatively fair rostering of multilevel nurses is an important supplement to the research of fair rostering.In this paper, MLNRP is a particular type of multilevel nurse rostering problem with special requirements and preferences. Algorithms are powerful tools to search for high-quality solutions. The exact algorithms employed for nurse rostering problem include integer programming algorithm [12], dynamic programming algorithm [13], branch and bound method [14], and column generation method [15]. However, when the problem becomes complex and highly constrained, it may consume numerous computational time to search for an optimal solution with an exact algorithm. Heuristic algorithm, used to search for a satisfied solution within an acceptable computational cost, comes into full usage in such a situation. Metaheuristic algorithm is a general heuristic approach of exploring solutions in search spaces between intensiﬁcation and diversiﬁcation [13]. The intensiﬁed search-based algorithms for nurse rostering problem include tabu search (TS) [16] and variable neighbourhood search (VNS) [17]. The diversiﬁed search-based algorithms for nurse rostering problem include genetic algorithm (GA) [18], particle swarm optimization (PSO) [7], ant colony optimization (ACO) [19], artificial bee colony (ABC) [20], and harmony search algorithm (HSA) [21]. Compared with single metaheuristic, hybrid algorithms such as SA-GA [22] and SA-VNS [23] have shown more efficient and effective in solving the nurse rostering problem with high constrained search space.Just as the no free lunch (NFL) theorem [24], none of these heuristic algorithms have been proven best for solving all optimization problems. The NFL promotes and improves innovation of the algorithm continuously. Mirjalili et al. [25] proposed a multiobjective grey wolf optimizer (MOGWO) and proved superiority in convergence behaviour and the coverage of the obtained Pareto optimal solutions. MOGWO shows superior performance in solving many engineering optimization problems. However, for some complex optimization tasks, it may face the problem of getting trapped at local optima and premature convergence. A series of improved algorithms based on GWO operator have been proposed to enhance its exploration performance. Ibrahim et al. [26] proposed an improved version of the grey wolf optimizer through using the chaotic logistic map, the opposition-based learning (OBL), the differential evolution(DE), and the disruption operator (DO) to improve the exploration and the exploitation ability of the GWO algorithm. Gupta and Deep [27] proposed a modified algorithm RW-GWO based on random walk for providing a better leadership to search a prey. Gupta and Deep [28] presented a novel algorithm OCS-GWO by introducing the opposition-based learning to approximate the closer search candidate solution to the global optima and chaotic local search for the exploitation of the search regions efficiently. Gupta and Deep [29] introduced an improved leadership-based GWO called GLF-GWO. In GLF-GWO, the leaders are updated through Levy-flight search mechanism and the promising areas found in the search space are avoided to be deviated by greedy strategy. Bouzary and Chen [30] proposed a new hybrid approach based on the GWO algorithm and evolutionary operators of the genetic algorithm for the solution of optimal service composition and optimal selection in cloud manufacturing.However, to the best of our knowledge, very few attempts have been made in MOGWO for nurse rostering problem. Based on the advantage of hybrid methods proposed in the literature [9], we proposed two hybrid algorithms based on MOGWO for solving this problem of MLNRP and compared their performance with that of their corresponding single metaheuristic algorithm.There are three main contributions of our research. The first is the model of MLNRP, which fully expresses the features of multilevel in nurse rostering problem. The second is the relative fairness of nurse rostering objectives. Not all nurses are assigned the same numbers of shifts, but only the nurses at the same hierarchy are assigned the same numbers of shifts. The third is hybrid algorithms based on MOGWO, outperforming the corresponding single metaheuristics on the generational distance (GD) and spacing (SP) of Pareto solutions. Furthermore, the improved hybrid algorithm NSGAII-MOGWO is superior to the other four algorithms in many aspects and can easily find high-quality solutions in relatively fair rostering objective.The remainder of the paper is organized as follows. Section2 gives the problem description and mathematical model of the MLNRP. Section 3 elaborates hybrid algorithm based on MOGWO. Experimental results and analysis are laid out in Section 4. Finally, Section 5 presents conclusions and directions for future work.


## 2. Problem Description and Model

### 2.1. Premodeling Condition Settings

According to the premodeling structure proposed in this paper, we should grasp the following information: shift character, cycle character, demand character, and nurse character. Take the Geriatric Ward of the Third People's Hospital, Panzhihua, China, as an example. In the Geriatric Ward, elderly patients with chronic diseases who lose self-awareness or mobility will accept medical care here and nurses will provide continuous nursing services. There are three working shifts: day shift (D: 08:00–16:00), evening shift (E: 16:00–24:00), and night shift (N: 00:00–08:00). Each shift covers eight hours. Schedule horizon is four weeks. The number of nurses in each shift is determined. The number of nurses required for shift D is five and that for shift E and N is, respectively, two, from Monday to Sunday. There are thirteen full-time nurses, including one head nurse, two charge nurses, and ten general nurses. They belong to the first, second, and third levels of hierarchical management, respectively. The skill level of head nurse and one charge nurse is A, that of one charge nurse and five general nurses is B, and that of the other five general nurses is C. The abstract of premodeling information is shown in Table2. Detailed information on nurses and demands is shown in Table 3.Table 2
Premodeling condition settings in MLNRP.
ComponentsElementsDetail descriptionsMLNRP∗α: premodeling condition settingsT: shift characterThree-shift✓S: schedule characterCycled schedule✓Schedule horizon4-weekD: demand characterCertain demand✓N: nurse characterOnly full-time✓Hierarchical management3Skill levelA-B-CNumbers13Table 3
Descriptive statistics for nurses and demands in studied local hospital.
Nurse informationDemand of each shiftTitleNumbersHierarchical managementSkill level distribution (A-B-C)Monday–Sunday (D-E-N)Head nurse11st1-0-05-2-2Charge nurse22nd1-1-0General nurse103rd0-5-5


### 2.2. Decision Objective

Objectives provide an optimization direction for nurse rostering, and the satisfaction of objectives reflects the quality of the rosters. When there is a certain conflict between objectives, we often adopt multiobjective optimization.According to the survey, the nurse rostering objectives of the studied hospital are mainly reflected in three aspects: (1) minimizing violations of soft constraints; (2) minimizing the fairness bias of nurse rostering at each hierarchy; and (3) maximizing the quality of weekend rostering. Objectives come from requirements and appeals of hospital managers and nurses for rosters. On the one hand, hospital managers consider nonmandatory management rules as soft constraints and hope to satisfy them as much as possible. On the other hand, the nurses at different hierarchies expect to take fairness separately in rosters and take day-offs as much as possible on weekends. The preference of weekend rostering is ranked from high to low as follows: (1) two days off on weekend; (2) two consecutive days off, one of which is on weekend; (3) single day off on weekend; and (4) no weekends off. A three-objective programming is considered in MLNRP.


### 2.3. Constraints

A feasible and reasonable nurse roster is subject to two types of constraints: hard and soft. Hard constraints are used to determine or judge the feasibility of solutions, while soft constraints are used for improving or measuring the quality of the feasible solutions. The nurse rostering problem considered in this research includes four hard constraints (i.e., H1–H4 in Table4) and eight soft constraints (i.e., S1–S8 in Table 4).Table 4
Description of hard and soft constraints.
Hard constraintsH1No nurse can work more than one shift per dayH2Shift N cannot be assigned immediately after shift E because the end time of shift E is connected with the start time of shift NH3A minimum number of nurses must be guaranteed for each working shift to ensure proper service quality of the hospitalH4From Monday to Sunday, at least one head nurse or charge nurse is required for shift D. Because head nurse is assigned a fixed roster of shift D from Monday to Friday; this constraint translates into at least one charge nurse assigned to shift D on weekends.Soft constraintsS1Each nurse can be assigned 1 day off at least in seven consecutive daysS2Each nurse can be assigned 4 night shifts at most in seven consecutive daysS3Each nurse can be assigned 11 working days at most in 2 weeksS4Each nurse can be assigned 8 days off at least during the rostering period (28 days)S5Each nurse can be assigned 3 consecutive days off at most in the rosterS6Each nurse can be assigned 3 consecutive night shifts at most in the rosterS7The sum of levels A and B nurses should be more than or equal to that of level C nurse in each shift on every day to ensure proper service quality of the hospitalS8One day off should be arranged after a pair of shift E or N, such as E-E, N-N, or N-E


### 2.4. Mathematical Model

Based on the above descriptions, the model can be formulated as a 0-1 integer programming model. Note that since head nurses have been assigned to regular shifts, the rostering of head nurses is no longer considered in modeling.


#### 2.4.1. Notations of the Model

The related notations of the model are shown in Table5.Table 5
Notations of the model.
NotationsDefinitionNNumber of nurses available for arrangement,n = 1, …, NN1Number of charge nurses available for arrangement,n = 1, …, N1TNumber of days for the rostering horizon (T = 28), t = 1, …, TKTypes of shift (K = 4), k = 1, 2, 3, 4, represents day shift, evening shift, night shift, and rest shift, respectivelyINumber of soft constraints,i = 1, …, IFManagement level of nurses (F = 2), f = 1, represents charge nurse at 2nd hierarchy; f = 2, represents general nurse at 3rd hierarchySiViolation times of soft constrainti, i = 1, …, ICjNumber of typej weekend rostering, j = 1, 2, 3, 4. (1) j = 1, which means two-day weekends off; (2) j = 2, which means two consecutive days off and one of them is on the weekend; (3) j = 3, which means single day off on weekends; (4) j = 4, which means no weekends offwWeight value,w1−w8 represents penalty value for violation of soft constraints i; wd,we,wn,wr represents the preferences of shift K in nurses’ minds; w31,w32,w33,w34 represents preference for type j weekend rosteringICNumber of nurses with skill C qualificationRdayNumber of nurse requirement for day shift from Monday to SundayReveningNumber of nurse requirement for evening shift from Monday to SundayRnightNumber of nurse requirement for night shift from Monday to SundayGlimitUpper limit on number of working shifts in two weeks (Glimit=11)NlimitUpper limit on number of night shift in one week (Nlimit=4)RlimitUpper limit on number of days off in four weeks (Rlimit=8)DavgfAverage number of day shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)EavgfAverage number of evening shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)NavgfAverage number of night shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)RavgfAverage number of rest shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)Dnf+,Dnf−Positive and negative deviation fromDavgf for nurse n at f hierarchy (f = 1, 2)Enf+,Enf−Positive and negative deviation fromEavgf for nurse n at f hierarchy (f = 1, 2)Nnf+,Nnf−Positive and negative deviation fromNavgf for nurse n at f hierarchy (f = 1, 2)Rnf+,Rnf−Positive and negative deviation fromRavgf for nurse n at f hierarchy (f = 1, 2)


#### 2.4.2. Mathematical Model of the MLNRP

The decision variables of MLNRP are shown as follows:(1)Xknt=1,nursenwithfmanagenment level is assigned to shiftkon dayt,0,otherwise.Based on the above symbols, the MLNRP mathematical model is built as follows:(2)minZ1=∑i=18wiSi,(3)minZ2=∑n=1N1wdDn1++Dn1−+weEn1++En1−+wnNn1++Nn1−+wrRn1++Rn1−+∑n=N1+1NwdDn2++Dn2−+weEn2++En2−+wnNn2++Nn2−+wrRn2++Rn2−,(4)minZ3=∑i=14w3jCj,subject to(5)∑t=1TX1nt+Dn1++Dn1−=Davg1,∀n=1,…,N1,(6)∑t=1TX2nt+En1++En1−=Eavg1,∀n=1,…,N1,(7)∑t=1TX3nt+Nn1++Nn1−=Navg1,∀n=1,…,N1,(8)∑t=1TX4nt+Rn1++Rn1−=Ravg1,∀n=1,…,N1,(9)∑t=1TX1nt+Dn2++Dn2−=Davg2,∀n=N1+1,…,N,(10)∑t=1TX2nt+En2++En2−=Eavg2,∀n=N1+1,…,N,(11)∑t=1TX3nt+Nn2++Nn2−=Navg2,∀n=N1+1,…,N,(12)∑t=1TX4nt+Rn2++Rn2−=Ravg2,∀n=N1+1,…,N,(13)∑n=1N∑m=14Xkn7m+1=Cj,∀Xkn7m−1+Xkn7m=0,m=1,2,3,4,j=1,(14)∑n=1N∑m=14Xkn7m−1+1=Cj1,∀Xkn7m−2+Xkn7m−1=0,m=1,2,3,4,j=2,(15)∑n=1N∑m=13Xkn7m+1=Cj2,∀Xkn7m+Xkn7m+1=0,m=1,2,3,j=2,(16)Cj=Cj1+Cj2,∀j=2,(17)∑n=1N∑m=14Xkn7m−1+Xkn7m=Cj,∀Xkn7m−1+Xkn7m=1,m=1,2,3,4,j=3,(18)∑n=1N∑m=14Xkn7m=Cj,∀Xkn7m−1+Xkn7m=2,m=1,2,3,4,j=4,(19)∑k=1KXknt=1,∀n,t,(20)X2nt+X3nt+1≤1,∀n,t,(21)∑n=1NX1nt=Rday,∀t,(22)∑n=1NX2nt=Revening,∀t,(23)∑n=1NX3nt=Rnight,∀t,(24)∑n=1N1X1nt≥1,∀t=6,7,13,14,21,27,28,(25)∑t=tτ+6X4nt≥1,∀n,τ=1,…,T−6,(26)∑t=tτ+6X3nt+X2nt≤Nlimit,∀n,τ=1,…,T−6,(27)∑t=ττ+13X4nt≥14−Glimit,∀n,τ=1,…,T−13,(28)∑t=1TX4nt≥Rlimit,∀n,(29)∑t=ττ+3X4nt≤3,∀n,τ=1,…,T−3,(30)∑t=ττ+3X2nt+X3nt≤3,∀n,τ=1,…,T−3,(31)∑n=1N−IcX1nt≥∑n=N−Ic+1NX1nt,∀t,(32)∑n=1N−IcX2nt≥∑n=N−Ic+1NX2nt,∀t,(33)∑n=1N−IcX3nt≥∑n=N−Ic+1NX3nt,∀t,(34)X3nt+X3nt+1+Xknt+3=2,∀k,n,t=1,…,T−3,(35)X2nt+X2nt+1+Xknt+3=2,∀k,n,t=1,…,T−3,(36)X3nt+X2nt+1+Xknt+3=2,∀k,n,t=1,…,T−3,(37)Xknt=0or1,∀k,n,t,(38)Dnf+,Dnf−,Enf+,Enf−,Nnf+,Nnf−,Rnf+,Rnf−≥0,∀n,f.The decision objectives are actually equivalent to the minimization of deviations from the preferences and violation of soft constraints. Equation (2) is expressed as minimization of the whole penalty values of soft constraints violations. Equation (3) is described as minimization of the whole deviation values from equitable shifts of nurses at different management levels. Equation (4) is expressed as optimization of weekend rostering quality. To unify the optimization direction, weight values of equation (4) are set inversely proportional to preferences. By this way, maximization is converted into minimization. For details regarding the setting process of weight value in the objective function, see Section 2.4.3.Equations (5)–(12) are deviation summation from the average number of shifts between charge nurses and general nurses. For details regarding the calculation process of average shift number, see Section 2.4.4.Equations (13)–(18) are statistics of four weekend shift schedules. C1 represents the number of consecutive Saturdays and Sundays off in a roster. C2 equals C21 plus C22, which means the number of consecutive Fridays and Saturdays or Sundays and Mondays off in a roster. C3 indicates the number of a day off on Saturdays or Sundays. C4 represents the number of consecutive Saturdays and Sundays on in a roster.Equations (19)–(24) are four hard constraints that must be met. Equations (25)–(36) are eight soft constraints to be satisfied as much as possible. In equation (25), “in any week” of S1 indicates any seven consecutive days in the roster and so does equation (26). In equation (26), “night shifts” of S2 include shifts E and N and so do equations (30) and (34)–(36). This is because in the studied hospital, the ratio of nurses to beds in the ward is lower than the criterion of the Ministry of Health (0.4:1), and nurses frequently feel tired after work, especially after shift E or shift N. Classifying Shift E and shift N into “night shifts” is to reduce nurses’ fatigue in rostering. Equations (37) and (38) are decision variables.


#### 2.4.3. Weight Setting in the Model

The first kind of weight is penalty value for violation of soft constraints, expressed in w1-w8. The higher the penalty value is, the higher the cost of violating the soft constraint is, and so the less likely the soft constraint will be violated. According to the survey, hospital administrators consider these soft constraints to be equally important. Therefore, the values of w1−w8 are considered as one unit, respectively.The second kind of weight is the preferences of shifts in nurses' minds, expressed inwd,we,wn,wr. The more the nurses like the shift, the more they hope it to be assigned fairly and the larger the penalty value for violation of fairness is. According to the survey, the weight value of shift R is double that of the working shifts and the working shifts are the same.The third kind of weight is preference for weekend rostering, expressed inw31,w32,w33,w34. Weight value of w31 indicates a preference for two-day off on weekends, w32 shows the preference for two-day off with one day on weekends, w33 means the preference for single day off on weekends, and w34 The nurses expect their preferred weekend off pattern to be arranged as many as possible. Since the objective function value of weekend rostering is to minimize, the more the preference weekend off pattern, the lower the corresponding weight value should be set to. The weights are based on survey, as seen in Table 6.Table 6
Weight values in MLNRP.
Objective 1Objective 2Objective 3WeightValues (units)WeightValues (units)WeightValues (units)w1−w81wd,we,wn0.2w310.1wr0.4w320.2w330.3w340.4


#### 2.4.4. Calculation of Hierarchical Fair Shifts

In hierarchical fair rostering, fairness is to pursue absolute fairness at the same hierarchy and relative fairness at different levels. The average number of shifts each team leader nurse should receive in a rostering horizon is different from general nurse, while the average number of shifts in the same management level nurses is almost equivalent. Due to the requirement of management work, charge nurses are assigned more D shifts than general nurses.LetDavg1,Navg1, and Eavg1 be the average numbers of shift D, shift N, and shift E, assigned to charge nurses in the rostering horizons, respectively, Davg2,Navg2, and Eavg2 be the same one assigned to general nurses, respectively, and N1 and N2 be numbers of team leader nurse and general nurse, respectively. The formula is shown in equations (39)–(43).(39)Davg1∗N1+Davg2∗N2=Dtotal−Dheadnurse,(40)Navg1∗N1+Navg2∗N2=Ntotal,(41)Eavg1∗N1+Eavg2∗N2=Etotal,(42)Davg1+Navg1+Eavg1≅Davg2+Navg2+Eavg2≅Wtotal,(43)Davg1>Davg2,where Dtotal, Ntotal, and Etotal represent the total number of day shifts, night shifts, and evening shifts in the rostering horizons, respectively. In the ward under study, Dtotal equals 140 (5∗28=140) shifts, and Ntotal and Etotal equal 56 (2∗28=56) shifts, respectively. Dheadnurse represents the total day shifts of head nurse in the rostering horizons, namely, 20(5∗4=20) day shifts. Wtotal represents the total number of working shifts assigned to each nurse in the rostering horizons, namely, 20 working shifts.A set of feasible and acceptable solutions can be obtained asS0 for a group of one head nurse, two charge nurses, and ten general nurses by simple trial calculation. S0 = {Davg1 = 14, Navg1 = 3, Eavg1 = 3; Davg2 = 9.2, Navg2 = 5, Eavg2 = 5}, as seen in Table 7.Table 7
A set of feasible shifts assignment for nurses.
Shift DShift EShift NWorking shiftHead nurse2020Team leader nurse143320General nurse9.25519.2≅20It is worth mentioning here thatDavg2 equals 9.2 which means that some nurses are assigned ten day shifts and some nurses are assigned nine day shifts. The fair rostering for general nurses is achieved by assigning nine day shifts to them in turn. It can be seen that the MLNRP is more complex than the general NRP. It is well known that NRP is a NP-hard problem. Therefore, heuristic algorithm is more suitable than exact algorithm for the problem of MLNRP.


## 2.1. Premodeling Condition Settings

According to the premodeling structure proposed in this paper, we should grasp the following information: shift character, cycle character, demand character, and nurse character. Take the Geriatric Ward of the Third People's Hospital, Panzhihua, China, as an example. In the Geriatric Ward, elderly patients with chronic diseases who lose self-awareness or mobility will accept medical care here and nurses will provide continuous nursing services. There are three working shifts: day shift (D: 08:00–16:00), evening shift (E: 16:00–24:00), and night shift (N: 00:00–08:00). Each shift covers eight hours. Schedule horizon is four weeks. The number of nurses in each shift is determined. The number of nurses required for shift D is five and that for shift E and N is, respectively, two, from Monday to Sunday. There are thirteen full-time nurses, including one head nurse, two charge nurses, and ten general nurses. They belong to the first, second, and third levels of hierarchical management, respectively. The skill level of head nurse and one charge nurse is A, that of one charge nurse and five general nurses is B, and that of the other five general nurses is C. The abstract of premodeling information is shown in Table2. Detailed information on nurses and demands is shown in Table 3.Table 2
Premodeling condition settings in MLNRP.
ComponentsElementsDetail descriptionsMLNRP∗α: premodeling condition settingsT: shift characterThree-shift✓S: schedule characterCycled schedule✓Schedule horizon4-weekD: demand characterCertain demand✓N: nurse characterOnly full-time✓Hierarchical management3Skill levelA-B-CNumbers13Table 3
Descriptive statistics for nurses and demands in studied local hospital.
Nurse informationDemand of each shiftTitleNumbersHierarchical managementSkill level distribution (A-B-C)Monday–Sunday (D-E-N)Head nurse11st1-0-05-2-2Charge nurse22nd1-1-0General nurse103rd0-5-5


## 2.2. Decision Objective

Objectives provide an optimization direction for nurse rostering, and the satisfaction of objectives reflects the quality of the rosters. When there is a certain conflict between objectives, we often adopt multiobjective optimization.According to the survey, the nurse rostering objectives of the studied hospital are mainly reflected in three aspects: (1) minimizing violations of soft constraints; (2) minimizing the fairness bias of nurse rostering at each hierarchy; and (3) maximizing the quality of weekend rostering. Objectives come from requirements and appeals of hospital managers and nurses for rosters. On the one hand, hospital managers consider nonmandatory management rules as soft constraints and hope to satisfy them as much as possible. On the other hand, the nurses at different hierarchies expect to take fairness separately in rosters and take day-offs as much as possible on weekends. The preference of weekend rostering is ranked from high to low as follows: (1) two days off on weekend; (2) two consecutive days off, one of which is on weekend; (3) single day off on weekend; and (4) no weekends off. A three-objective programming is considered in MLNRP.


## 2.3. Constraints

A feasible and reasonable nurse roster is subject to two types of constraints: hard and soft. Hard constraints are used to determine or judge the feasibility of solutions, while soft constraints are used for improving or measuring the quality of the feasible solutions. The nurse rostering problem considered in this research includes four hard constraints (i.e., H1–H4 in Table4) and eight soft constraints (i.e., S1–S8 in Table 4).Table 4
Description of hard and soft constraints.
Hard constraintsH1No nurse can work more than one shift per dayH2Shift N cannot be assigned immediately after shift E because the end time of shift E is connected with the start time of shift NH3A minimum number of nurses must be guaranteed for each working shift to ensure proper service quality of the hospitalH4From Monday to Sunday, at least one head nurse or charge nurse is required for shift D. Because head nurse is assigned a fixed roster of shift D from Monday to Friday; this constraint translates into at least one charge nurse assigned to shift D on weekends.Soft constraintsS1Each nurse can be assigned 1 day off at least in seven consecutive daysS2Each nurse can be assigned 4 night shifts at most in seven consecutive daysS3Each nurse can be assigned 11 working days at most in 2 weeksS4Each nurse can be assigned 8 days off at least during the rostering period (28 days)S5Each nurse can be assigned 3 consecutive days off at most in the rosterS6Each nurse can be assigned 3 consecutive night shifts at most in the rosterS7The sum of levels A and B nurses should be more than or equal to that of level C nurse in each shift on every day to ensure proper service quality of the hospitalS8One day off should be arranged after a pair of shift E or N, such as E-E, N-N, or N-E


## 2.4. Mathematical Model

Based on the above descriptions, the model can be formulated as a 0-1 integer programming model. Note that since head nurses have been assigned to regular shifts, the rostering of head nurses is no longer considered in modeling.


### 2.4.1. Notations of the Model

The related notations of the model are shown in Table5.Table 5
Notations of the model.
NotationsDefinitionNNumber of nurses available for arrangement,n = 1, …, NN1Number of charge nurses available for arrangement,n = 1, …, N1TNumber of days for the rostering horizon (T = 28), t = 1, …, TKTypes of shift (K = 4), k = 1, 2, 3, 4, represents day shift, evening shift, night shift, and rest shift, respectivelyINumber of soft constraints,i = 1, …, IFManagement level of nurses (F = 2), f = 1, represents charge nurse at 2nd hierarchy; f = 2, represents general nurse at 3rd hierarchySiViolation times of soft constrainti, i = 1, …, ICjNumber of typej weekend rostering, j = 1, 2, 3, 4. (1) j = 1, which means two-day weekends off; (2) j = 2, which means two consecutive days off and one of them is on the weekend; (3) j = 3, which means single day off on weekends; (4) j = 4, which means no weekends offwWeight value,w1−w8 represents penalty value for violation of soft constraints i; wd,we,wn,wr represents the preferences of shift K in nurses’ minds; w31,w32,w33,w34 represents preference for type j weekend rosteringICNumber of nurses with skill C qualificationRdayNumber of nurse requirement for day shift from Monday to SundayReveningNumber of nurse requirement for evening shift from Monday to SundayRnightNumber of nurse requirement for night shift from Monday to SundayGlimitUpper limit on number of working shifts in two weeks (Glimit=11)NlimitUpper limit on number of night shift in one week (Nlimit=4)RlimitUpper limit on number of days off in four weeks (Rlimit=8)DavgfAverage number of day shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)EavgfAverage number of evening shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)NavgfAverage number of night shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)RavgfAverage number of rest shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)Dnf+,Dnf−Positive and negative deviation fromDavgf for nurse n at f hierarchy (f = 1, 2)Enf+,Enf−Positive and negative deviation fromEavgf for nurse n at f hierarchy (f = 1, 2)Nnf+,Nnf−Positive and negative deviation fromNavgf for nurse n at f hierarchy (f = 1, 2)Rnf+,Rnf−Positive and negative deviation fromRavgf for nurse n at f hierarchy (f = 1, 2)


### 2.4.2. Mathematical Model of the MLNRP

The decision variables of MLNRP are shown as follows:(1)Xknt=1,nursenwithfmanagenment level is assigned to shiftkon dayt,0,otherwise.Based on the above symbols, the MLNRP mathematical model is built as follows:(2)minZ1=∑i=18wiSi,(3)minZ2=∑n=1N1wdDn1++Dn1−+weEn1++En1−+wnNn1++Nn1−+wrRn1++Rn1−+∑n=N1+1NwdDn2++Dn2−+weEn2++En2−+wnNn2++Nn2−+wrRn2++Rn2−,(4)minZ3=∑i=14w3jCj,subject to(5)∑t=1TX1nt+Dn1++Dn1−=Davg1,∀n=1,…,N1,(6)∑t=1TX2nt+En1++En1−=Eavg1,∀n=1,…,N1,(7)∑t=1TX3nt+Nn1++Nn1−=Navg1,∀n=1,…,N1,(8)∑t=1TX4nt+Rn1++Rn1−=Ravg1,∀n=1,…,N1,(9)∑t=1TX1nt+Dn2++Dn2−=Davg2,∀n=N1+1,…,N,(10)∑t=1TX2nt+En2++En2−=Eavg2,∀n=N1+1,…,N,(11)∑t=1TX3nt+Nn2++Nn2−=Navg2,∀n=N1+1,…,N,(12)∑t=1TX4nt+Rn2++Rn2−=Ravg2,∀n=N1+1,…,N,(13)∑n=1N∑m=14Xkn7m+1=Cj,∀Xkn7m−1+Xkn7m=0,m=1,2,3,4,j=1,(14)∑n=1N∑m=14Xkn7m−1+1=Cj1,∀Xkn7m−2+Xkn7m−1=0,m=1,2,3,4,j=2,(15)∑n=1N∑m=13Xkn7m+1=Cj2,∀Xkn7m+Xkn7m+1=0,m=1,2,3,j=2,(16)Cj=Cj1+Cj2,∀j=2,(17)∑n=1N∑m=14Xkn7m−1+Xkn7m=Cj,∀Xkn7m−1+Xkn7m=1,m=1,2,3,4,j=3,(18)∑n=1N∑m=14Xkn7m=Cj,∀Xkn7m−1+Xkn7m=2,m=1,2,3,4,j=4,(19)∑k=1KXknt=1,∀n,t,(20)X2nt+X3nt+1≤1,∀n,t,(21)∑n=1NX1nt=Rday,∀t,(22)∑n=1NX2nt=Revening,∀t,(23)∑n=1NX3nt=Rnight,∀t,(24)∑n=1N1X1nt≥1,∀t=6,7,13,14,21,27,28,(25)∑t=tτ+6X4nt≥1,∀n,τ=1,…,T−6,(26)∑t=tτ+6X3nt+X2nt≤Nlimit,∀n,τ=1,…,T−6,(27)∑t=ττ+13X4nt≥14−Glimit,∀n,τ=1,…,T−13,(28)∑t=1TX4nt≥Rlimit,∀n,(29)∑t=ττ+3X4nt≤3,∀n,τ=1,…,T−3,(30)∑t=ττ+3X2nt+X3nt≤3,∀n,τ=1,…,T−3,(31)∑n=1N−IcX1nt≥∑n=N−Ic+1NX1nt,∀t,(32)∑n=1N−IcX2nt≥∑n=N−Ic+1NX2nt,∀t,(33)∑n=1N−IcX3nt≥∑n=N−Ic+1NX3nt,∀t,(34)X3nt+X3nt+1+Xknt+3=2,∀k,n,t=1,…,T−3,(35)X2nt+X2nt+1+Xknt+3=2,∀k,n,t=1,…,T−3,(36)X3nt+X2nt+1+Xknt+3=2,∀k,n,t=1,…,T−3,(37)Xknt=0or1,∀k,n,t,(38)Dnf+,Dnf−,Enf+,Enf−,Nnf+,Nnf−,Rnf+,Rnf−≥0,∀n,f.The decision objectives are actually equivalent to the minimization of deviations from the preferences and violation of soft constraints. Equation (2) is expressed as minimization of the whole penalty values of soft constraints violations. Equation (3) is described as minimization of the whole deviation values from equitable shifts of nurses at different management levels. Equation (4) is expressed as optimization of weekend rostering quality. To unify the optimization direction, weight values of equation (4) are set inversely proportional to preferences. By this way, maximization is converted into minimization. For details regarding the setting process of weight value in the objective function, see Section 2.4.3.Equations (5)–(12) are deviation summation from the average number of shifts between charge nurses and general nurses. For details regarding the calculation process of average shift number, see Section 2.4.4.Equations (13)–(18) are statistics of four weekend shift schedules. C1 represents the number of consecutive Saturdays and Sundays off in a roster. C2 equals C21 plus C22, which means the number of consecutive Fridays and Saturdays or Sundays and Mondays off in a roster. C3 indicates the number of a day off on Saturdays or Sundays. C4 represents the number of consecutive Saturdays and Sundays on in a roster.Equations (19)–(24) are four hard constraints that must be met. Equations (25)–(36) are eight soft constraints to be satisfied as much as possible. In equation (25), “in any week” of S1 indicates any seven consecutive days in the roster and so does equation (26). In equation (26), “night shifts” of S2 include shifts E and N and so do equations (30) and (34)–(36). This is because in the studied hospital, the ratio of nurses to beds in the ward is lower than the criterion of the Ministry of Health (0.4:1), and nurses frequently feel tired after work, especially after shift E or shift N. Classifying Shift E and shift N into “night shifts” is to reduce nurses’ fatigue in rostering. Equations (37) and (38) are decision variables.


### 2.4.3. Weight Setting in the Model

The first kind of weight is penalty value for violation of soft constraints, expressed in w1-w8. The higher the penalty value is, the higher the cost of violating the soft constraint is, and so the less likely the soft constraint will be violated. According to the survey, hospital administrators consider these soft constraints to be equally important. Therefore, the values of w1−w8 are considered as one unit, respectively.The second kind of weight is the preferences of shifts in nurses' minds, expressed inwd,we,wn,wr. The more the nurses like the shift, the more they hope it to be assigned fairly and the larger the penalty value for violation of fairness is. According to the survey, the weight value of shift R is double that of the working shifts and the working shifts are the same.The third kind of weight is preference for weekend rostering, expressed inw31,w32,w33,w34. Weight value of w31 indicates a preference for two-day off on weekends, w32 shows the preference for two-day off with one day on weekends, w33 means the preference for single day off on weekends, and w34 The nurses expect their preferred weekend off pattern to be arranged as many as possible. Since the objective function value of weekend rostering is to minimize, the more the preference weekend off pattern, the lower the corresponding weight value should be set to. The weights are based on survey, as seen in Table 6.Table 6
Weight values in MLNRP.
Objective 1Objective 2Objective 3WeightValues (units)WeightValues (units)WeightValues (units)w1−w81wd,we,wn0.2w310.1wr0.4w320.2w330.3w340.4


### 2.4.4. Calculation of Hierarchical Fair Shifts

In hierarchical fair rostering, fairness is to pursue absolute fairness at the same hierarchy and relative fairness at different levels. The average number of shifts each team leader nurse should receive in a rostering horizon is different from general nurse, while the average number of shifts in the same management level nurses is almost equivalent. Due to the requirement of management work, charge nurses are assigned more D shifts than general nurses.LetDavg1,Navg1, and Eavg1 be the average numbers of shift D, shift N, and shift E, assigned to charge nurses in the rostering horizons, respectively, Davg2,Navg2, and Eavg2 be the same one assigned to general nurses, respectively, and N1 and N2 be numbers of team leader nurse and general nurse, respectively. The formula is shown in equations (39)–(43).(39)Davg1∗N1+Davg2∗N2=Dtotal−Dheadnurse,(40)Navg1∗N1+Navg2∗N2=Ntotal,(41)Eavg1∗N1+Eavg2∗N2=Etotal,(42)Davg1+Navg1+Eavg1≅Davg2+Navg2+Eavg2≅Wtotal,(43)Davg1>Davg2,where Dtotal, Ntotal, and Etotal represent the total number of day shifts, night shifts, and evening shifts in the rostering horizons, respectively. In the ward under study, Dtotal equals 140 (5∗28=140) shifts, and Ntotal and Etotal equal 56 (2∗28=56) shifts, respectively. Dheadnurse represents the total day shifts of head nurse in the rostering horizons, namely, 20(5∗4=20) day shifts. Wtotal represents the total number of working shifts assigned to each nurse in the rostering horizons, namely, 20 working shifts.A set of feasible and acceptable solutions can be obtained asS0 for a group of one head nurse, two charge nurses, and ten general nurses by simple trial calculation. S0 = {Davg1 = 14, Navg1 = 3, Eavg1 = 3; Davg2 = 9.2, Navg2 = 5, Eavg2 = 5}, as seen in Table 7.Table 7
A set of feasible shifts assignment for nurses.
Shift DShift EShift NWorking shiftHead nurse2020Team leader nurse143320General nurse9.25519.2≅20It is worth mentioning here thatDavg2 equals 9.2 which means that some nurses are assigned ten day shifts and some nurses are assigned nine day shifts. The fair rostering for general nurses is achieved by assigning nine day shifts to them in turn. It can be seen that the MLNRP is more complex than the general NRP. It is well known that NRP is a NP-hard problem. Therefore, heuristic algorithm is more suitable than exact algorithm for the problem of MLNRP.


## 2.4.1. Notations of the Model

The related notations of the model are shown in Table5.Table 5
Notations of the model.
NotationsDefinitionNNumber of nurses available for arrangement,n = 1, …, NN1Number of charge nurses available for arrangement,n = 1, …, N1TNumber of days for the rostering horizon (T = 28), t = 1, …, TKTypes of shift (K = 4), k = 1, 2, 3, 4, represents day shift, evening shift, night shift, and rest shift, respectivelyINumber of soft constraints,i = 1, …, IFManagement level of nurses (F = 2), f = 1, represents charge nurse at 2nd hierarchy; f = 2, represents general nurse at 3rd hierarchySiViolation times of soft constrainti, i = 1, …, ICjNumber of typej weekend rostering, j = 1, 2, 3, 4. (1) j = 1, which means two-day weekends off; (2) j = 2, which means two consecutive days off and one of them is on the weekend; (3) j = 3, which means single day off on weekends; (4) j = 4, which means no weekends offwWeight value,w1−w8 represents penalty value for violation of soft constraints i; wd,we,wn,wr represents the preferences of shift K in nurses’ minds; w31,w32,w33,w34 represents preference for type j weekend rosteringICNumber of nurses with skill C qualificationRdayNumber of nurse requirement for day shift from Monday to SundayReveningNumber of nurse requirement for evening shift from Monday to SundayRnightNumber of nurse requirement for night shift from Monday to SundayGlimitUpper limit on number of working shifts in two weeks (Glimit=11)NlimitUpper limit on number of night shift in one week (Nlimit=4)RlimitUpper limit on number of days off in four weeks (Rlimit=8)DavgfAverage number of day shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)EavgfAverage number of evening shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)NavgfAverage number of night shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)RavgfAverage number of rest shift nurse atf hierarchy should be assigned in four weeks (f = 1, 2)Dnf+,Dnf−Positive and negative deviation fromDavgf for nurse n at f hierarchy (f = 1, 2)Enf+,Enf−Positive and negative deviation fromEavgf for nurse n at f hierarchy (f = 1, 2)Nnf+,Nnf−Positive and negative deviation fromNavgf for nurse n at f hierarchy (f = 1, 2)Rnf+,Rnf−Positive and negative deviation fromRavgf for nurse n at f hierarchy (f = 1, 2)


## 2.4.2. Mathematical Model of the MLNRP

The decision variables of MLNRP are shown as follows:(1)Xknt=1,nursenwithfmanagenment level is assigned to shiftkon dayt,0,otherwise.Based on the above symbols, the MLNRP mathematical model is built as follows:(2)minZ1=∑i=18wiSi,(3)minZ2=∑n=1N1wdDn1++Dn1−+weEn1++En1−+wnNn1++Nn1−+wrRn1++Rn1−+∑n=N1+1NwdDn2++Dn2−+weEn2++En2−+wnNn2++Nn2−+wrRn2++Rn2−,(4)minZ3=∑i=14w3jCj,subject to(5)∑t=1TX1nt+Dn1++Dn1−=Davg1,∀n=1,…,N1,(6)∑t=1TX2nt+En1++En1−=Eavg1,∀n=1,…,N1,(7)∑t=1TX3nt+Nn1++Nn1−=Navg1,∀n=1,…,N1,(8)∑t=1TX4nt+Rn1++Rn1−=Ravg1,∀n=1,…,N1,(9)∑t=1TX1nt+Dn2++Dn2−=Davg2,∀n=N1+1,…,N,(10)∑t=1TX2nt+En2++En2−=Eavg2,∀n=N1+1,…,N,(11)∑t=1TX3nt+Nn2++Nn2−=Navg2,∀n=N1+1,…,N,(12)∑t=1TX4nt+Rn2++Rn2−=Ravg2,∀n=N1+1,…,N,(13)∑n=1N∑m=14Xkn7m+1=Cj,∀Xkn7m−1+Xkn7m=0,m=1,2,3,4,j=1,(14)∑n=1N∑m=14Xkn7m−1+1=Cj1,∀Xkn7m−2+Xkn7m−1=0,m=1,2,3,4,j=2,(15)∑n=1N∑m=13Xkn7m+1=Cj2,∀Xkn7m+Xkn7m+1=0,m=1,2,3,j=2,(16)Cj=Cj1+Cj2,∀j=2,(17)∑n=1N∑m=14Xkn7m−1+Xkn7m=Cj,∀Xkn7m−1+Xkn7m=1,m=1,2,3,4,j=3,(18)∑n=1N∑m=14Xkn7m=Cj,∀Xkn7m−1+Xkn7m=2,m=1,2,3,4,j=4,(19)∑k=1KXknt=1,∀n,t,(20)X2nt+X3nt+1≤1,∀n,t,(21)∑n=1NX1nt=Rday,∀t,(22)∑n=1NX2nt=Revening,∀t,(23)∑n=1NX3nt=Rnight,∀t,(24)∑n=1N1X1nt≥1,∀t=6,7,13,14,21,27,28,(25)∑t=tτ+6X4nt≥1,∀n,τ=1,…,T−6,(26)∑t=tτ+6X3nt+X2nt≤Nlimit,∀n,τ=1,…,T−6,(27)∑t=ττ+13X4nt≥14−Glimit,∀n,τ=1,…,T−13,(28)∑t=1TX4nt≥Rlimit,∀n,(29)∑t=ττ+3X4nt≤3,∀n,τ=1,…,T−3,(30)∑t=ττ+3X2nt+X3nt≤3,∀n,τ=1,…,T−3,(31)∑n=1N−IcX1nt≥∑n=N−Ic+1NX1nt,∀t,(32)∑n=1N−IcX2nt≥∑n=N−Ic+1NX2nt,∀t,(33)∑n=1N−IcX3nt≥∑n=N−Ic+1NX3nt,∀t,(34)X3nt+X3nt+1+Xknt+3=2,∀k,n,t=1,…,T−3,(35)X2nt+X2nt+1+Xknt+3=2,∀k,n,t=1,…,T−3,(36)X3nt+X2nt+1+Xknt+3=2,∀k,n,t=1,…,T−3,(37)Xknt=0or1,∀k,n,t,(38)Dnf+,Dnf−,Enf+,Enf−,Nnf+,Nnf−,Rnf+,Rnf−≥0,∀n,f.The decision objectives are actually equivalent to the minimization of deviations from the preferences and violation of soft constraints. Equation (2) is expressed as minimization of the whole penalty values of soft constraints violations. Equation (3) is described as minimization of the whole deviation values from equitable shifts of nurses at different management levels. Equation (4) is expressed as optimization of weekend rostering quality. To unify the optimization direction, weight values of equation (4) are set inversely proportional to preferences. By this way, maximization is converted into minimization. For details regarding the setting process of weight value in the objective function, see Section 2.4.3.Equations (5)–(12) are deviation summation from the average number of shifts between charge nurses and general nurses. For details regarding the calculation process of average shift number, see Section 2.4.4.Equations (13)–(18) are statistics of four weekend shift schedules. C1 represents the number of consecutive Saturdays and Sundays off in a roster. C2 equals C21 plus C22, which means the number of consecutive Fridays and Saturdays or Sundays and Mondays off in a roster. C3 indicates the number of a day off on Saturdays or Sundays. C4 represents the number of consecutive Saturdays and Sundays on in a roster.Equations (19)–(24) are four hard constraints that must be met. Equations (25)–(36) are eight soft constraints to be satisfied as much as possible. In equation (25), “in any week” of S1 indicates any seven consecutive days in the roster and so does equation (26). In equation (26), “night shifts” of S2 include shifts E and N and so do equations (30) and (34)–(36). This is because in the studied hospital, the ratio of nurses to beds in the ward is lower than the criterion of the Ministry of Health (0.4:1), and nurses frequently feel tired after work, especially after shift E or shift N. Classifying Shift E and shift N into “night shifts” is to reduce nurses’ fatigue in rostering. Equations (37) and (38) are decision variables.


## 2.4.3. Weight Setting in the Model

The first kind of weight is penalty value for violation of soft constraints, expressed in w1-w8. The higher the penalty value is, the higher the cost of violating the soft constraint is, and so the less likely the soft constraint will be violated. According to the survey, hospital administrators consider these soft constraints to be equally important. Therefore, the values of w1−w8 are considered as one unit, respectively.The second kind of weight is the preferences of shifts in nurses' minds, expressed inwd,we,wn,wr. The more the nurses like the shift, the more they hope it to be assigned fairly and the larger the penalty value for violation of fairness is. According to the survey, the weight value of shift R is double that of the working shifts and the working shifts are the same.The third kind of weight is preference for weekend rostering, expressed inw31,w32,w33,w34. Weight value of w31 indicates a preference for two-day off on weekends, w32 shows the preference for two-day off with one day on weekends, w33 means the preference for single day off on weekends, and w34 The nurses expect their preferred weekend off pattern to be arranged as many as possible. Since the objective function value of weekend rostering is to minimize, the more the preference weekend off pattern, the lower the corresponding weight value should be set to. The weights are based on survey, as seen in Table 6.Table 6
Weight values in MLNRP.
Objective 1Objective 2Objective 3WeightValues (units)WeightValues (units)WeightValues (units)w1−w81wd,we,wn0.2w310.1wr0.4w320.2w330.3w340.4


## 2.4.4. Calculation of Hierarchical Fair Shifts

In hierarchical fair rostering, fairness is to pursue absolute fairness at the same hierarchy and relative fairness at different levels. The average number of shifts each team leader nurse should receive in a rostering horizon is different from general nurse, while the average number of shifts in the same management level nurses is almost equivalent. Due to the requirement of management work, charge nurses are assigned more D shifts than general nurses.LetDavg1,Navg1, and Eavg1 be the average numbers of shift D, shift N, and shift E, assigned to charge nurses in the rostering horizons, respectively, Davg2,Navg2, and Eavg2 be the same one assigned to general nurses, respectively, and N1 and N2 be numbers of team leader nurse and general nurse, respectively. The formula is shown in equations (39)–(43).(39)Davg1∗N1+Davg2∗N2=Dtotal−Dheadnurse,(40)Navg1∗N1+Navg2∗N2=Ntotal,(41)Eavg1∗N1+Eavg2∗N2=Etotal,(42)Davg1+Navg1+Eavg1≅Davg2+Navg2+Eavg2≅Wtotal,(43)Davg1>Davg2,where Dtotal, Ntotal, and Etotal represent the total number of day shifts, night shifts, and evening shifts in the rostering horizons, respectively. In the ward under study, Dtotal equals 140 (5∗28=140) shifts, and Ntotal and Etotal equal 56 (2∗28=56) shifts, respectively. Dheadnurse represents the total day shifts of head nurse in the rostering horizons, namely, 20(5∗4=20) day shifts. Wtotal represents the total number of working shifts assigned to each nurse in the rostering horizons, namely, 20 working shifts.A set of feasible and acceptable solutions can be obtained asS0 for a group of one head nurse, two charge nurses, and ten general nurses by simple trial calculation. S0 = {Davg1 = 14, Navg1 = 3, Eavg1 = 3; Davg2 = 9.2, Navg2 = 5, Eavg2 = 5}, as seen in Table 7.Table 7
A set of feasible shifts assignment for nurses.
Shift DShift EShift NWorking shiftHead nurse2020Team leader nurse143320General nurse9.25519.2≅20It is worth mentioning here thatDavg2 equals 9.2 which means that some nurses are assigned ten day shifts and some nurses are assigned nine day shifts. The fair rostering for general nurses is achieved by assigning nine day shifts to them in turn. It can be seen that the MLNRP is more complex than the general NRP. It is well known that NRP is a NP-hard problem. Therefore, heuristic algorithm is more suitable than exact algorithm for the problem of MLNRP.


## 3. The Proposed Algorithms

In this section, we firstly adopted two hybrid algorithms based on MOGWO to solve the problem of MLNRP. In MOGWO, the iteration of the whole wolves is carried out through three leader wolves, and the leader wolves come from the whole wolves. Therefore, MOGWO algorithm has certain dependence on the three wolves of initial wolves. Consequently, we first optimize the initial wolves by the heuristic approaches of NSGAII [31] or MOPSO [12] and then employ MOGWO to explore the optimal solution. Finally, we compare the performance of NSGAII-MOGWO and MOPSO-MOGWO with those of corresponding single algorithms, namely, standard NSGAII, standard MOPSO, and standard MOGWO.As the principles and operators of the three standard algorithms were introduced in the literature, we do not repeat them here. We take NSGAII-MOGWO as an example to illustrate the heuristic principles. In this hybrid algorithm, the first rank wolves resulted from NSGAII algorithm are taken as the initial solutions of MOGWO algorithm. The better wolf of alpha, beta, and delta can be found from the optimized initial wolves. The quality of the solution is further improved by iterative optimization of MOGWO.


### 3.1. Flowchart of Proposed Algorithm

In flowchart of the proposed NSGAII-MOGWO, the input of MOGWO is the output of NSGAII (see Figure1).Figure 1
Flowchart of the proposed NSGAII-MOGWO algorithm.


### 3.2. Encoding

One solution is a roster ofN nurses scheduled for T days. In the roster, shift D is represented by numeral 1, shift E by numeral 2, shift N by numeral 3, and shift R by numeral 4. This roster can also reshape to a 1 ∗ N ∗ T transversal vector, together with other reshape rosters, to form a group of initial solutions.


### 3.3. Initial Solution

In order to keep the diversity of solutions as much as possible, the initial schedule is generated randomly.


### 3.4. Fitness Function

The fitness function come from the multiobjective function of mathematical model to evaluate the quality of each solution updated in each iteration. The Pareto nondominant solution is adopted to compare the quality of solutions.


### 3.5. Postiteration Adjustment

After an iteration of each solution, the values in the roster may no longer be 1, 2, 3, or 4 and need to be restored. Any integer values between 0 and 3 can be obtained by the following equation:(44)Xid=ceilmodXid,4,where Xid is defined as the shift type to be assigned for the ith nurse on the dth day. If Xid = 1, shift D is assigned; if Xid = 2, shift E is assigned; if Xid = 3, shift N is assigned; and if Xid = 0, shift R is assigned.


### 3.6. Judgement and Repairing

Note that the initial solution generated inSection 3.3 is not necessarily a feasible roster. In addition, iteration and updating may make the solution infeasible. Therefore, the feasibility of the solution is judged and repaired by the following three hard constraints.HC1: shift D on Saturdays and Sundays with at least one team leader nurse.HC2: a minimum number of nurses must be guaranteed for each working shift.HC3: a work pattern of E-N is not allowed.


#### 3.6.1. The Neighbourhood Structure

For the unsatisfactory hard constraints, the repairing is based on the method of variable neighbourhood structure. In the examples, the nurse in boldface is the one who best meets the selection criteria.(1) VNS1. Given that nurse k (with 1st level) and nurse l (with 1st level) are assigned non-D shift on weekends, select one with a greater insufficiency in fair rostering of D shift and assign it to her or him. The other one left is arranged for R shift. The purpose of VNS1 is to satisfy HC1 while improving fair rostering and weekend rostering quality. An example of VNS1 is shown in Table 8.Table 8
An example of VNS1.
NursesBefore swapAfter swapSaturdaySaturdayTeam leader nursekNDTeam leader nurselER(2) VNS2. Given that nurses of D shift are insufficient while nurses of E shift are over equipped on the same day, select nurse k with a greater surplus in fair rostering of E shift and assign D shift to her or him. The same is true for other shifts that do not meet the demand. The purpose of VNS2 is to satisfy HC2 while considering fair rostering at the same time. An example of VNS2 is shown in Table 9.Table 9
An example of VNS2.
NursesBefore swapAfter swapDayjDayjNurse kEDSum D shiftInsufficientSatisfiedSum E shiftOverequippedSatisfied(3) VNS3. Given that nurse k has an E shift followed by N shift on day i, to destroy the structure of E-N, move E shift or N shift depending on which has greater insufficiency in fair rostering. Next, vertically swap it with the nurse who has a greater insufficiency in the shifts of fair rostering. The purpose of VNS3 is to satisfy HC3 while considering fair rostering at the same time. An example of VNS3 is shown in Table 10.Table 10
An example of VNS3.
NursesBefore swapAfter swapDayiDayjDayiDayjNursekENEENurse lRERNThe neighbourhood structures should guarantee the feasibility of nurse roster. Therefore, in the process of repairing, the constraints that have been met should not be violated as far as possible.


## 3.1. Flowchart of Proposed Algorithm

In flowchart of the proposed NSGAII-MOGWO, the input of MOGWO is the output of NSGAII (see Figure1).Figure 1
Flowchart of the proposed NSGAII-MOGWO algorithm.


## 3.2. Encoding

One solution is a roster ofN nurses scheduled for T days. In the roster, shift D is represented by numeral 1, shift E by numeral 2, shift N by numeral 3, and shift R by numeral 4. This roster can also reshape to a 1 ∗ N ∗ T transversal vector, together with other reshape rosters, to form a group of initial solutions.


## 3.3. Initial Solution

In order to keep the diversity of solutions as much as possible, the initial schedule is generated randomly.


## 3.4. Fitness Function

The fitness function come from the multiobjective function of mathematical model to evaluate the quality of each solution updated in each iteration. The Pareto nondominant solution is adopted to compare the quality of solutions.


## 3.5. Postiteration Adjustment

After an iteration of each solution, the values in the roster may no longer be 1, 2, 3, or 4 and need to be restored. Any integer values between 0 and 3 can be obtained by the following equation:(44)Xid=ceilmodXid,4,where Xid is defined as the shift type to be assigned for the ith nurse on the dth day. If Xid = 1, shift D is assigned; if Xid = 2, shift E is assigned; if Xid = 3, shift N is assigned; and if Xid = 0, shift R is assigned.


## 3.6. Judgement and Repairing

Note that the initial solution generated inSection 3.3 is not necessarily a feasible roster. In addition, iteration and updating may make the solution infeasible. Therefore, the feasibility of the solution is judged and repaired by the following three hard constraints.HC1: shift D on Saturdays and Sundays with at least one team leader nurse.HC2: a minimum number of nurses must be guaranteed for each working shift.HC3: a work pattern of E-N is not allowed.


### 3.6.1. The Neighbourhood Structure

For the unsatisfactory hard constraints, the repairing is based on the method of variable neighbourhood structure. In the examples, the nurse in boldface is the one who best meets the selection criteria.(1) VNS1. Given that nurse k (with 1st level) and nurse l (with 1st level) are assigned non-D shift on weekends, select one with a greater insufficiency in fair rostering of D shift and assign it to her or him. The other one left is arranged for R shift. The purpose of VNS1 is to satisfy HC1 while improving fair rostering and weekend rostering quality. An example of VNS1 is shown in Table 8.Table 8
An example of VNS1.
NursesBefore swapAfter swapSaturdaySaturdayTeam leader nursekNDTeam leader nurselER(2) VNS2. Given that nurses of D shift are insufficient while nurses of E shift are over equipped on the same day, select nurse k with a greater surplus in fair rostering of E shift and assign D shift to her or him. The same is true for other shifts that do not meet the demand. The purpose of VNS2 is to satisfy HC2 while considering fair rostering at the same time. An example of VNS2 is shown in Table 9.Table 9
An example of VNS2.
NursesBefore swapAfter swapDayjDayjNurse kEDSum D shiftInsufficientSatisfiedSum E shiftOverequippedSatisfied(3) VNS3. Given that nurse k has an E shift followed by N shift on day i, to destroy the structure of E-N, move E shift or N shift depending on which has greater insufficiency in fair rostering. Next, vertically swap it with the nurse who has a greater insufficiency in the shifts of fair rostering. The purpose of VNS3 is to satisfy HC3 while considering fair rostering at the same time. An example of VNS3 is shown in Table 10.Table 10
An example of VNS3.
NursesBefore swapAfter swapDayiDayjDayiDayjNursekENEENurse lRERNThe neighbourhood structures should guarantee the feasibility of nurse roster. Therefore, in the process of repairing, the constraints that have been met should not be violated as far as possible.


## 3.6.1. The Neighbourhood Structure

For the unsatisfactory hard constraints, the repairing is based on the method of variable neighbourhood structure. In the examples, the nurse in boldface is the one who best meets the selection criteria.(1) VNS1. Given that nurse k (with 1st level) and nurse l (with 1st level) are assigned non-D shift on weekends, select one with a greater insufficiency in fair rostering of D shift and assign it to her or him. The other one left is arranged for R shift. The purpose of VNS1 is to satisfy HC1 while improving fair rostering and weekend rostering quality. An example of VNS1 is shown in Table 8.Table 8
An example of VNS1.
NursesBefore swapAfter swapSaturdaySaturdayTeam leader nursekNDTeam leader nurselER(2) VNS2. Given that nurses of D shift are insufficient while nurses of E shift are over equipped on the same day, select nurse k with a greater surplus in fair rostering of E shift and assign D shift to her or him. The same is true for other shifts that do not meet the demand. The purpose of VNS2 is to satisfy HC2 while considering fair rostering at the same time. An example of VNS2 is shown in Table 9.Table 9
An example of VNS2.
NursesBefore swapAfter swapDayjDayjNurse kEDSum D shiftInsufficientSatisfiedSum E shiftOverequippedSatisfied(3) VNS3. Given that nurse k has an E shift followed by N shift on day i, to destroy the structure of E-N, move E shift or N shift depending on which has greater insufficiency in fair rostering. Next, vertically swap it with the nurse who has a greater insufficiency in the shifts of fair rostering. The purpose of VNS3 is to satisfy HC3 while considering fair rostering at the same time. An example of VNS3 is shown in Table 10.Table 10
An example of VNS3.
NursesBefore swapAfter swapDayiDayjDayiDayjNursekENEENurse lRERNThe neighbourhood structures should guarantee the feasibility of nurse roster. Therefore, in the process of repairing, the constraints that have been met should not be violated as far as possible.


## 4. Computational Experiments and Results

In this section, all algorithms were coded in MATLAB R2017a and implemented on a computer of DESKTOP-HPQ946M, Intel(R) Core(TM) i7-7500U CPU 2.7 GHz, 8 GB RAM. To compare the general performance of hybrid algorithm based on standard algorithm, parameter settings are almost consistent with the corresponding standard parameter settings (see Table11 for parameter details).Table 11
Parameters of MOGWO-based hybrid algorithm.
ParameterNSGAII-MOGWOMOPSO-MOGWONSGAIIMOGWOMOPSOMaxIt100100100100100npop100100100100100nRep/nArchive100100—100100nGrid77—77Alpha0.10.1—0.10.1Beta33—33Gamma22—22Pcrossover0.7—0.7——Pmutation0.4—0.4——mu0.020.10.02—0.1w—0.5——0.5wdamp—0.99——0.99c1—1——1c2—2——2


### 4.1. Comparison of Computational Results

A real dataset from studied hospital was used to evaluate the performance of all the competing algorithms. Considering the stochastic characteristics of metaheuristic algorithm, 10 independent runs were taken for each algorithm. To visualize the computational results of the algorithms, we randomly selected one run of results, put them in the same three-dimensional coordinate space, and projected them onto two-dimensional planes, respectively (see Figure2).Figure 2
Comparison results of four algorithms for MLNRP. (a) Nondominant solutions. (b) Nondominant solution in 2D. (c) Nondominant solution in 2D. (d) Nondominant solution in 2D.
(a)(b)(c)(d)In Figure2, SC rostering quality represents the sum of soft constraints violated in rostering. The lower the value of SC rostering quality, the higher the quality of the roster. Fair rostering quality shows the general deviation of nurses from relative fair shift arrangement. The lower the value of fair rostering quality, the better the quality of the roster. Weekend rostering quality indicates weekend rest arrangements. The lower the value of weekend rostering quality, the better the quality of the roster. When the objective value is zero, the optimal solution on the objective is achieved.According to the results, the Pareto solutions obtained by MOPSO are the most dispersive, while the Pareto solutions obtained by MOGWO are the most concentrated. As to the quality of the solutions, the Pareto solutions obtained by NSGAII-MOGWO are superior to those obtained by other four algorithms. Furthermore, NSGAII-MOGOW obtains more Pareto solutions with optimal relative fairness objective. This is very important for a team of nurses who advocate respective fairness. A roster embodying the best relative fairness is shown in Table12.Table 12
A roster obtained by algorithm NSGAII-MOGWO.
MTWTFSSMTWTFSSMTWTFSSMTWTFSS∑​DNER1➀ADDDDDRRDDDDDRRDDDDDRRDDDDDRR200082➁ARNEDNDRRDDDRDDDDDDRNDDERDERR143383➁BNRDNERDREDDERRDDRDDDRDEDRDDD143384➂BDRNRRDNERREEDDRDEEDEDNDRRDED105585➂CEDRNRDDNERRDDERRDERDDNERRND95596➂BDEDRERRDRERDDNERRDNEDNDRNRDN95597➂CDDEDNDRRDNERRDNERRDNERRDREDN95598➂BRDDDDNERRDDNERDNERRRNERRDNDE95599➂CRRREDDNDRRDNERRDNERDDRDNEDNE955910➂BERRDDNDNERRDNERRDNERRDNEDRDD955911➂CNERRDEDDNERDDNERDDNDRRDNERRD1055812➂BDNDRREDEDNERNDNERRDDERRDNDRR955913➂CRDNERREDDDNRRDDNERRDNERDDNER9559D5555555555555555555555555555Solutions = (16, 0, 15.4)S0 = {Davg1 = 14, Navg1 = 3, Eavg1 = 3; Davg2 = 9.2, Navg2 = 5, Eavg2 = 5}N2222222222222222222222222222E2222222222222222222222222222➀: head nurse; ➁: team leader nurse; ➂: general nurse.In order to evaluate the performance of multiobjective algorithm in a statistical significance, we adopt two evaluation indexes: generational distance (GD) and spacing (SP). We use min-max normalization for each objective data to eliminate the dimension difference. The formula should be referred to as equations (45) and (46).(45)GD=∑i=1ndi2n,(46)SP≜∑i=1nd¯−di2n−1.The concept of GD was introduced as an indicator of the approximation degree between the obtained Pareto frontier and the optimal Pareto frontier. The vectordi in equation (45) is the Euclidean distance between the solution i on the Pareto frontier obtained and the nearest solution of the Pareto optimal set. The notation n refers to the number of nondominant solutions on Pareto Frontier obtained. The smaller the value of GD, the better the convergence of the algorithm. When GD equals zero, all nondominant solutions in the Pareto frontier are included on the optimal Pareto frontier.The concept of SP was proposed as a measure of distribution throughout the nondominant solutions on the Pareto frontier obtained. The vectordi in equation (46) is minimum sum of absolute value of difference between current nondominant solution and other nondominant solution on the Pareto frontier obtained. d¯ is the mean of all. The smaller the SP value is, the better the uniformity of solution distribution is. When SP equals zero, the nondominant solutions on the Pareto frontier are evenly distributed at equal distances.The statistical results of the two indexes are listed in Tables13 and 14. Since computing time is also an important evaluation index of the algorithm, the computing time of five algorithms for ten independent runs is shown in Table 15. For MLNRP model with relative fairness objective, Pareto solutions with optimal relative fairness objective can be obtained, which is a highlight of the algorithm. The number of runs with Pareto solutions on zero objective value of relative fairness in ten independent runs is shown in Table 16. In all tables, the best results are shown in bold.Table 13
Results of GD for five algorithms in ten independent runs.
GDNSGAII- MOGWOMOPSO- MOGWONSGAIIMOGWOMOPSOBest0.01050.01770.01370.02470.032Worst0.02960.03800.03540.06640.0527Average0.01710.02420.02110.03990.0418Std.0.00640.01310.00770.01130.0062Table 14
Results of SP for five algorithms in ten independent runs.
SPNSGAII- MOGWOMOPSO- MOGWONSGAIIMOGWOMOPSOBest0.05630.10220.06580.08100.1523Worst0.14070.17230.14990.29130.2858Average0.09620.13090.10360.17380.1932Std.0.02820.02360.03580.05740.0395Table 15
Computing time for five algorithms in ten independent runs.
Time (s)NSGAII- MOGWOMOPSO- MOGWONSGAIIMOGWOMOPSOBest468.8465.3147.5461.3128.1Worst914.6651.2289.8543.1289.4Average674.31528.79244.94505.4233.63Std.182.2461.3753.6927.5349.51Table 16
Runs of the optimal solution on relative fairness objective in ten independent runs.
NSGAII- MOGWOMOPSO- MOGWONSGAIIMOGWOMOPSORuns50300According to the statistical results of these five algorithms, we can get the following statistical results. First, the Pareto solutions obtained by the NSGAII-MOGWO are more evenly distributed than those obtained by other four algorithms. Second, although MOGWO has good performance in many engineering optimization, its performance in nurse rostering is not outstanding. However, the performance of MOGWO can be improved by combining with NSGAII or MOPSO. Third, in the two hybrid algorithms, NSGAII-MOGWO outperforms MOPSO-MOGWO in many aspects except for computing time. This may be because NSGAII is more time-consuming but is more powerful than MOPSO in optimizing initial solutions. Fourth, among the five algorithms, the average computing time of MOPSO is the shortest, and the average GD and SP values of MOPSO are the worst. Interestingly, NSGAII-MOGWO is the opposite. Lastly, NSGAII-MOGWO has obtained some Pareto solutions with optimal relative fairness objective in five rounds out of ten independent runs, while NSGAII has only three runs and other three algorithms have none. This shows that NSGAII-MOGWO is easier to find the relative fairest rosters.


## 4.1. Comparison of Computational Results

A real dataset from studied hospital was used to evaluate the performance of all the competing algorithms. Considering the stochastic characteristics of metaheuristic algorithm, 10 independent runs were taken for each algorithm. To visualize the computational results of the algorithms, we randomly selected one run of results, put them in the same three-dimensional coordinate space, and projected them onto two-dimensional planes, respectively (see Figure2).Figure 2
Comparison results of four algorithms for MLNRP. (a) Nondominant solutions. (b) Nondominant solution in 2D. (c) Nondominant solution in 2D. (d) Nondominant solution in 2D.
(a)(b)(c)(d)In Figure2, SC rostering quality represents the sum of soft constraints violated in rostering. The lower the value of SC rostering quality, the higher the quality of the roster. Fair rostering quality shows the general deviation of nurses from relative fair shift arrangement. The lower the value of fair rostering quality, the better the quality of the roster. Weekend rostering quality indicates weekend rest arrangements. The lower the value of weekend rostering quality, the better the quality of the roster. When the objective value is zero, the optimal solution on the objective is achieved.According to the results, the Pareto solutions obtained by MOPSO are the most dispersive, while the Pareto solutions obtained by MOGWO are the most concentrated. As to the quality of the solutions, the Pareto solutions obtained by NSGAII-MOGWO are superior to those obtained by other four algorithms. Furthermore, NSGAII-MOGOW obtains more Pareto solutions with optimal relative fairness objective. This is very important for a team of nurses who advocate respective fairness. A roster embodying the best relative fairness is shown in Table12.Table 12
A roster obtained by algorithm NSGAII-MOGWO.
MTWTFSSMTWTFSSMTWTFSSMTWTFSS∑​DNER1➀ADDDDDRRDDDDDRRDDDDDRRDDDDDRR200082➁ARNEDNDRRDDDRDDDDDDRNDDERDERR143383➁BNRDNERDREDDERRDDRDDDRDEDRDDD143384➂BDRNRRDNERREEDDRDEEDEDNDRRDED105585➂CEDRNRDDNERRDDERRDERDDNERRND95596➂BDEDRERRDRERDDNERRDNEDNDRNRDN95597➂CDDEDNDRRDNERRDNERRDNERRDREDN95598➂BRDDDDNERRDDNERDNERRRNERRDNDE95599➂CRRREDDNDRRDNERRDNERDDRDNEDNE955910➂BERRDDNDNERRDNERRDNERRDNEDRDD955911➂CNERRDEDDNERDDNERDDNDRRDNERRD1055812➂BDNDRREDEDNERNDNERRDDERRDNDRR955913➂CRDNERREDDDNRRDDNERRDNERDDNER9559D5555555555555555555555555555Solutions = (16, 0, 15.4)S0 = {Davg1 = 14, Navg1 = 3, Eavg1 = 3; Davg2 = 9.2, Navg2 = 5, Eavg2 = 5}N2222222222222222222222222222E2222222222222222222222222222➀: head nurse; ➁: team leader nurse; ➂: general nurse.In order to evaluate the performance of multiobjective algorithm in a statistical significance, we adopt two evaluation indexes: generational distance (GD) and spacing (SP). We use min-max normalization for each objective data to eliminate the dimension difference. The formula should be referred to as equations (45) and (46).(45)GD=∑i=1ndi2n,(46)SP≜∑i=1nd¯−di2n−1.The concept of GD was introduced as an indicator of the approximation degree between the obtained Pareto frontier and the optimal Pareto frontier. The vectordi in equation (45) is the Euclidean distance between the solution i on the Pareto frontier obtained and the nearest solution of the Pareto optimal set. The notation n refers to the number of nondominant solutions on Pareto Frontier obtained. The smaller the value of GD, the better the convergence of the algorithm. When GD equals zero, all nondominant solutions in the Pareto frontier are included on the optimal Pareto frontier.The concept of SP was proposed as a measure of distribution throughout the nondominant solutions on the Pareto frontier obtained. The vectordi in equation (46) is minimum sum of absolute value of difference between current nondominant solution and other nondominant solution on the Pareto frontier obtained. d¯ is the mean of all. The smaller the SP value is, the better the uniformity of solution distribution is. When SP equals zero, the nondominant solutions on the Pareto frontier are evenly distributed at equal distances.The statistical results of the two indexes are listed in Tables13 and 14. Since computing time is also an important evaluation index of the algorithm, the computing time of five algorithms for ten independent runs is shown in Table 15. For MLNRP model with relative fairness objective, Pareto solutions with optimal relative fairness objective can be obtained, which is a highlight of the algorithm. The number of runs with Pareto solutions on zero objective value of relative fairness in ten independent runs is shown in Table 16. In all tables, the best results are shown in bold.Table 13
Results of GD for five algorithms in ten independent runs.
GDNSGAII- MOGWOMOPSO- MOGWONSGAIIMOGWOMOPSOBest0.01050.01770.01370.02470.032Worst0.02960.03800.03540.06640.0527Average0.01710.02420.02110.03990.0418Std.0.00640.01310.00770.01130.0062Table 14
Results of SP for five algorithms in ten independent runs.
SPNSGAII- MOGWOMOPSO- MOGWONSGAIIMOGWOMOPSOBest0.05630.10220.06580.08100.1523Worst0.14070.17230.14990.29130.2858Average0.09620.13090.10360.17380.1932Std.0.02820.02360.03580.05740.0395Table 15
Computing time for five algorithms in ten independent runs.
Time (s)NSGAII- MOGWOMOPSO- MOGWONSGAIIMOGWOMOPSOBest468.8465.3147.5461.3128.1Worst914.6651.2289.8543.1289.4Average674.31528.79244.94505.4233.63Std.182.2461.3753.6927.5349.51Table 16
Runs of the optimal solution on relative fairness objective in ten independent runs.
NSGAII- MOGWOMOPSO- MOGWONSGAIIMOGWOMOPSORuns50300According to the statistical results of these five algorithms, we can get the following statistical results. First, the Pareto solutions obtained by the NSGAII-MOGWO are more evenly distributed than those obtained by other four algorithms. Second, although MOGWO has good performance in many engineering optimization, its performance in nurse rostering is not outstanding. However, the performance of MOGWO can be improved by combining with NSGAII or MOPSO. Third, in the two hybrid algorithms, NSGAII-MOGWO outperforms MOPSO-MOGWO in many aspects except for computing time. This may be because NSGAII is more time-consuming but is more powerful than MOPSO in optimizing initial solutions. Fourth, among the five algorithms, the average computing time of MOPSO is the shortest, and the average GD and SP values of MOPSO are the worst. Interestingly, NSGAII-MOGWO is the opposite. Lastly, NSGAII-MOGWO has obtained some Pareto solutions with optimal relative fairness objective in five rounds out of ten independent runs, while NSGAII has only three runs and other three algorithms have none. This shows that NSGAII-MOGWO is easier to find the relative fairest rosters.


## 5. Conclusions

This article has studied a special kind of multilevel nurse rostering problem (MLNRP). The main conclusions of this paper are as follows:(1)
This paper summarizes some characteristics of this special kind of multilevel nurse rostering problem (MLNRP). Grasping the characteristics of the problem is helpful for modeling and solving.(2)
Based on literature and hospital research, this paper proposes a simple and general model structure for nurse rostering problem. This can help hospital administrators to collect information needed for modeling faster and more completely.(3)
This paper presents an applied theoretical model of MLNRP, which is close to real-world nurse rostering problem. The model aims at meeting soft constraints and relative fair rostering and improving weekend rostering quality, taking resource constraints such as hospital demands and nurses’ preferences into account.(4)
Considering the differences of job requirements and fairness preference between charge nurses and general nurses, this paper put forward a relative fairness rostering strategy and its calculation method.(5)
In solving the multilevel nurse rostering problem, MOGWO does not as good as it does on other engineering optimization problems. However, after combining with NSGAII or MOPSO, their ability to find better Pareto solutions is greatly enhanced.(6)
The hybrid algorithm NSGAII-MOGWO outperforms MOPSO-MOGWO in the quality of Pareto solutions, which may be attributed to the fact that NSGAII is more powerful than MOPSO for optimization of initial solutions.(7)
The hybrid algorithm NSGAII-MOGWO is superior to the other four algorithms in exploring better Pareto solutions, although the computation time is the longest. However, it is acceptable for hospital managers because it is more important to arrange a satisfactory roster for nurses in understaffing.Future research will be carried out from the following four aspects: (1) from the perspective of human factor engineering, the effects of different rostering strategies on nurses’ fatigue, emotions, and behaviour performance will be compared and studied; (2) research on nurse rostering in multiple scenarios by adjusting the scale, skill level distribution, and hierarchy proportion of nurses; (3) rostering strategy research—change the inherent rostering model in studying more about robust flexible rostering model under uncertain demand; and (4) research on the principle and characteristic of the algorithms. The more we master the characteristics of the algorithm, the more we can choose the algorithm rationally rather than randomly solving the optimization problem.



---

*Source: 6637207-2021-01-12.xml*