Developing three-phase modified bat algorithms to solve medical staff scheduling problems while considering minimal violations of preferences and mean workload

Abstract

BACKGROUND:

This research studies a medical staff scheduling problem, which includes government regulations and hospital regulations (hard constraints) and the medical staff’s preferences (soft constraints).

OBJECTIVE:

The objective function is to minimize the violations (or dissatisfaction) of medical staff’s preferences.

METHODS:

This study develops three variants of the three-phase modified bat algorithms (BAs), named BA1, BA2, and BA3, in order to satisfy the hard constraints, minimize the dissatisfaction of the medical staff and balance the workload of the medical staff. To ensure workload balance, this study balances the workload among medical staff without increasing the objective function values.

RESULTS:

Based on the numerical results, the BA3 outperforms the BA1, BA2, and particle swarm optimization (PSO). The robustness of the BA1, BA2, and BA3 is verified. Finally, conclusions are drawn, and directions for future research are highlighted.

CONCLUSIONS:

The framework of this research can be used as a reference for other hospitals seeking to determine their future medical staff schedule.

Keywords

Bat algorithm (BA)medical staff scheduling nurse scheduling/rostering medical staff’s preferences workload balance

1. Introduction

Emergency departments, which specialize in treating patients with sudden and unexpected injuries, are a critical part of modern hospitals and feature diverse patients with various medical conditions [1, 2, 3]. The public demand for medical treatment is continually increasing, and insufficient medical resources have led to patient overcrowding and bed shortages in emergency departments. In addition, the stressful work environment and unsatisfactory pay have led to overworked medical personnel and labor shortages [4, 5]. Among such shortages, a lack of nurses impedes patients from acquiring satisfactory medical treatment. Therefore, appropriately deploying emergency staff to take care of patients has become a crucial challenge for all medical institutions [6, 7, 8, 9, 10]. Labor costs have been rising gradually. Numerous industries, including technology, electronics, service, and even medical industries, have incorporated the business model of operating 24 hours a day, 7 days a week, 52 weeks a year to serve their customers. Allocating the labor force into appropriate units is a decision problem for hospital managers [11, 12]. Every day, uncertainty surrounds patient-oriented hospital services. For example, the number and types of patients vary daily, and medical personnel are the frontline workers in medical facilities, contacting patients the most directly and frequently [13, 14]. Incorrectly deploying medical personnel leads to their physical and psychological fatigue and indirectly reduces the quality of medical services. Effectively deploying medical staff substantially affects the quality of medical services [10].

Scheduling medical personnel is a key procedure in healthcare organizations’ human resource allocation. Numerous restrictions have complicated the medical staff scheduling problem (MSSP) [11, 15, 16, 17, 18, 19, 20, 21]. Burke et al. [22] addressed the complexity of the MSSP. Creating shift schedules that create a fair work environment and balance the preferences of medical personnel enhances the work attitudes as well as mitigates the workload of medical personnel profoundly. Developing a medical workforce scheduling system is imperative to creating effective and fair shift schedules, thereby satisfying the preferences of medical personnel. Hospital managers are required to personally schedule medical personnel every month – a process that requires the consideration of government regulations and medical workforce demands; consequently, such a manual scheduling method is time- and labor-intensive. The MSSP has been shown to be a nondeterministic polynomial-time hard (NP-hard) problem [23]. Studies worldwide have investigated medical staff scheduling. The current study develops three three-phase modified bat algorithms (BAs), named BA1, BA2, and BA3, to solve the MSSP involving various constraints, thereby creating a shift schedule that minimizes the dissatisfaction of medical staff’s preferences and provides hospital managers with a reference. In addition to investigating the preferences of medical personnel, this study statistically analyzes the workload of each medical worker in the shift schedule of each hospital sub-department. The preferences and workload are thus incorporated to form a much more satisfying shift schedule for the medical staff.

The remainder of this article is organized as follows. Section 2 reviews the literature on medical staff scheduling using metaheuristics and the BAs. Section 3 defines the research problem, the proposed mathematical model, and the modified BAs. Section 4 uses a case study to validate the proposed methodology described in Section 3. Finally, Section 5 concludes the paper and suggests future directions for research.

2. Literature review

2.1 Medical staff scheduling using metaheuristics

Distinct from the exact optimization methods, metaheuristics are a new type of solution approach inspired by the laws of nature and behaviors of animal communities [16, 24, 25]. For the NP-hard problems, when the problem size is large, the solving time when searching for an optimal solution increases exponentially [26]. As the MSSP has been proven to be an NP-hard problem [23], using the exact optimization methods to solve the large MSSP makes it difficult to obtain an optimal solution within a reasonable timeframe [24, 25]. Furthermore, related studies have shown that metaheuristics obtain a good or near-optimal solution of the MSSP within a reasonable timeframe [20, 27, 28, 29, 30, 31, 32, 33, 34]. Thus, researchers have applied different metaheuristics to solve the MSSPs [28, 31].

The literature on using metaheuristics to solve the MSSP is summarized as follows. Gutjahr and Rauner [27] verified the applicability of the ACO algorithm for solving the MSSP and confirmed the close relationship between the soft and hard hospital constraints and the shift schedule. Xiang et al. [33] showed that the modified ACO algorithm had better performance on the makespan, resources’ working time, individual maximum overtime, and nurses’ overtime than the schedule used in the case hospital. Tsai and Li [28] considered government and hospital regulations and medical personnel preferences by incorporating a two-phase mathematical model and an GA to solve the MSSP in another case hospital. Lin et al. [31] developed a novel preference satisfaction function to calculate the preference of each medical personnel based on the preferred work shifts and preferred days off by applied the GA. Todorovic and Petrovic [30] applied the Bee colony optimization algorithm to solve the MSSP in a case hospital in consideration of hospital regulations, nurse levels, and the restrictions on the nurse level and the number of personnel in each shift. Awadallah et al. [29] developed a hybrid artificial bee colony algorithm to the nurse rostering problem. Wong et al. [8] indicated that the mathematical model enabled the schedule to satisfy all the hard constraints and most of the soft constraints while shortening the scheduling time considerably. Michael et al. [32] considered five soft constraints in their medical staff model and used the competitive nurse roistering agent-based algorithm to search the minimal violations of medical personnel’s preferences. Zheng et al. [20] developed a randomized variable neighborhood search method to solve a nurse rostering problem. Moon [35] suggested that the efficient model of the hospital information system for nurse resource management could forecast optimum nurse resources based on the nursing intensity of the hospitalized patients. Yao et al. [36] used a bat algorithm to find the optimal referral between Hospitals with the unfixed daily patient referral policy.

2.2 Development and application of the BAs

Bats, the only mammals capable of powered flight, use a special echolocation principle to avoid obstacles and detect prey in the dark. Yang [37] simulated the relationship between bats’ preying behavior and optimization, thereby formulating the BAs. For the global search, each bat’s position and velocity are updated by using Eqs (1)–(3). For the local search, the position of each bat is updated by using Eq. (2.2), the loudness is reduced by using Eq. (5), and the pulse rate is increased by using Eq. (6).

$\displaystyle f_{i}^{t}=f_{\min}+(f_{\max}-f_{\min})\beta,\text{where\,}\beta% \in[0,1]$ (1) $\displaystyle v_{i}^{t}=v_{i}^{t-1}+(x_{i}^{t}-x_{\ast})\times f_{i}^{t}$ (2) $\displaystyle x_{i}^{t}=x_{i}^{t-1}+v_{i}^{t}$ (3) $\displaystyle x_{{\rm new}}=x_{{\rm old}}+\varepsilon A^{t},\text{where\,}% \varepsilon\in[-1,1],$ (4) $\displaystyle\text{and\,}A^{t}\text{\,is the average loudness of all bats at % the\,}t\text{\,iteration}$ $\displaystyle A_{i}^{t+1}=\alpha A_{i}^{t},\text{where\,}\alpha\in[0,1]$ (5) $\displaystyle r_{i}^{t+1}=r_{i}^{0}(1-\text{exp}^{-\gamma t}),\text{where\,}% \gamma\text{\,is a positive constant}$ (6)

BA surpassed the GA and particle swarm optimization approach (PSO) methods in terms of its solving time and efficiency [37]. Since its development, BA has been employed to solve optimization problems involving continuous variables effectively [38]. Sheng and Ye [39] recoded and initialized the BA according to the restrictions encountered in solving a discrete permutation flow-shop scheduling problem Meanwhile, Xu et al. [40] improved BA contained a new encoding method and added the crossover and mutation operations in order to increase the searching ability for a dual flexible job-shop scheduling problem. Li et al. [41] used the genetic mutation BA to solve a 0 and 1 knapsack problem according to the characteristics of the problem. Furthermore, Zhou et al. [42] designed a novel complex-valued encoding BA to solve the 0 and 1 knapsack problem. Osaba et al. [43] developed an improved discrete BA to solve the symmetric and asymmetric traveling salesman problems. Cai et al. [44] studied how to improve the optimal solution quality of the standard BA and developed two improved strategies: an optimal forage strategy and a random disturbance strategy. Yahya and Tokhi [45] studied a constrained optimization problem that included multiple constraints and found that violating a constraint could be transformed into adding a penalty for the objective function values by a developed modified adaptive bat sonar algorithm.

2.3 Summary

Based upon the literature reviewed, although there have been many successful applications of metaheuristics to solve the MSSP with multiple hard constraints, two issues have emerged. First, it usually takes time to find an initial solution without violating hard constraints, especially for multiple hard constraints of the MSSP. Second, when performing the local search of metaheuristics, it is easy to generate an infeasible solution due to the violation of hard constraints for each iteration; this requires a good repair/correction mechanism to make the schedule feasible. The current research deals with the two issues. The first issue is designing an initial solution to satisfy some of the hard constraints in Phase 1, which can avoid designing the corresponding correction mechanisms, thereby reducing repair/correction time. The second issue is designing shift schedule correction mechanisms applied in Phases 1 and 2 in order to repair the violation of hard constraints. Hence, a feasible schedule can be obtained. The detailed procedures of initializing a feasible schedule and making corrections for infeasible schedules are described in Section 3.2.

3. Methodology

3.1 Mathematical programming of the MSSP

This study considers a radiological technologist schedule in the case hospital. The director of the imaging center assigns 16 radiological technologists to support X-ray (X), portable X-ray (P), and computed tomography (CT) services. The notations, hard and soft constraints, and the objective function of the MSSP can be referred to [46, 47]. The mathematical model of the MSSP can be summarized as follows:

Medical staff scheduling problem (MSSP):

Minimize Eq. (27) in [46]

Subject to:

Equations (19)–(23) in [46] for hard constraints. Equations (24)–(26) in [46] for soft constraints.

The purpose of the developed modified three-phase BAs is to solve the MSSP, which means that the developed BAs need to satisfy all hard constraints while minimizing the violation of the weighted soft constraints, thereby improving medical staff’s satisfaction with their monthly schedule.

3.2 Solution procedures and corresponding pseudo code of the three-phase modified BAs

In this study, the three-phase modified BAs were developed to solve the MSSP. The modified BAs consisted of the initial shift schedule generation, the shift schedule correction, the shift schedule update, and the workload balance mechanisms. In Phase 1, an initial shift schedule satisfying some of the hard constraints was created; if an infeasible solution was obtained, the shift schedule would be corrected to satisfy all hard constraints. In Phase 2, the initial shift schedule was modified into a new shift schedule through the BAs’ global and local search mechanisms. If the new shift schedule was an infeasible solution, the shift schedule would be corrected to satisfy all hard constraints. Finally, the workload balance mechanism in Phase 3 was implemented to reduce the uneven workload among medical staff. Detailed procedures are introduced in the following paragraphs.

Solution procedures for minimization problems:

The detailed procedures are described as follows:

Phase 1:

1.
Initialize parameters: Before the modified BAs were executed, the initial position, initial velocity, initial pulse rate, initial loudness, maximal and minimal pulse frequency, and maximum number of iterations were established. The initial iteration was set to one. Each bat represented a monthly shift schedule for radiological technologists.
2.
Generate a random shift schedule: For each bat, a shift schedule with the number of total medical staff was required to be created. The shifts of all the medical personnel on the first day of the month were generated in random numbers in accordance with the labor demand for every shift of each sub-department in order to satisfy hard constraints, as shown in Eqs (19) and (20) in [46]. The shifts on the second day were generated in the same manner, and the process continued until the schedule for the entire month was complete. In other words, the shift schedule for all the medical personnel was created on a day-by-day basis rather than instantly for the entire month.
3.
Assess solution feasibility: The initial shift schedule was examined for any violation of the remaining hard constraints (i.e., violating at least one of Eqs (21)-(23) in [46]). If the schedule violated any hard constraint, then the corresponding shift schedule correction mechanism was incorporated. This procedure was repeated until the shift schedule of each worker in the solution of each bat had satisfied all hard constraints. Hence, Phase 1 ended.

After Phase 1 was complete, the initial feasible solutions (or the shift schedules) were obtained. The shift schedules that satisfied all the hard constraints from Phase 1 were used as the initial solutions in Phase 2 of the modified BAs.

Phase 2:

The detailed procedures are described as follows:

1.
Update the shift schedule: The bat movement in the BAs was enhanced to fit the questions in this study. The subsequently formulated updating method was applied to update the schedules through the use of the frequency and speed generated by each bat as the bat movement [37]. Figure 1 depicts an example of the movement schematic diagram. For example, the original eight-worker schedule is that Worker 1 takes the R1 shift and Worker 5 takes the R2 shift. If the four movements are calculated by the BA, the updated eight-worker schedule will be that Worker 1 takes the R2 shift (Worker 5’s shift $+$ 4 movements) and Worker 5 takes the R1 shift (Worker 1’s shift $+$ 4 movements).
2.
Assess whether the random number ( $r_{0}$ ) is larger than the pulse rate ( $r_{i}$ ): If $r_{0}>r_{i}$ , then go to the next step; otherwise, a new solution was randomly created, and go to Step 4.
3.
Generate an adjacent solution for local searches: The factors that affected the shift schedule were numerous and complex. To identify the improved solutions effectively in the nearby area, three adjacent-solution generation methods were proposed as three variants of the modified BAs. The merits of these three methods are to maintain the feasibility of Eqs (19) and (20) in [46]. The ranges of influence by these three methods varied; the comparison results are presented in Section 4. The three methods are as follows:

–
Generation Method 1 (BA1): Select one random day and two random workers to exchange their shifts. Figure 2 illustrates the shift schematic diagram, in which Day 2 was selected and the shifts of Worker 2 and Worker 6 were exchanged, thereby changing the shift of Worker 2 from P1 to P2 and that of Worker 6 from P2 to P1.
–
Generation Method 2 (BA2): Select one random day and one random worker as the referring point. Exchange the shift of the first worker with that of the last worker, that of the second worker with that of the second-to-last worker, etc. Figure 3 illustrates the shift schematic diagram, in which Day 3 and Worker 4 were selected as the referring point for executing the aforementioned shift exchange pattern until the referring point was reached or no more shifts could be exchanged.
–
Generation Method 3 (BA3): Select two random days and exchange the shifts of all personnel on these two days. Figure 4 illustrates the shift schematic diagram, in which the shifts on Day 4 are exchanged with those of Day 21. For Worker 1, Day 4 is changed from R1 to a day off while Day 21 is changed from a day off to R1. The shifts of the other workers were similarly changed.

4.
Assess solution feasibility: The current shift schedule was examined for any violation of the hard constraints(i.e., violating at least one of Eqs (21)-(23) in [46]). If the schedule violated these constraints, then the three correction mechanisms were executed; otherwise, go to the next step.
5.
Assess whether the random number ( $r_{0}$ ) is smaller than the loudness ( $A_{i}$ ) and whether the new solution is smaller than the current best solution: If $r_{0}<A_{i}$ and the new solution is smaller than the current best solution, then the current best solution was updated by the new solution. The pulse rate ( $r_{i}$ ) was increased and the loudness ( $A_{i}$ ) was decreased. Otherwise, the bats were sorted by the objective function value; if the current best solution is larger than the solution with the minimal objective function value, the current best solution was updated by the solution with the minimal objective function value.
6.
Assess whether the maximum number of iterations was achieved: If the current iteration reached the maximum number of iterations, go to Phase 3; otherwise, go to Step 1 of Phase 2.

Figure 1.
Example of updating the shift movement.

Figure 2.
Schematic diagram of Adjacent Solution Generation Method 1 (BA1).

Figure 3.
Schematic diagram of Adjacent Solution Generation Method 2 (BA2).

Figure 4.
Schematic diagram of Adjacent Solution Generation Method 3 (BA3).

Phase 3:

The detailed procedures are described as follows:

Workload balance mechanism:

After the best shift schedule was created using the three variants of the modified BAs, the shift workload of each worker in this month was calculated according to the shifts in the schedule. Because the objective function value was determined in advance, only the same shifts of the same day were exchanged in order to adhere to all the hard constraints. The workload in the studied emergency radiology sub-departments could not be directly compared with each another due to qualitatively different required duties. Calculating the workload involved analyzing the radiology patient data from the past four months with respect to the number of patients in each shift of each sub-department. The consistency of the total patient ratio in each shift of each sub-department with the monthly ratio was verified. Thus, the workload was determined using the total patient ratio.

The workload balance mechanism was applied to reduce the standard deviation of the shift workload of each worker. Figure 5 shows the schematic diagram of the workload balance mechanism, in which Worker 5 has Shift R2 with a workload of 6 on Day 5. The shift of Worker 5 could only be exchanged with that of another worker on the same shift (i.e., Shift 2). Worker 2 has Shift P2 with a workload of 4.5, and Worker 6 has Shift C2 with a workload of 6.5. Because the shift workload and shift weight of Worker 5 were larger than those of Worker 2, the two shifts were exchanged, thereby reducing Worker 5’s workload.

Figure 5.
Schematic diagram of the workload balance mechanism.

Shift schedule correction mechanism:

For the shift schedule correction mechanism, a correction mechanism was formulated in the problem-solving process to make every shift schedule solution feasible. The correction processes for adhering to the hard constraints – repairing any violation of Eqs (21)-(23) in [46] – were as follows:

If an infeasible solution needs to be repaired, a repairing procedure will be performed by one of Correction Mechanisms 1, 2, and 3. The repairing procedure goes repeating until the repaired solution satisfies Eqs (21)-(23) in [46].
Figure 6.
Example of Correction Mechanism 1.

Figure 7.
Example of Correction Mechanism 2.

Correction Mechanism 1 (Fig. 6): No worker was allowed more than four consecutive days off for Eq. (21) in [46]. The correction steps are described in the following:

Step a:
The total number of consecutive days off provided to each worker was calculated.
Step b:
For each worker, if the total number of consecutive days was more than four, then the following procedure was executed. For those workers whose schedules violated Eq. (21) in [46], a random off-duty day from the schedule was exchanged for the working day from another worker on the same day to satisfy Eq. (21) in [46]. The number using Correction Mechanism 1 increased by one.
Step c:
The total number of consecutive days off provided to each worker was recalculated.
Step d:
If the schedules of all the workers satisfied Eq. (21) in [46], the correction was complete; otherwise, Step b was repeated.

Correction Mechanism 2 (Fig. 7): Each worker was required to take at least one day off in every seven-day period for Eq. (22) in [46]. The correction steps are described in the following:

Step a:
The total number of consecutive working days assigned to each worker in the schedule was calculated.
Step b:
For each worker, if the total number of consecutive working days was equal to or greater than seven, then the following procedure was executed. For those workers whose schedules violated Eq. (22) in [46], a random working day from the schedule was exchanged for the day off of another worker on the same day to satisfy Eq. (22) in [46]. The number using Correction Mechanism 2 increased by one.
Step c:
The total number of consecutive working days assigned to each worker in the schedule was recalculated.
Step d:
If the schedules of all the workers satisfied Eq. (22) in [46], the correction was complete; otherwise, Step b was repeated.

Correction Mechanism 3 (Fig. 8): Workers could not take shift $j$ on one day and then take shift $i$ on the following day for Eq. (23) in [46], where $i$ and $j\in\{1,2,3\}$ and $i<j$ . The correction steps are described in the following:

Step a:
The shifts of each worker after the shift $j$ were examined for the presence of shift $i$ , where $i$ and $j\in\{1,2,3\}$ and $i<j$ .
Step b:
If any such shift was present, which means violating Eq. (23) in [46], then the following procedure was executed. For those workers whose schedules violated Eq. (23) in [46], their shifts on the previous day were exchanged with those of the other workers assigned with the same sub-department shifts on the previous day. The number using Correction Mechanism 3 increased by one.
Step c:
The shifts of each worker after the shift $j$ were reexamined for the presence of shift $i$ , where $i$ and $j\in\{1,2,3\}$ and $i<j$ .
Step d:
If the schedules of all the workers satisfied Eq. (23) in [46], the correction was complete; otherwise, Step b was repeated.

Figure 8.
Example of Correction Mechanism 3.

4. Results and discussions

Section 4.1 introduces the background of the case hospital, the imaging center, and radiological technologists. Section 4.2 introduces the weight calculation for the corresponding soft constraints based on the radiological technologists’ preferences, which were analyzed using an analytic hierarchy process (AHP) questionnaire. Section 4.3 presents the workload calculation for each shift of each sub-department based on the case hospital’s data. Section 4.4 describes the parameter settings of the modified BAs. Section 4.5 analyzes the results of the BA1, BA2, BA3, and PSO. Finally, Section 4.6 discusses the managerial implications of this study.

4.1 Background of the case hospital and imaging center

The case hospital has 1,278 beds and four departments: Internal Medicine, Surgery, Obstetrics and Gynecology & Pediatrics, and Other departments (Chinese Medicine, Dentistry, Emergency Medicine, Radiation Oncology, Radiology, Outpatient Services, etc.). In the Department of Radiology, the director of the case imaging center is responsible for X-ray, portable X-ray, CT, magnetic resonance imaging (MRI), and ultrasound services.

The emergency radiological technologist team requires 3 shifts a day and 7 days a week, making it the most difficult shifts to schedule due to the worker size, shift regulations, and workers’ preferences. Hence, this study focuses on the 16 radiological technologists who work for the emergency radiological technologist team, including X-ray, portable X-ray, and CT services. Based on past experiences for scheduling shifts, the director identified radiological technologists’ useful preferences – namely, three unsatisfied working shift patterns, such as working for two different shifts on consecutive days, working the off-working shift-off pattern, and working the working shift-off-working shift pattern. Therefore, this study formulates these three unsatisfied working shift patterns as soft constraints, as presented in Eqs (24)–(26) in [46], respectively.

4.2 Hierarchical analysis weightings

In light of the constraints on the MSSP and the discussions with the director of the case imaging center, an AHP [48, 49] questionnaire on the weights for the soft constraints was designed to measure the importance of these soft constraints to the medical staff.

Based on the results of the questionnaires for investigating the radiological technologists’ preferences, the AHP method was applied to generate the corresponding weights for the soft constraints, as listed in Table 1. The AHP method are detailed in the references [18, 48, 49]. The weights for the soft constraints were used as the weights for the objective function in Eq. (27) in [46] to ensure the generated shift schedule satisfied not only government and hospital regulations, but also most of the preferences of the medical staff.

Table 1
Weights for the soft constraints

Soft constraints	Weight
Each worker does not take shift 2 the day after taking shift 1 (24-1) in [46]	0.055
Each worker does not take shift 3 the day after taking shift 1 (24-2) in [46]	0.050
Each worker does not take shift 3 the day after taking shift 2 (24-3) in [46]	0.046
An “off-shift 1-off” order does not appear in a worker’s shift schedule (25-1) in [46]	0.170
An “off-shift 2-off” order does not appear in a worker’s shift schedule (25-2) in [46]	0.153
An “off-shift 3-off” order does not appear in a worker’s shift schedule (25-3) in [46]	0.269
An “shift 3-off-shift 1” order does not appear in a worker’s shift schedule (26) in [46]	0.257

4.3 Workload calculation

This research collected the data of daily patients who required physical examinations in the case imaging center for four months. Table 2 lists the numbers of patients for each shift of each sub-department in the case imaging center. The total number of patients in sub-department $P$ was 2,188, 2,121, and 4,445 for Shift 1, Shift 2, and Shift 3, respectively. These data were used in Eq. (7) to obtain the workload rounded to the nearest hundredth, which was 0.25, 0.24, and 0.51 for Shift 1, Shift 2, and Shift 3, respectively. The same calculation method was applied for the other two sub-departments, as shown in Table 3.

$\displaystyle\text{Workload for shift\,}s\text{\,of sub-deparment\,}r=\frac{% \text{Patients served in shift\,}s\text{\,of sub-department\,}r}{\sum\limits_{r}{\text{% Patients served in shift\,}s\text{\,of sub-department\,}r}}$ (7) $\displaystyle\text{Workload for shift 3 of sub-deparment\,}P=\frac{4,445{\rm}}% {(2,188+2,121+4,445)}=0.51$

Table 2

Number of patients in each shift of each sub-department

[height=0.8cm,width=4cm]ShiftSub-department	$P$	$C$	$R$
Shift 1	2,188	2,585	12,071
Shift 2	2,121	2,234	12,666
Shift 3	4,445	1,009	5,812

Table 3

Workload for each shift of each sub-department

[height=0.8cm,width=4cm]ShiftSub-department	$P$	$C$	$R$
Shift 1	0.25	0.45	0.40
Shift 2	0.24	0.38	0.41
Shift 3	0.51	0.17	0.19

The data collected indicated that the number of patients in each shift of each sub-department varied day by day, thereby causing fluctuations in the radiological technologists’ workload. In this study, the workload of medical staff in each shift of each sub-department was calculated using the average number of patients. In practice, medical staff’s workload may be quite different between weekdays and weekends in some medical departments. Integrating the varied workloads into the MSSP to generate a more balanced workload schedule becomes a challenging issue. Hence, researchers may consider the workload factor for future medical staff scheduling research in order to equalize the workload balance among medical staff.

4.4 Parameter settings of the modified BAs

This research used an Intel(R) Core(TM) i7–6700 CPU 3.40 GHz, DDR3 8GB, and Microsoft Windows 7 computer. The three-phase modified BAs (i.e., BA1, BA2, and BA3) applied in this study were devised using the Hypertext Preprocessor (PHP). Before applying the proposed method, the parameters that affect the mechanisms in the modified BAs must be determined. Yang [37] indicated that selecting parameters requires testing them according to the characteristics of the problem. For the BA, eight parameters ( $f_{\max}$ , $f_{\min}$ , $\beta$ , $\varepsilon$ , $\alpha$ , $\gamma$ , $r_{0}$ , $A_{0}$ ) in Eqs (1)–(6) had to be initialized. Generally, the parameters of the BA in the literature [40, 42, 43, 44] are summarized as follows: ( $f_{\min}$ , $f_{\max}$ ) is between 0 and a given constant; $\beta$ is randomly generated between 0 and 1; $\varepsilon$ is randomly generated between $-$ 1 and 1; $\alpha$ is a constant between 0 and 1; $\gamma$ is a constant between 0 and 1; the initial loudness ( $A_{0}$ ) of a bat ranges from 0 to 1; and its initial pulse rate ( $r_{0}$ ) is between 0 and 1. In this study, ( $f_{\min}$ , $f_{\max}$ ) was set to (0, 30), where 30 is the number of days in a month; $\beta$ was set to a uniform (0, 1); and $\varepsilon$ was set to a uniform ( $-$ 1, 1). This study tested different BAs’ parameter settings, which included two levels (0.9, 0.9) and (0.99, 0.99) of ( $\alpha,\gamma$ ), three levels (0.2, 0.5, and 0.9) of $r_{0}$ , and three levels (0.2, 0.5, 0.9) of $A_{0}$ in order to determine the appropriate BAs’ parameter setting for ( $\alpha$ , $\gamma$ , $r_{0}$ , $A_{0}$ ) for the BA1, BA2, and BA3. There were a total of 2 * 3 * 3 $=$ 18 parameter settings, and each parameter setting was run for 20 replications for the BA1, BA2, and BA3. Based on the 20 replications, the results in Table 4 showed the parameter setting, ( $\alpha$ , $\gamma$ , $r_{0}$ , $A_{0}$ ) $=$ (0.99, 0.99, 0.2, 0.9) and generated the average minimal objective function value in Phase 3, which was 7.83, 6.86, and 6.49 for the BA1, BA2, and BA3, respectively. Therefore, this study adapted the parameter setting ( $\alpha$ , $\gamma$ , $r_{0}$ , $A_{0}$ ) $=$ (0.99, 0.99, 0.2, 0.9) for the remaining analyses of the BAs.

Table 4
After Phase 3, results of 18 ( $\alpha$ , $\gamma$ , $r_{0}$ , $A_{0}$ ) parameter settings of BA1, BA2, and BA3

No.	Parameter setting	BA1		BA2		BA3
	( $\alpha$ , $\gamma$ , $r_{0}$ , $A_{0}$ )	Average objective function value	Solving time (s)	Average objective function value	Solving time (s)	Average objective function value	Solving time (s)
1	(0.9, 0.9, 0.2, 0.2)	11.89	56.05	11.92	55.00	12.23	55.45
2	(0.9, 0.9, 0.2, 0.5)	10.38	55.05	10.20	55.05	10.28	53.85
3	(0.9, 0.9, 0.2, 0.9)	9.61	55.90	9.47	53.95	9.34	53.90
4	(0.9, 0.9, 0.5, 0.2)	12.96	111.50	12.89	111.85	12.85	111.80
5	(0.9, 0.9, 0.5, 0.5)	11.34	111.07	11.27	113.17	11.19	113.37
6	(0.9, 0.9, 0.5, 0.9)	10.46	111.65	10.34	110.25	10.16	111.55
7	(0.9, 0.9, 0.9, 0.2)	14.45	186.05	14.51	183.55	14.55	185.85
8	(0.9, 0.9, 0.9, 0.5)	13.05	186.10	13.14	186.40	13.19	187.30
9	(0.9, 0.9, 0.9, 0.9)	12.43	188.85	12.25	189.35	12.39	187.60
10	(0.99, 0.99, 0.2, 0.2)	11.29	55.95	10.47	54.80	10.65	55.20
11	(0.99, 0.99, 0.2, 0.5)	8.72	56.15	8.32	55.15	7.70	54.10
12	(0.99, 0.99, 0.2, 0.9)	7.83	56.25	6.86	54.30	6.49	53.95
13	(0.99, 0.99, 0.5, 0.2)	11.81	112.65	11.78	112.10	11.25	110.35
14	(0.99, 0.99, 0.5, 0.5)	9.82	110.25	9.33	110.75	9.27	109.65
15	(0.99, 0.99, 0.5, 0.9)	8.61	112.45	7.96	112.15	7.74	112.70
16	(0.99, 0.99, 0.9, 0.2)	13.76	187.40	14.01	187.35	14.21	189.05
17	(0.99, 0.99, 0.9, 0.5)	12.84	189.45	12.30	190.10	12.40	188.30
18	(0.99, 0.99, 0.9, 0.9)	11.69	189.30	11.61	190.40	11.46	189.10

Note: Bold means the minimal value of the average minimal objective function value of the 18 parameter settings for each BA.

For the modified BAs, the number of bats is closely related to the maximum number of iterations. A higher number of bats increases a chance to achieve the convergence of the objective function value. The 1,001-iteration test was performed 10 times for BA1, BA2, and BA3. As the maximum number of iterations of each individual trail reached about 900 iterations in Fig. 9a–c, the convergence of the objective function value in the modified BAs was achieved. Therefore, to achieve the convergence, the maximum number of iterations was set at 1,000.

Figure 9.

a. Curve diagram of the maximum number of iterations for BA1. b. Curve diagram of the maximum number of iterations for BA2. c. Curve diagram of the maximum number of iterations for BA3.

When the number of bats increases, more satisfactory (or smaller) solutions may be obtained, but the solving time may be prolonged. In order to determine an appropriate number of bats, this study conducted 10 parameter settings, from 1 to 10 bats, each of which underwent 20 replications. The results showed that, when the number of bats for the BA1 increased from 1 to 5, the average objective function value decreased, thereby generating a better solution; when the number of bats for the BA1 increased from 5 to 10, the average objective function value decreased slightly. For the solving time, the results in Table 5 showed that, when the number of bats for the BA1 increased from 1 to 10, the solving time increased. Similarly, the same findings were obtained for the BA2 and BA3. Therefore, the number of bats for the BA1, BA2, and BA3 in this study was determined to be five.

Table 5

After Phase 3, results of varying numbers of bats, from 1 to 10, adapted in the BA1, BA2, and BA3

No.	Parameter setting	BA1		BA2		BA3
	Number of bats	Average objective function value	Solving time (s)	Average objective function value	Solving time (s)	Average objective function value	Solving time (s)
1	1	7.03	34.55	5.72	33.60	5.11	33.55
2	2	6.37	67.25	5.74	66.30	4.71	66.30
3	3	6.34	101.35	5.37	100.50	4.80	98.60
4	4	6.07	133.75	5.19	132.70	4.58	130.65
5	5	6.00	167.80	4.93	165.50	4.43	164.85
6	6	6.00	200.30	4.86	201.45	4.44	196.35
7	7	6.00	235.10	4.80	236.26	4.45	234.55
8	8	5.86	270.65	4.91	271.40	4.66	238.20
9	9	5.82	300.55	4.94	303.90	4.32	299.30
10	10	5.75	339.85	4.79	338.45	4.31	334.05

4.5 Medical shift schedule solutions

For easier use and viewing of the schedule, a program interface was designed to enable the user to select the year, month, and number of radiological technologists for scheduling in a schedule, as well as the number of bats and maximum number of iterations. After the parameters are set for the 9 to 10 medical worker scenario, the user can click on the modified BA solution button (i.e., BA3 Run). Once the problem-solving process is complete, the best shift schedule obtained is obtained. After Phase 2 ended, before the workload balance mechanism was performed, the minimum workload for the shifts was 4.99 and the maximum workload of the shifts was 8.22; after the workload balance mechanism was performed in Phase 3, the minimum workload was 5 and the maximum workload was 7.65. Before and after the workload balance mechanism, the mean workload of the 16 workers in the entire month was 6.22; however, the standard deviation of the weights was 0.93 and 0.46 before and after the workload balance mechanism, respectively.

For the same 9 to 10 medical worker scenario, the testing instance was run for 20 replications using the same parameters to verify the stability of the workload balance mechanism for the BA1, BA2, and BA3. Table 6 shows the results of the three variants of the modified BAs after performing the procedures in Phases 1, 2, and 3. The results of the BA1 in Table 6 revealed that, when the objective function values remained, the average standard deviation of each medical worker was 0.95 and 0.45 before and after the workload balance mechanism, respectively, constituting a standard deviation reduction of up to 53%. The results of the BA2 in Table 6 revealed that, when the objective function values remained, the average standard deviation of each medical worker was 0.94 and 0.46 before and after the workload balance mechanism, respectively, constituting a standard deviation reduction of up to 51%. The results of the BA3 in Table 6 revealed that, when the objective function values remained, the average standard deviation of each medical worker was 0.99 and 0.48 before and after the workload balance mechanism, respectively, constituting a standard deviation reduction of up to 52%. Therefore, the workload balance mechanism applied in the BA1, BA2, and BA3 of this study effectively reduced the workload differences among the medical personnel.

Furthermore, in Table 6, BA3 had the smallest average objective function value, and all three BA variants could be executed within 150 seconds. Since the means of BA1 and BA2 failed to the normality test, the Mann-Whitney $U-$ tests were used. In order to determine the best BA variant, three Mann-Whitney $U$ -tests were performed on the three variants of the modified BAs, with $\alpha=$ 0.05 (H ${}_{0}$ : $\eta_{BA1}-\eta_{BA2}=$ 0, indicating that no differences existed between the two variants; H ${}_{1:}\eta_{BA1}-\eta_{BA2}\neq$ 0, indicating that significant differences existed between the two variants). Based on the results in Table 7, when the BA1 and BA2 were compared to each other, $p=$ 0 (reject H ${}_{0}$ ), indicating that significant differences existed between the BA1 and BA2 on their average objective function values. The 95% conference interval of ( $\eta_{BA1}-\eta_{BA2}$ ) was positive, which meant that the objective function value of the BA1 was larger than that of the BA2. This meant that, for minimizing the MSSP, the BA2 outperformed the BA1. Similarly, when the BA1 and BA3 as well as BA2 and BA3 were compared with each other, $p=$ 0 (reject H ${}_{0}$ ), indicating that significant differences existed between the BA1 and BA3 as well as the BA2 and BA3 on their average objective function values. In addition, the 95% conference interval of ( $\eta_{BA1}-\eta_{BA3}$ ) and ( $\eta_{BA2}-\eta_{BA3}$ ) was positive, meaning that the objective function value of the BA1 and BA2 was larger than that of the BA3. Thus, to minimize the MSSP, the BA3 outperformed the BA1 and BA2. As the BA3 had the smallest average objective function value, the BA3 was selected as the method for solving the MSSP. The possible reason for this finding was that the BA3 had a larger chance to search more solution space than the other BAs, which implied that a better local search should merit future research.

In order to analyze the three correction mechanisms, the results in Table 8 showed that, for the same 9 to 10 medical worker scenario with 20 replications, the average number of Correction Mechanism 1 performed in Phases 1 and 2 was 4,543, 4,140, and 3,955 times for BA1, BA2, and BA3, respectively, in order to repair the violation of Eq. (21) in [46]. The average number of Correction Mechanism 2 performed in Phases 1 and 2 was 80,560, 78,016, and 78,814 times for BA1, BA2, and BA3, respectively, in order to repair the violation of Eq. (22) in [46]. Finally, the average number of Correction Mechanism 3 performed in Phases 1 and 2 was 1,532,230, 1,487,982, and 1,482,923 times for BA1, BA2, and BA3,

Table 6
Solutions and solving time of BA1, BA2, and BA3 after Phase 3

No.	BA1				BA2				BA3
	Average obj. fun. value	Solving time (s)	Std of workload in Phase 2	Std of workload in Phase 3	Average obj. fun. value	Solving time (s)	Std of workload in Phase 2	Std of workload in Phase 3	Average obj. fun. value	Solving time (s)	Std of workload in Phase 2	Std of workload in Phase 3
1	6.50	140	0.58	0.37	5.16	145	1.08	0.47	4.42	151	0.72	0.44
2	5.54	141	0.86	0.67	5.26	140	1.05	0.46	4.26	152	0.94	0.40
3	6.23	139	1.03	0.38	5.05	147	0.68	0.46	5.19	148	1.10	0.44
4	5.99	138	0.77	0.39	5.28	141	1.10	0.46	4.65	149	1.05	0.66
5	4.98	143	1.01	0.45	4.99	150	1.00	0.67	5.43	141	1.25	0.56
6	6.31	141	0.87	0.39	5.40	145	0.78	0.34	5.23	146	1.08	0.47
7	5.91	140	1.22	0.48	5.04	141	1.14	0.53	4.56	144	0.83	0.37
8	5.95	139	1.07	0.34	5.02	141	1.27	0.46	4.25	146	1.13	0.49
9	5.91	147	0.89	0.41	4.92	142	0.77	0.35	4.29	143	0.93	0.40
10	5.11	142	1.06	0.45	5.05	140	0.79	0.28	4.74	149	0.98	0.60
11	6.54	142	1.28	0.50	5.09	143	0.93	0.42	4.51	148	1.10	0.34
12	5.05	145	1.04	0.53	5.31	139	0.92	0.40	4.34	147	1.15	0.49
13	6.45	141	0.86	0.43	5.81	145	1.08	0.40	4.55	140	0.79	0.61
14	6.28	142	0.86	0.43	5.59	142	0.87	0.30	4.62	143	1.13	0.49
15	5.98	139	0.95	0.48	5.21	142	0.42	0.39	4.93	149	0.72	0.55
16	6.54	142	0.72	0.42	5.01	148	1.13	0.66	4.89	147	1.00	0.47
17	6.26	139	0.95	0.41	5.80	139	0.99	0.40	5.14	147	0.85	0.42
18	6.46	147	0.92	0.33	5.34	147	0.90	0.52	4.60	146	0.92	0.49
19	6.34	146	0.99	0.68	5.63	146	1.01	0.71	5.23	147	1.04	0.36
20	6.09	139	1.16	0.52	5.06	141	0.90	0.45	4.70	149	1.01	0.51
Average	6.02	141.60	0.95	0.45	5.25	143.20	0.94	0.46	4.73	146.60	0.99	0.48
Std	0.49	2.76	0.16	0.09	0.27	3.21	0.20	0.10	0.36	3.12	0.14	0.08

Note: Std represents standard deviation.

Table 7

Comparisons of the average objective function values of BA1, BA2, and BA3 after Phase 3 by the Mann-Whitney $U$ -tests

Average objective function values	95% confidence interval	$W$ value
H ${}_{0}$ : $\eta_{BA1}-\eta_{BA2}=$ 0	[0.6301, 1.1001]	562.0
H ${}_{0}$ : $\eta_{BA1}-\eta_{BA3}=$ 0	[1.0699, 1.6601]	595.0
H ${}_{0}$ : $\eta_{BA2}-\eta_{BA3}=$ 0	[0.3600, 0.7400]	552.0

Table 8

Average number of corrections and updates performed in different phases of the BA1, BA2, and BA3

Variant of BAs	Average number of correction mechanism 1 performed in Phases 1 and 2	Average number of correction mechanism 2 performed in Phases 1 and 2	Average number of correction mechanism 3 performed in Phases 1 and 2	Average number of updating workers’ workload performed in Phase 3
BA1	4,543	80,560	1,532,230	112,331.85
BA2	4,140	78,016	1,487,982	116,740.90
BA3	3,955	78,814	1,482,923	115,545.25

respectively, in order to repair the violation of Eq. (23) in [46]. The results showed that Correction Mechanism 3 required being performed more times to repair Eq. (23) in [46], which included three sub-constraints: workers must not take shift 1 the day after taking shift 2, workers must not take shift 1 the day after taking shift 3, and workers must not take shift 2 the day after taking shift 3. Furthermore, these results implied that, if a better correction mechanism can be developed to repair the violation of Eq. (23) in [46], the solving time may be reduced proportionally due to the reduction of the number of times the developed correction mechanism was performed.

In order to test the robustness of the BA1, BA2, and BA3, the authors conducted two scenarios, involving 9 to 10 and 11 to 12 medical workers, and compared results to the PSO method. The PSO method consisted of the same parameters, such as five particles and the maximum iteration $=$ 1,000, and the same three correction mechanisms and workload balance mechanism compared to the BA1, BA2, and BA3. Each scenario consisted of 10 testing instances, which required 9 to 10 or 11 to 12 medical workers for each day. Each testing instance ran 20 replications to calculate the average objective function values and the average solving time. Table 9 shows that, in the 9 to 10 medical worker scenario, the average objective function values of the BA1 were between 5.44 and 6.33 while the standard deviation of the objective function values ranged between 0.33 and 0.58; the average objective function values of the BA2 were between 4.60 and 5.20 while the standard deviation of the objective function values ranged between 0.28 and 0.53; and the average objective function values of the BA3 were between 4.09 and 4.69 while the standard deviation of the objective function values ranged between 0.21 and 0.58. The results indicated that, for the BA1, BA2, and BA3, the average objective function value and the standard deviation objective function value fell in a small range of values, meaning the BA1, BA2, and BA3 were robust.

Table 9

Comparisons of the average objective function values and solving time of the BA1, BA2, BA3, and PSO in the 9 to 10 medical worker scenario

	BA1			BA2			BA3			PSO
Testing instances	Average obj. fun. value	Std of obj. fun. value	Solving time (s)	Average obj. fun. value	Std of obj. fun. value	Solving time (s)	Average obj. fun. value	Std of obj. fun. value	Solving time (s)	Average obj. fun. value	Std of obj. fun. value	Solving time (s)
1	5.94	0.48	150.65	5.00	0.37	157.70	4.43	0.34	155.50	14.72	0.43	99.25
2	5.89	0.37	145.20	4.88	0.41	151.25	4.11	0.58	158.90	14.09	0.44	91.60
3	6.02	0.36	163.20	5.02	0.39	167.15	4.69	0.41	165.65	14.97	0.35	99.65
4	5.73	0.33	139.35	4.81	0.47	146.40	4.10	0.39	141.15	14.02	0.68	91.90
5	6.33	0.44	159.00	5.16	0.53	165.15	4.68	0.55	156.35	14.49	0.69	97.70
6	6.13	0.42	161.65	5.16	0.40	168.75	4.68	0.43	159.35	14.78	0.34	97.85
7	5.69	0.38	151.00	4.60	0.49	160.30	4.49	0.40	149.70	13.89	0.58	92.60
8	6.19	0.58	152.45	5.20	0.40	143.05	4.64	0.35	148.80	14.76	0.63	98.60
9	5.44	0.46	132.85	4.65	0.30	125.20	4.14	0.21	128.50	13.78	0.48	91.85
10	5.61	0.49	137.80	4.70	0.28	130.30	4.09	0.48	136.35	14.76	0.46	99.15

Table 10

Comparisons of the average objective function values of BA1, BA2, BA3, and PSO by the Mann-Whitney $U$ -tests in the 9 to 10 medical worker scenario

Average objective function values	95% confidence interval	$W$ value	$p$ value
H ${}_{0}$ : $\eta_{BA1}-\eta_{BA2}=$ 0	[0.7300, 1.2399]	155.0	0.0002
H ${}_{0}$ : $\eta_{BA1}-\eta_{BA3}=$ 0	[1.2101, 1.7901]	155.0	0.0002
H ${}_{0}$ : $\eta_{BA1}-\eta_{PSO}=$ 0	[ $-$ 8.950, $-$ 8.130]	55.0	0.0002
H ${}_{0}$ : $\eta_{BA2}-\eta_{BA3}=$ 0	[0.2199, 0.7702]	148.0	0.0013
H ${}_{0}$ : $\eta_{BA2}-\eta_{\textit{PSO}}=$ 0	[ $-$ 9.900, $-$ 9.080]	55.0	0.0002
H ${}_{0}$ : $\eta_{BA3}-\eta_{\textit{PSO}}=$ 0	[ $-$ 10.390, $-$ 9.640]	55.0	0.0002

Since the mean of BA3 did not pass the normality test, the Mann-Whitney $U$ -tests were used. Based on the Mann-Whitney $U$ -tests among the BA1, BA2, BA3, and PSO, the results in Table 10 showed that, for the average objective function values, the ranking was the BA3, followed by the BA2, the BA1, and the PSO from smallest to largest. This indicated that the BA3 outperformed the other three algorithms. Furthermore, the results in Table 9 showed that the PSO had the smallest solving time among the four algorithms.

In the 11 to 12 medical worker scenario, Table 11 shows that the average objective function values of the BA1 were between 5.72 and 7.74 while the standard deviation of the objective function values ranged between 0.45 and 0.70; the average objective function values of the BA2 were between 5.28 and 6.07 while the standard deviation of the objective function values ranged between 0.38 and 0.64; and the average objective function values of the BA3 were between 4.72 and 5.59 while the standard deviation of the objective function values ranged between 0.39 and 0.60. The results indicated that, for the BA1, BA2, and BA3, the average objective function value and the standard deviation objective function value fell in a small range of values. This meant that the BA1, BA2, and BA3 were robust.

Table 11

Comparisons of the average objective function values and solving time of the BA1, BA2, BA3, and PSO in the 11 to 12 medical worker scenario

1	7.40	0.51	445.45	5.87	0.61	452.50	5.41	0.60	459.40	13.11	0.37	248.95
	BA1			BA2			BA3			PSO
Testing instances	Average obj. fun. value	Std of obj. fun. value	Solving time (s)	Average obj. fun. value	Std of obj. fun. value	Solving time (s)	Average obj. fun. value	Std of obj. fun. value	Solving time (s)	Average obj. fun. value	Std of obj. fun. value	Solving time (s)
2	7.46	0.52	705.05	5.46	0.63	704.05	5.31	0.58	697.50	12.07	0.59	368.75
3	7.53	0.45	734.50	6.01	0.47	737.35	5.59	0.49	737.45	12.56	0.69	385.90
4	7.13	0.56	678.45	5.47	0.64	671.60	5.15	0.39	684.65	12.09	0.66	372.85
5	7.74	0.68	945.30	6.07	0.38	962.15	5.37	0.57	904.65	12.20	0.47	495.50
6	7.26	0.67	1,215.84	5.98	0.45	1182.65	5.39	0.51	1230.40	12.12	0.51	618.55
7	5.72	0.57	726.30	5.66	0.50	682.05	4.79	0.45	714.95	11.95	0.55	381.55
8	7.55	0.70	574.30	5.76	0.53	591.55	5.26	0.44	588.75	12.78	0.50	316.95
9	6.92	0.58	522.60	5.52	0.44	538.30	4.81	0.42	538.90	12.10	0.65	286.50
10	6.43	0.65	445.15	5.28	0.44	453.60	4.72	0.50	449.70	12.92	0.56	247.70

Since the mean of PSO did not pass the normality test, the Mann-Whitney $U$ -tests were used. Based on the Mann-Whitney $U$ -tests among the BA1, BA2, BA3, and PSO, the results in Table 12 showed that, for the average objective function values, the ranking was, from smallest to largest, the BA3, followed by the BA2, the BA1, and the PSO. This indicated that the BA3 outperformed the other three algorithms. Furthermore, the results in Table 11 showed that the PSO had the smallest solving time among the four algorithms. Therefore, based on the two scenarios, the results indicated that the BA3 had the better average objective function value, but the PSO had the smaller solving time.

Table 12

Comparisons of the average objective function values of BA1, BA2, BA3, and PSO by the Mann-Whitney $U$ -tests in the 11 to 12 medical worker scenario

Average objective function values	95% confidence interval	$W$ value	$p$ value
H ${}_{0}$ : $\eta_{BA1}-\eta_{BA2}=$ 0	[1.0601, 1.8801]	150.0	0.0008
H ${}_{0}$ : $\eta_{BA1}-\eta_{BA3}=$ 0	[1.6202, 2.3802]	155.0	0.0002
H ${}_{0}$ : $\eta_{BA1}-\eta_{\textit{PSO}}=$ 0	[ $-$ 5.670, $-$ 4.670]	55.0	0.0002
H ${}_{0}$ : $\eta_{BA2}-\eta_{BA3}=$ 0	[0.2001, 0.7598]	147.0	0.0017
H ${}_{0}$ : $\eta_{BA2}-\eta_{\textit{PSO}}=$ 0	[ $-$ 7.050, $-$ 6.250]	55.0	0.0002
H ${}_{0}$ : $\eta_{BA3}-\eta_{\textit{PSO}}=$ 0	[ $-$ 7.530, $-$ 6.760]	55.0	0.0002

4.6 Management implications

In this study, a favorable mathematical model was provided, an interface enabling users to easily use and view the shift schedule was established, and the three variants of BAs were applied to solve the MSSP. Incorporating the modified BAs required discussing the current state of the case hospital with managers and understanding the challenges and scheduling requirements of the hospital. Thus, a reference was provided to the managers for the results following a change in future scheduling.

Three variants of the modified BAs were proposed in this study. Using the BA3 obtained more satisfactory solutions overall than did using either the BA2, BA3, or PSO while minimizing worker dissatisfaction with the shift schedule. Without compromising the average objective function value, the workload of the medical personnel was balanced. Thus, each worker received a more evenly distributed workload.

Regarding the medical personnel preference questionnaire, because each worker’s schedule preferences varied, an AHP as well as expert input was used to establish the critical and influential preference factors. In addition, the consistency of the factors was verified according to their hierarchical weightings, thereby ensuring that the factors were qualified for representing the experts’ mutual opinions. Thus, hospital managers could adjust the shift schedule according to the specified preferences of the medical personnel and ultimately shorten the scheduling time. However, overly high average objective function values must be avoided to reduce medical personnel’s dissatisfaction with the schedule.

5. Conclusions and future research

In this study, the original BA was adapted and three modified BAs with varying adjacent solution generation methods were developed. These new variants of BAs allowed for creating a shift schedule that satisfied the hard constraints arising from government and hospital regulations while preventing errors in manual scheduling. Applying the BA3 in the MSSP yielded a better shift schedule than the BA1, BA2, PSO and shortened the scheduling time considerably from the manual scheduling to computer scheduling based on the case imaging center’s schedule setting. The manual scheduling usually takes 1 to 2 days for the director of the imaging center to generate a monthly schedule. As part of the interview of the medical personnel in the case hospital, an AHP questionnaire was distributed to determine their schedule preferences and thereby establish soft constraints. The weighted values of the preferences were then calculated using the AHP. Thus, the weighted values were no longer scores derived intuitively and the shift schedule satisfied the preferences of the medical personnel more favorably and flexibly. In this study, medical personnel’s schedule preferences and their workload level were combined and solved consecutively to improve shift schedule fairness and flexibility. Currently, numerous medical facilities require incorporating systematic, consistent medical staff scheduling models like the one incorporated in this study. This model can reduce the time and resources required for manual scheduling not only in medical staff scheduling systems, but also in other types of weighted scheduling processes.

According to the challenges and limitations encountered in this study, three suggestions are proposed for future studies. First, workers with a large workload in one month may be provided with a decreased workload in the following month, thereby improving the fairness of the shift schedule. Second, the program logics, along with bat mechanisms and parameters, can be improved to obtain more desirable solutions. Third, as the workload balance issue becomes more and more important for workers in practice, researchers should integrate the workload balance into the objective function in their future research. In this way, the results will generate an optimal schedule with a less standard deviation of the workload among workers, thereby generating a more balanced workload schedule for workers.

Footnotes

Acknowledgments

This research is supported by the Ministry of Science and Technology – Taiwan, R.O.C under contract no. MOST 109-2221-E-033-028.

Conflict of interest

None to report.

References

Ang

Lam

SWS

Pasupathy

Ong

MEH

. Nurse workforce scheduling in the emergency department: a sequential decision support system considering multiple objectives. J Nurs Manage. 2018; 26(4): 432-441.

Liu

Xie

. Physician staffing for emergency departments with time-varying demand. Informs J Comput. 2018; 30(3): 588-607.

Chen

Gabriel

Kodali

Urman

. Effect of anesthesia staffing ratio on first-case surgical start time. J Med Syst. 2016; 40(5): Article 115.

Wright

Bretthauer

. Strategies for addressing the nursing shortage: coordinated decision making and workforce flexibility. Decision Sci. 2010; 41(2): 373-401.

Lapointe

Bhesania

Tanner

Peruri

Mehta

. An innovative approach to improve communication and reduce physician stress and burnout in a university affiliated residency program. J Med Syst. 2018; 42(7): Article 117.

Puente

Gómez

Fernández

Priore

. Medical doctor rostering problem in a hospital emergency department by means of genetic algorithms. Comput Ind Eng. 2009; 56(4): 1232-1242.

Ganguly

Lawrence

Prather

. Emergency department staff planning to improve patient care and reduce costs. Decision Sci. 2014; 45(1): 115-145.

Wong

Chin

. A two-stage heuristic approach for nurse scheduling problem: a case study in an emergency department. Comput Oper Res. 2014; 51: 99-110.

Dexter

Epstein

. Influence of annual meetings of the American society of anesthesiologists and of large national surgical societies on caseloads of major therapeutic procedures. J Med Syst. 2018; 42(12): Article 259.

10.

Wutthisirisart

Martinez

Heaton

Pasupathy

Thompson

Sir

. Maximizing patient coverage through optimal allocation of residents and scribes to shifts in an emergency department. J Med Syst. 2018; 42(11): Article 212.

11.

De Bruecker

Van den Bergh

Beliën

Demeulemeester

. Workforce planning incorporating skills: state of the art. Eur J Oper Res. 2015; 243(1): 1-16.

12.

Ingels

Maenhout

. Optimised buffer allocation to construct stable personnel shift rosters. Omega-Int J Manage S. 2019; 82: 102-117.

13.

Defraeye

Van Nieuwenhuyse

. Staffing and scheduling under nonstationary demand for service: a literature review. Omega-Int J Manage S. 2016; 58: 4-25.

14.

Legrain

Bouarab

Lahrichi

. The nurse scheduling problem in real-life. J Med Syst. 2015; 39(1): Article 160.

15.

Ernst

Jiang

Krishnamoorthy

Sier

. Staff scheduling and rostering: a review of applications, methods and models. Eur J Oper Res. 2004; 153(1): 3-27.

16.

van den Bergh

Beliën

De Bruecker

Demeulemeester

De Boeck

. Personnel scheduling: a literature review. Eur J Oper Res. 2013; 226(3): 367-385.

17.

Huang

W-T

Chen

P-S

Liu

Chen

Y-R

Chen

Y-H

. Dynamic configuration scheduling problem for stochastic medical resources. J Biomed Inform. 2018; 80: 96-105.

18.

Chen

P-S

Lin

Peng

. A two-stage method to determine the allocation and scheduling of medical staff in uncertain environments. Comput Ind Eng. 2016; 99: 174-188.

19.

Bagheri

Devin

Izanloo

. An application of stochastic programming method for nurse scheduling problem in real word hospital. Comput Ind Eng. 2016; 96: 192-200.

20.

Zheng

Liu

Gong

. A simple randomized variable neighbourhood search for nurse rostering. Comput Ind Eng. 2017; 110: 165-174.

21.

Zanda

Zuddas

Seatzu

. Long term nurse scheduling via a decision support system based on linear integer programming: a case study at the University Hospital in Cagliari. Comput Ind Eng. 2018; 126: 337-347.

22.

Burke

De Causmaecker

Vanden Berghe

Van Landeghem

. The state of the art of nurse rostering. J Sched. 2004; 7(6): 441-499.

23.

Osogami

Imai

. Classification of various neighborhood operations for the nurse scheduling problem. In: Lee DT, Teng S-H, eds. Algorithms and Computation. ISAAC 2000, LNCS 1969, 72-83: Springer-Verlag Berlin Heidelberg; 2000.

24.

Sorensen

. Metaheuristics-the metaphor exposed. Int T Oper Res. 2015; 22(1): 3-18.

25.

Bouajaja

Dridi

. A survey on human resource allocation problem and its applications. Oper Res-Ger. 2017; 17(2): 339-369.

26.

Cormen

Leiserson

Rivest

Stein

. Introduction to Algorithms. Third edition ed. Cambridge, MA, USA: The MIT Press; 2009.

27.

Gutjahr

Rauner

. An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria. Comput Oper Res. 2007; 34(3): 642-666.

28.

Tsai

C-C

SHA

. A two-stage modeling with genetic algorithms for the nurse scheduling problem. Expert Syst Appl. 2009; 36(5): 9506-9512.

29.

Awadallah

, Bolaji ALa Al-Betar

. A hybrid artificial bee colony for a nurse rostering problem. Appl Soft Comput. 2015; 35: 726-739.

30.

Todorovic

Petrovic

. Bee colony optimization algorithm for nurse rostering. IEEE Trans Syst Man Cybern Syst. 2013; 43(2): 467-473.

31.

Lin

Kang

Chiang

Chen

. Nurse scheduling with joint normalized shift and day-off preference satisfaction using a genetic algorithm with immigrant scheme. Int J Distrib Sens N. 2015; 2015: Article ID 595419, 10 pages.

32.

Michael

Jeffery

David

. Nurse preference rostering using agents and iterated local search. Ann Oper Res. 2015; 226(1): 443-461.

33.

Xiang

Yin

Lim

. A short-term operating room surgery scheduling problem integrating multiple nurses roster constraints. Artif Intell Med. 2015; 63(2): 91-106.

34.

Yeh

Lee

. A particle swarm optimization approach with refinement procedure for nurse rostering problem. Comput Oper Res. 2015; 54: 52-63.

35.

Moon

. Development and evaluation of NRMIS (Nursing Resources Management Information System) for managing healthcare resources. Technol Health Care. 2019; 27(5): 557-565.

36.

Yao

Chen

Kuo

Shih

Wang

Chen

. Solving patient referral problems by using bat algorithm. Technol Health Care. 2020; 28(S1): 433-442.

37.

Yang

X-S

. A New Metaheauristic Bat-Inspired Algorithm. Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), Volume 284 of the series studies in Computational Intelligence: Springer Berlin Heidelberg; 2010. 65-74.

38.

Yılmaz

Küçüksille

. A new modification approach on bat algorithm for solving optimization problems. Appl Soft Comput. 2015; 28: 259-275.

39.

Sheng

X-H

C-M

. Application of bat algorithm to permutation flow-shop scheduling problem. Ind Eng J. 2013; 16(1): 121-124.

40.

Bao

Zhang

. Solving dual flexible job-shop scheduling problem using a bat algorithm. Adv Prod Eng Manag. 2017; 12(1): 5-16.

41.

Zhang

. Genetic mutation bat algorithm for 0–1 knapsack problem. Comput Eng Appl. 2012; 50(11): 49-52.

42.

Zhou

. A complex-valued encoding bat algorithm for solving 0-1 knapsack problem. Neural Process Lett. 2016; 44(2): 407-430.

43.

Osaba

Yang

Diaz

Lopez-Garcia

Carballedo

. An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Eng Appl Artif Intel. 2016; 48: 59-71.

44.

Cai

Gao

Xue

. Improved bat algorithm with optimal forage strategy and random disturbance strategy. Int J Bio-Inspir Com. 2016; 8(4): 205-214.

45.

Yahya

Tokhi

. A modified bats echolocation-based algorithm for solving constrained optimisation problems. Int J Bio-Inspir Com. 2017; 10(1): 12-23.

46.

Chen

Zeng

. Developing two heuristic algorithms with metaheuristic algorithms to improve solutions of optimization problems with soft and hard constraints: An application to nurse rostering problems. Appl Soft Comput. 2020; 93: Article 106336.

47.

Chen

Lin

Peng

. A two-stage method to determine the allocation and scheduling of medical staff in uncertain environments. Comput Ind Eng. 2016; 99: 174-188.

48.

Saaty

. The Analytic Hierarchy Process: McGraw Hill International; 1980.

49.

Saaty

. Decision Making For Leaders-the Analytic Hierarchy Process for Decisions in a Complex World: Pittsburgh, PA: RWS Publications; 1990.

Developing three-phase modified bat algorithms to solve medical staff scheduling problems while considering minimal violations of preferences and mean workload

Abstract

BACKGROUND:

OBJECTIVE:

METHODS:

RESULTS:

CONCLUSIONS:

Keywords

1. Introduction

2. Literature review

2.1 Medical staff scheduling using metaheuristics

2.2 Development and application of the BAs

3. Methodology

3.1 Mathematical programming of the MSSP

3.2 Solution procedures and corresponding pseudo code of the three-phase modified BAs

Solution procedures for minimization problems:

Phase 1:

Phase 2:

Phase 3:

Workload balance mechanism:

Shift schedule correction mechanism:

4.1 Background of the case hospital and imaging center

4.2 Hierarchical analysis weightings

Table 1 Weights for the soft constraints

Table 4 After Phase 3, results of 18 ( α , γ , r 0 , A 0 ) parameter settings of BA1, BA2, and BA3

Table 6 Solutions and solving time of BA1, BA2, and BA3 after Phase 3

5. Conclusions and future research

Footnotes

Acknowledgments

Conflict of interest

References

Table 1
Weights for the soft constraints

Table 4
After Phase 3, results of 18 ( $\alpha$ , $\gamma$ , $r_{0}$ , $A_{0}$ ) parameter settings of BA1, BA2, and BA3

Table 6
Solutions and solving time of BA1, BA2, and BA3 after Phase 3