A heuristic algorithm for medical staff’s scheduling problems with multiskills and vacation control

Abstract

Introduction

The main issue related to the duty schedule is to allocate medical staff to each medical department by considering personnel skills and personal vocation preferences. However, how to effectively use staff’s multiskill characteristics and how to execute vocation control have not been well investigated.

Objectives

This article aims to develop duty scheduling and vacation permission decisions to minimize the sum of customers’ waiting costs, the overtime cost of medical staff, the cost of failing to meet medical staff’ vacation requirements, and the cost of mutual support between departments.

Methods

This study formulated the problem as a multiperiod mixed integer nonlinear programming model and developed a hybrid heuristic based on evolutionary mechanism of genetic algorithm and linear programming to efficiently solve the proposed model.

Results

Five types of problems were solved through Lingo optimization and the proposed approach. For small-scale problems, both methods can find the optimal solutions. For a slightly larger problem, the solutions found by the proposed approach are superior those of Lingo.

Conclusion

This research discusses the complex decision-making problem of on-duty arrangement and vacation control of medical staff in a multidepartmental medical center. This research formulates the medical staff’s scheduling and vacation control problems as constrained mixed integer quadratic programming problems. Computational results indicate that the proposed approach can efficiently produce compromise solutions that outperform the solutions of the Lingo optimization software.

Keywords

Medical staff scheduling multiskills vacation control heuristic

Introduction

Operating a medical department usually needs to meet some requirements, which include (1) the combination of medical staff assigned to each department should meet each department's manpower needs, and (2) the duty days of each staff should meet the requirements of the maximum and minimum working days. In general, the internal staff of each medical department is sufficient to meet these requirements. However, some gaps may exist between the manpower from internal members due to uncertainty demand. The uncertain factors include emergencies and uncertain operation times,¹ uncertain surgery durations² and so forth. When the medical manpower of a department is insufficient, many negative consequences may occur. First, patients must spend additional waiting time. The workload of the medical staff in the department is expected to increase.³ A department may take the risk of shortage of basic care services^4,5 and poor patient prognosis⁶ due to insufficient nurses. In addition, employees who apply for a vacation may be requested to postpone their leave application due to insufficient night shift staff and insufficient staff on holidays.

Basically, the increase of manpower can enhance the quality of medical care service. However, from a cost–benefit point of view, merely increasing manpower is not economical because excessive increase in staff will only ineffectively increase the cost of medical services.⁷ Thus, properly arranging manpower under the established personnel and determining the correct number of manpower deployed on any given shift are important.⁸ When arranging medical manpower, planners can further notice two phenomena. First, staff have more than two technical skills. This feature enables staff in different departments to support one another across departments in the same branch or other branches because they have the skills required by the supported department. Second, medical staff may have their personal preferences to apply for their statutory holidays or to make up for certain overtime days. To avoid the cancellation of approved leave applications due to insufficient manpower, it is better to simultaneously arrange medical manpower and perform vacation permission control at the same time, because the staff's vacation preference will affect the number of people that can be arranged.

However, no work in the literature simultaneously investigates how to effectively use staff’s multiskill characteristics and how to execute vocation control. In order to fill the research gap, this study establishes a mathematical model and an intelligent heuristic approach to construct the decisions of medical staff's duty scheduling and vacation control to minimize the sum of customers’ waiting costs, the overtime cost of medical staff, the cost of failing to meet medical staff’s vacation requirements, and the cost of mutual support between departments.

Literature review

Baker⁹ categorized the personnel scheduling problems into three types, namely, the shift scheduling problem, days off scheduling problem, and tour scheduling problem. The shift scheduling problem type is of a daily time scheduling problem and is scheduled in daily scheduling. The days off scheduling problem means the length of the work week in the facility does not necessarily match the length of the work week of employees. The third category is a combination of the first two problem types. In personnel scheduling, organization staff work seven days a week and work shift every day. This type of planned schedule not only considers the rules of the number of days that should be applied for work and vacation within a period but also includes the work and rest periods on the working day. The scope and type of the third category are complex, and problem solving is less easy. The problems discussed in this article are of this type.

The characteristic of large-scale personnel scheduling problem is that it is large in scale, with complicated constraints, and is difficult to solve. In terms of solution methods, Bechtold et al.¹⁰ classified the solution method of personnel scheduling problem into two types: linear programming or construction-based approaches. Erhard et al.¹¹ provided a good overview of quantitative methods for physician scheduling problems. They addressed the characteristics of various physician scheduling problems, categorized the existing research methods, and explained the research gaps. Mathematical programming techniques, such as linear, integer, or mixed integer programming, are usually applied to formulate most personnel scheduling problems. Problem solving techniques, such as heuristic algorithms based on decomposition techniques and meta-heuristics, are used to solve them. However, it is difficult to obtain a satisfactory solution within a reasonable time using exactly methods since most personnel scheduling problems are computationally complex. Thus, many heuristics or meta-heuristics such as neural networks, particle swarm optimization, ant colony optimization, scatter search iterated local search and variable neighborhood search^12–16 have been applied to solve various types of personnel scheduling problems because they can effectively generate reasonable feasible solutions within a limited computational time.

The components in the objective function and the constraints on decision variables in various scheduling problems are quite diverse. Personnel costs are usually considered. Some authors also consider customer waiting costs. Johnson et al.¹⁷ showed that nearly 77% of emergency department patients leave the hospital without receiving treatment due to the long waiting time. Bhandari et al.¹⁸ proposed an algorithm to solve a dynamic operator staffing problem in a call center. The objective of their model is to minimize cost associated with delay, hiring servers, waiting and using temporary servers. Nah and Kim¹⁹ established a mathematical model for the purpose of minimizing the costs related to waiting, labor, and abandonment to discuss the labor planning and deployment of hospital appointment call centers. Othman et al.²⁰ balanced patient needs and human resources from the viewpoint of the workload of all medical staff, patient waiting time, and patient response time to optimize the functions of the pediatric emergency department.

The above literature does not consider personnel scheduling issues with cross-department support. Mabert and Raedels²¹ established a model with multisectors in which the holiday schedule is used to deal with changes in daily customer demand in the bank office. Later, Bechtold²² developed a transfer model to discuss the same problem. However, neither of these two seminal works consider the scheduling issues of mutual assistance among personnel across departments. Considering employees’ abilities and skills, Dahmen et al.²³ dealt with a personalized multidepartment multiday shift planning problem in which employees can transfer between departments subject to certain restrictions. The goal of the problem is to assign workday shifts to employees within the scope of the multiday plan by considering some common restrictions related to the multiday shift plan and some restrictions that apply to the interdepartmental transfer flexibility option. They established a scheduling plan to minimize the costs related to under-coverage, over-coverage, transfer, and labor. However, in this research, the workdays of each employee are known. Schoenfelder et al.²⁴ established a model to deal with a nurse scheduling problem through the determinations of resource sizes and allocations, cross-training levels, patient process strategies, and nurse arrangements by using flexible labor and patient transfer between inpatient units.

Some researchers deal with the duty scheduling problem in which the personnel have multiple skills. Bechtold et al.¹⁰ classified personnel scheduling solutions into three groups according to the flexibility of skills. The first group is defined by planners. In this case, the scheduler can freely define the skills of each person. The second group is related to the issue of hierarchical workforce. In this case, higher-level employees can perform the tasks of lower-level employees, and vice versa. The characteristic of the last group is that skills cannot be substituted. Tasks or jobs that require specific skills can only be performed by workers with that skill. Nevertheless, workers may still receive cross-training. Van den Bergh et al.²⁵ divided personnel scheduling problems into three categories according to the flexibility of skills. The first category is user-defined skill types. In this type, everyone's skills can be freely defined. This type is suitable for the situation where employees with certain specific skills can easily be hired or trained. The second group handles the case with hierarchical workforce. In this case, high-level skilled personnel can do jobs lower than their own skill level. The third group is where jobs with specific skills can only be performed by people with that skill and cannot be replaced by people with other skills. However, workers may still receive cross-training.

When personnel can be divided into different skill categories, a hard constraint is usually added to ensure that the number of workers required for each skill is sufficient during a specific period. In the case of soft constraints, when employees with the right skills are lacking, people with other skills can take over, but the disadvantage is that it damages the objective value. Harper et al.²⁶ used simulation optimization methods to solve the problem of nursing team size and skills. Campbell²⁷ proposed a two-stage stochastic procedure to schedule and assign cross-trained workers in a multidepartment service environment with random demands.

Among the mentioned literature with mutual support between departments, no research considers the multiskilled characteristics of personnel and the waiting time of patients. Long waiting time is an important reason for patient dissatisfaction. Therefore, in this study, in addition to considering the multiskilled characteristics of the personnel, the human support among multiple departments, and the vacation preferences of medical staff, waiting cost is considered in the objective function.

Model description and assumption

A medical institution provides medical services by its S employees and M departments. The number of skills needed in this medical institution is divided into K types. The service provided by each department requires a different combination of skill types. We use parameters $D_{k}^{m} = 1$ and $D_{k}^{m} = 1$ to indicate that skill k is needed and not needed in department m, respectively. In department m, $P_{k}^{m}$ internal employees are allocated to serve jobs that require skill k. The total number of internal employees in department m is $P^{m} = \sum_{k = 1}^{K} P_{k}^{m}$ with $S = \sum_{m = 1} P^{m}$ . We respectively use binary parameters $e_{s}^{m} = 1$ and $e_{s}^{m} = 0$ to indicate whether or not employee s is an internal employee of department m. Every employee in the department has a primary skill. In addition to primary skill, some staff have secondary skills. Let binary parameters $a_{s k} = 1$ and $a_{s k} = 0$ to indicate that staff s has and does not have skill k, respectively.

The institution is planning a T days’ staff schedule and divides a day into H periods. During the planning days, the minimum and maximum working days of each staff are $T_{1}$ and $T_{2}$ days, respectively. The working time of each employee is E consecutive periods, and each employee must have an allowable starting working period. We use binary parameters $a_{s}^{h} = 1$ and $a_{s}^{h} = 0$ respectively to indicate whether or not employee s can start to work from the start of period h. In addition, employees apply for personal leaves on working days. We use symbol $r_{s t}$ to represent whether employee s applies for a leave on day t.

For department m on day t, let $B_{t}^{m}$ and $E_{t}^{m}$ be the starting and ending operating periods, respectively. For convenience, we set $B_{t}^{m} = 0$ and $E_{t}^{m} = 0$ if no operation on day t. During the operation period of department m, the maximum service station that can be set up in department m is $n^{m} = J^{m}$ due to capacity limitation; the minimum service station that needs to be setup is $n^{m} = 1$ due to the maintenance of basic operations. If $n_{t}^{m h}$ severs are setup in period h of day t in department m, the number of employees with skill k needed is required to have at least $n_{t}^{m h} N_{k}^{m}$ for all k. The hourly service rate per sever of department m is assumed to follow the exponential servicer time with parameter $μ^{m}$ . During the operation period of department m, the average customer arrival rate during period h is assumed to follow the Poisson distribution with average arrival rate per hour, $λ_{t}^{m h}$ . Each department has different workloads at different periods. To reach the purpose of mutual support between departments, the hospital performs staff transfer to adjust the number of service stations in each department.

In addition, the period waiting cost of customers in department m is $c^{m}$ , the daily overtime cost of staff s is represented by $c_{s}^{o}$ , and the cost of failing to allow staff s’ leave application is represented by $c_{s}^{r}$ . In addition, we let $g_{s}^{m}$ represent the cost of dispatching employee s to work in department m. If department m is employee s’ own department, then the cost is $g_{s}^{m} = 0$ .

The medical institution expects to minimize the sum of customers’ waiting cost, the cost of failing to allow vacation applications, the overtime cost and the cost of dispatching employees to support other departments. To reach this goal, the medical institution must seriously make the following decisions: (1) the decision of each employee's starting working period, (2) the decision of each employee's working days, (3) the decision of whether employees work in their own department, (4) the decision related to which departments’ employees are dispatched to support departments with short manpower, and (5) the decision to approve leave application. The relevant symbols and decisions are summarized as follows, and the mathematical model is formulated thereafter.

The total cost (TC) includes the cost of unapproving employees’ leave applications (CR), the overtime cost and the dispatch cost for cross-departmental personnel support (CO), and patients’ waiting cost (CW), and is given by (1).

TC = C W + CR + CO + CD .

(1)

where

C R = \sum_{t = 1}^{T} \sum_{s = 1}^{S} (r_{s t} - y_{s t}) c_{s}^{r} .

(2)

C O = \sum_{s = 1}^{S} (\sum_{t = 1}^{T} \sum_{h = 1}^{H} x_{s t}^{h} - T_{1}) c_{s}^{o} .

(3)

C D = \sum_{t = 1}^{T} \sum_{m = 1}^{M} \sum_{s = 1}^{S} \sum_{h = 1}^{H} z_{s t}^{h m} (1 - e_{s}^{m}) g_{s}^{m} .

(4)

C W = \sum_{t = 1}^{T} \sum_{m = 1}^{M} \sum_{h = 1}^{H} W_{q t j}^{m h} c^{m} .

(5)

On day t, the number of customer arrivals per hour in department m follows the Poisson distribution with an average of

λ_{t}^{m h}

. According to the M/M/S queueing model, the average waiting time that a customer waits at the queuing system of department m having

n_{t}^{m h} = j

severs in period h of day t can be estimated by (6).

W_{q t j}^{m h} = \frac{λ_{t}^{m h} μ^{m} {(λ_{t}^{m h} / μ^{m})}^{j}}{(j - 1)! {(j μ^{m} - λ_{t}^{m h})}^{2}} P_{t j}^{m h}, \forall m, t, h,

(6)

where

P_{t j}^{m h}

is the probability that no one appears at department m having j service stations and is given by (7).

P_{t j}^{m h} = \frac{1}{\sum_{n = 0}^{j - 1} \frac{1}{n!} {(\frac{λ_{t}^{m h}}{μ^{m}})}^{n} + 1 / j! {(\frac{λ_{t}^{m h}}{μ^{m}})}^{j} (\frac{j μ^{m}}{j μ^{m} - λ_{t}^{m h}})}, \forall m, t, h .

(7)

In addition, the decision variables are subject to the following constraints. The number of service stations in department m cannot exceed

J^{m}

. Thus, we have:

n_{t}^{m h} \leq J^{m}, \forall m, t, h .

(8)

The number of staff with skill k in department m in period t is the sum of staff dispatched from all departments to department m. Thus, we have:

q_{k t}^{m h} = \sum_{s = 1}^{S} z_{s t}^{m h} a_{s k} y_{s k t}^{h} \forall k, m, k, t, h .

(9)

The number of employees with skill k allocated must be no less than

N_{k}^{m}

when

n_{t}^{m h}

severs are setup in department m in period h of day t. Thus, we have:

q_{k t}^{m h} \geq n_{t}^{m h} N_{k}^{m}, \forall s, h .

(10)

Every employee has a shift starting period. Thus, we have:

\sum_{h = 1}^{H} z_{s}^{h} = 1, \forall s .

(11)

The start time of each employee must be selected from the set of periods that can start work. Thus, we have:

z_{s}^{h} \leq a_{s}^{h}, \forall s, h .

(12)

For any day, if the first period of an employee's shift time is not from time period h, then the employee's initial working time on any day is not from period h. Thus, we have:

x_{s t}^{h} \leq z_{s}^{h}, \forall s, t, h .

(13)

The sum of the number of duty periods of employee s in all departments on any day cannot exceed E working periods on any day. Thus, we have:

\sum_{m = 1}^{M} \sum_{h = 1}^{H} z_{s t}^{m h} \leq E, \forall s, t .

(14)

Employees will not be on duty in more than one department at the same time. Thus,

\sum_{m = 1}^{M} z_{s t}^{m h} \leq 1, \forall s, t, h .

(15)

Employees will not be on duty at any time of any day with two different skills at the same time. Therefore, we have (16).

\sum_{k = 1}^{K} y_{s k t}^{h} \leq 1, \forall s, t, h .

(16)

When employee s is on duty with his expertise k in period h on day t, he must be dispatched to a department that needs such an expertise on duty. Thus, we have (17).

y_{s k t}^{h} \leq \sum_{m = 1}^{M} z_{s t}^{m h} D_{k}^{m}, \forall s, t, h .

(17)

Suppose employee s is on duty in a certain department during the h-th period on any day. Then the shift start time corresponding to this duty period must satisfy (18–19).

\sum_{m = 1}^{M} z_{s t}^{m h} = \sum_{h^{'} = 1}^{h} x_{s t}^{h^{'}} + \sum_{h^{'} = H + h - E + 1}^{H} x_{s t}^{h^{'}}, \forall s, t, h \leq E - 1 .

(18)

\sum_{m = 1}^{M} z_{s t}^{m h} = \sum_{h^{'} = h - E + 1}^{h} x_{s t}^{h^{'}}, \forall s, t, h \geq E .

(19)

If day t is an employee's working day, then only one starting working period is recorded on that day. Thus, we have (20).

\sum_{h = 1}^{H} x_{s t}^{h} \leq 1, \forall s,

(20)

Each employee must work at least

T_{1}

days. Thus, we have (21).

\sum_{t = 1}^{T} \sum_{h = 1}^{H} x_{s t}^{h} \geq T_{1}, \forall s,

(21)

Each employee's maximum working days is

T_{2}

. Thus, we have (22).

\sum_{t = 1}^{T} \sum_{h = 1}^{H} x_{s t}^{h} \leq T_{2}, \forall s,

(22)

If no leave application exists, a decision whether to approve a leave is no longer needed. Thus, we have (23).

y_{s t} \leq r_{s t}, \forall s, t .

(23)

If employee s asks for a leave on day t and is approved, the employee will not be scheduled to work on that day. Thus, we have (24).

x_{s t}^{h} \leq 1 - y_{s t}, \forall s, t, h .

(24)

Finally,

n_{t}^{m h}

must be and integer, and

z_{s}^{h}

x_{s t}^{h}, y_{s k t}^{h}, g_{s t}^{m h}, y_{t k}, z_{s t}^{m h} \in {0, 1} \forall m, j, n, s, t .

Solution method

The problem is a mixed integer nonlinear programming problem. We develop a hybrid heuristic to solve the problem. The evolutionary mechanism of genetic algorithm is applied to determine the number of service stations, $n_{t}^{m h}$ , and skills used by employees on duty, $y_{s k t}^{h}$ . The concept of the heuristic is addressed as follows.

Encoding scheme of a chromosome for the number of service stations

Gene expression

Let $O_{t}^{m}$ be the smallest integer, such that $O_{t}^{m} E \geq E_{t}^{m} - B_{t}^{m}$ , and be used to determine the number of shifts on the operating day. A chromosome is composed of $\sum_{m = 1}^{M} \sum_{t = 1}^{T} O_{t}^{m}$ integer genes.

An example: Suppose a medical center is planning a T = 2-day scheduling for its M = 2 departments. The number of periods per shift for each employee is E = 4; the start period $B_{t}^{m}$ and end period $E_{t}^{m}$ of department m's operating periods on day t are assumed to be $(B_{1}^{1}, E_{1}^{1}) = (1, 12)$ , $(B_{2}^{1}, E_{2}^{1}) = (3, 10)$ , $(B_{1}^{2}, E_{1}^{2}) = (3, 10)$ and $(B_{2}^{2}, E_{2}^{2}) = (3, 10)$ .

In this situation, $O_{1}^{1} = 3$ and $O_{2}^{1} = 2$ service stations for department 1 for days 1 and 2, respectively; $O_{1}^{2} = 2$ and $O_{2}^{2} = 2$ service stations for department 2 for days 1 and 2, respectively. (3,1,2,2,1,1,22,1) on the fourth row of Table 1 is an example of a chromosome.

Table 1.

An example of a chromosome.

M	1					2
T	1			2		1		2
No. of genes	1	2	3	1	2	1	2	1	2
Chromosome	3	1	2	2	1	1	2	2	1
Period	1	5	9	3	7	3	7	3	7

Determination of the number of service stations

The $i = \sum_{m^{'} = 1}^{m - 1} \sum_{t^{'} = 1}^{t} O_{t^{'}}^{m^{'}} + \sum_{t^{'} = 1}^{t - 1} O_{t^{'}}^{m} + n$ -th gene, $g_{i}^{1}$ , is used to determine the values of $n_{t}^{m h}$ for $h = B_{t}^{m} + (n - 1) E$ through Formula (25).

n_{t}^{m h} = max {g_{i}^{1}, j_{t}^{m h}} \forall m, t, h .

(25)

where

j_{t}^{m h}

is given by (26).

j_{t}^{m h} = min {j | j μ^{m} \geq \max {λ_{t}^{m h}, B_{t}^{m} + (n - 1) E \leq h \leq B_{t}^{m} + n E - 1}} \forall m, t, h .

(26)

For example, the periods corresponding to the first three data of the chromosomes in Table 1 are periods h = 1, 5, and 9. For department m = 1, suppose the minimum integers that satisfy

j μ^{1} \geq \max {λ_{1}^{1, h}, 1 \leq h \leq 4}

j μ^{1} \geq \max {λ_{1}^{1, h}, 5 \leq h \leq 8

. }, and

j μ^{1} \geq \max {λ_{1}^{1, h}, 9 \leq h \leq 12

} are

j_{1}^{*} =

j_{2}^{*} =

2, and

j_{3}^{*} =

2, respectively. Then, consider that the values of

g_{i}

in the chromosome that correspond to periods h = 1, 5, and 9 are 3, 1, and 2, respectively. According to Equation (25), we know that for department 1, the number of service stations setup at periods 1, 5, and 9 are

max {3, j_{1}^{*}} = 3

max {1, j_{2}^{*}} = 2

, and

max {2, j_{3}^{*}} = 2

service stations, respectively. That is, for department m = 1 in day t = 1, the values of

n_{j}^{m h}

are

n_{1}^{1 h} = 0

for all h, except that

n_{1}^{1, 1} = 3

n_{1}^{1, 5} = 2

and

n_{1}^{1, 9} = 2

Encoding scheme of a chromosome for skills used by employees on duty

Gene expression

A chromosome is composed of $S M T H$ binaries. Employee s can only be on duty in departments with $e_{s}^{m} = 1$ , and department m's operating periods on day t are from $B_{t}^{m}$ to $E_{t}^{m}$ . On an operation day of department m, we let $T_{B t}^{E m} = E_{t}^{m} - B_{t}^{m} + 1$ for $E_{t}^{m} > B_{t}^{m}$ and $T_{B}^{E m} = 0$ for $E_{t}^{m} = B_{t}^{m} = 0$ . For employee s, we use $\sum_{m = 1}^{M} e_{s}^{m} \sum_{t = 1}^{T} T_{B t}^{E m}$ binaries to represent whether employee s is on duty in department m with skill k in time period h on day t. A chromosome is composed of $\sum_{s = 1}^{S} \sum_{m = 1}^{M} e_{s}^{m} \sum_{t = 1}^{T} T_{B t}^{E m}$ binary genes.

Determination of skills used by employees on duty

For employee s, $y_{s k t}^{h}$ is 0 in the following two situations: (a) department m is not a specialized department (i.e. $e_{s}^{m} = 0$ ) or (b) nonoperating time of possible duty department m (i.e. $B_{t}^{m} = E_{t}^{m} = 0$ ). In addition to the above situation, the values of $y_{s k t}^{h}$ are determined by its gene value. However, for fixed s, t, and h, given that only one of $y_{s k t}^{h}$ s can be 1, when the number of elements in ${k | y_{s k t}^{h} = 1, a_{s k}$ = 1} is larger than 1, we use the following criteria to determine which k will be one. We give different priorities on the basis of whether skill k with $y_{s k t}^{h} = 1$ is the original department of employee s. For all $k \in {k | y_{s k t}^{h} = 1, a_{s k}$ = 1}, if $D_{k}^{m} a_{s k}$ = $e_{s}^{m}$ , then the duty location of employee s, who uses skill k, is his/her original department. That is, we let $y_{s k^{'} t}^{h} = 0$ for all k, except $y_{s k t}^{h} = 1$ for the k with $D_{k}^{m} a_{s k}$ = $e_{s}^{m}$ .

Fitness function

After the values of $n_{t}^{m h}$ and $y_{s k t}^{h}$ are determined, the value of CW is also known by Equations (5)–(7). We can compute the value of CW. However, the number of employees may be insufficient to arrange feasible scheduling on the basis of the number of service stations generated by the previous step. Under a given policy of $n_{t}^{m h}$ , the required number of employees with skill k for period h of day t for department m is $n_{t}^{m h} N_{k}^{m}$ . If insufficient, then the policy of $n_{t}^{m h}$ and $y_{s k t}^{h}$ becomes an infeasible solution. To avoid unfeasible solutions, we define ${\tilde{z}}_{k t}^{m}$ as the shortage of employees with skill k in period h of day t in department m, and a penalty value ${\tilde{c}}_{s}^{m}$ is given to a shortage of employee with skill k in department m. We add a penalty cost function by (27).

\tilde{C D} = \sum_{t = 1}^{T} \sum_{m = 1}^{M} \sum_{h = 1}^{H} {\tilde{z}}_{k t}^{m} {\tilde{c}}_{s}^{m} .

(27)

We also add Constraint (28).

\sum_{s = 1}^{S} z_{s t}^{m h} a_{s k} + {\tilde{z}}_{k t}^{m} \geq n_{t}^{m h} N_{k}^{m}, \forall m, k, t, h .

(28)

Subsequently, the fitness value and the decisions of $z_{s}^{h}$ , $x_{s t}^{h}, g_{s t}^{m h}, y_{t k}, z_{s t}^{m h}$ under the policy of $n_{t}^{m h}$ and $y_{s k t}^{h}$ are obtained by solving the following model.

Min C W + CR + CO + CD + \tilde{C D}

(29)

Subject to equations (2) to (4), (11) to (23), and (27) to (28).

We refer to the above model as Model 1. The procedure is addressed as follows.

Solution procedure:

Parameter input.

Generate an initial population of a group of individuals, let the best cost be $T C^{*}$ and be a large number, and start the iteration index from I = 1.

Perform the following procedures while Iter < Iter_max or the stop criterion has not been met.

Perform the following steps for each individual.

For each department, determine the values of $n_{t}^{m h}$ and $y_{s k t}^{h}$ by using the decoding value generated by the proposed algorithm and Equations (24) and (25).

Substitute $n_{t}^{m h}$ and $y_{s k t}^{h}$ as the parameters into Model 1 and solve Model 1 to obtain the decisions of $z_{s}^{h}$ , $x_{s t}^{h}, g_{s t}^{m h}, y_{t k}, z_{s t}^{m h}$ and the fitness, $T C$ , of an individual.

If no shortage occurs, that is $\tilde{C D} = 0$ , and the current fitness, TC, is better than the best solution so far, $T C^{*}$ , then let $T C^{*} = T C$ and replace the decisions of $z_{s}^{* h}, x_{s t}^{* h}, y_{s k t}^{* h}, y_{s t}^{*}, z_{s t}^{* m h}$ , and $n_{t}^{* m h}$ with $z_{s}^{h},$ $x_{s t}^{h}, y_{s k t}^{h}, y_{s t}, z_{s t}^{m h}$ , and $n_{t}^{m h}$ , respectively.

If iter = iter_max or the stop criterion has been met, then report the result; otherwise, let iter = iter + 1; perform three operators, including election, crossover, and mutation; back to Step (a).

Numerical example

In this section, the duty scheduling problem of M = 8 departments is used to illustrate the duty scheduling planning. A total of 191 employees are recorded in these eight departments. Each staff's belonging department, $e_{s}^{m}$ , and possessing skills, $a_{s k}$ , are shown in Table 2. The values of $P_{k}^{m}$ and $P^{m}$ can also be obtained from Table 2. The minimum number of medical staff with skill k requires to set up a service station in department m, $N_{k}^{m}$ is as shown in Table 3. To shorten this paragraph, the remaining parameters are assumed to be in formula form to save space. Each department's starting and ending operating periods are assumed to be $B_{t}^{m} = 5$ and $E_{t}^{m} = 8$ for $1 \leq t \leq 5$ for departments $1 \leq m \leq 4$ , $B_{t}^{m} = 5$ and $E_{t}^{m} = 10$ for $2 \leq t \leq 6$ for departments $5 \leq m \leq 6$ , and $B_{t}^{m} = 1$ and $E_{t}^{m} = 12$ for $1 \leq t \leq 7$ for departments $7 \leq m \leq 8$ . The value of $a_{s}^{h}$ is assumed to be $a_{s}^{h} = 1$ for $\max {B_{t}^{m}, \forall m} \leq h \leq {E_{t}^{m}, \forall m}$ . The value of $r_{s t}$ is assumed to be $r_{s t^{'}} = 1$ , where $t^{'} = \mod (s, 7) + 1$ . The value of $μ^{m}$ is assumed to be 5 + mod(m,4). The value of $λ_{t}^{m h}$ is assumed to be $0.7 μ^{m} + 0.2 \mod (t + m + h, 4)$ . Costs of $c^{m}$ , $c_{s}^{r}$ , $c_{s}^{o}$ and $g_{s}^{m}$ are assumed to be $c^{m} = 60 + 20 \mod (m, 5)$ , $c_{s}^{r} = 100 + 100 \mod (m, 5)$ , $c_{s}^{o} = 1500 + 200 \mod (s, 3)$ , and $g_{s}^{m} = 20$ , respectively. Suppose that the belonging department of staff s is department n and the department on duty is department m. For m = n, suppose $g_{s}^{m}$ = 0. For $m \neq n$ , suppose $g_{s}^{m} = 20$ for $m \leq 6$ , $g_{s}^{m} = 90$ for $m = 7$ , and $g_{s}^{m} = 100$ for $m = 8$ .

Table 2.

The values of $a_{s k}$ and each employee's possessing skills.

s	S_m	AS	s	S_m	AS	s	S_m	AS	s	S_m	AS	s	S_m	AS	s	S_m	AS	s	S_m	AS
1	1	1,6	29	3	9,10	57	5	10,11	85	6	9	113	7	2,7	141	7	12	169	8	11,12
2	1	1,4	30	3	10,12	58	5	10,11	86	6	9	114	7	7,8	142	7	12	170	8	10,11
3	1	1,5	31	3	10,11	59	5	11,12	87	6	10	115	7	7	143	7	9,12	171	8	9,11
4	1	1,3	32	3	10,11	60	5	10,11	88	6	9	116	7	3,7	144	7	12	172	8	11,12
5	1	1,5	33	3	10,12	61	5	11	89	6	10,12	117	7	7,8	145	7	12	173	8	11,12
6	1	1,8	34	3	10,11	62	5	10,11	90	6	9,12	118	7	2,7	146	7	9,12	174	8	11
7	1	10	35	3	10,12	63	5	11	91	6	12	119	7	1,7	147	7	9,12	175	8	10,11
8	1	9,10	36	3	11,12	64	5	11	92	6	11,12	120	7	9,10	148	8	1,8	176	8	11,12
9	1	9,10	37	4	4,6	65	5	10,11	93	7	1,7	121	7	9,10	149	8	3,8	177	8	10,11
10	1	9,10	38	4	4,8	66	5	11	94	7	5,7	122	7	9,10	150	8	5,8	178	8	9,11
11	1	12	39	4	10	67	5	10,11	95	7	7	123	7	10	151	8	8	179	8	11
12	1	12	40	4	9,10	68	5	11	96	7	7	124	7	10	152	8	2,8	180	8	11
13	2	2,7	41	4	9,10	69	5	9,12	97	7	7,8	125	7	9,10	153	8	5,8	181	8	11,12
14	2	2,6	42	4	10	70	5	11,12	98	7	5,7	126	7	10	154	8	5,8	182	8	11
15	2	9,11	43	4	9,10	71	5	9,12	99	7	3,7	127	7	10,12	155	8	7,8	183	8	10,12
16	2	10,11	44	4	12	72	5	10,12	100	7	4,7	128	7	10,11	156	8	11	184	8	9,12
17	2	10,11	45	5	5,7	73	6	2,6	101	7	7,8	129	7	9,10	157	8	9,11	185	8	12
18	2	9,11	46	5	1,5	74	6	6,8	102	7	5,7	130	7	9,10	158	8	11	186	8	12
19	2	10,11	47	5	4,5	75	6	2,6	103	7	7	131	7	10,11	159	8	9,11	187	8	10,12
20	2	11	48	5	4,5	76	6	6,7	104	7	5,7	132	7	9,10	160	8	10,11	188	8	11,12
21	2	11,12	49	5	3,5	77	6	10,12	105	7	6,7	133	7	10	161	8	11,12	189	8	11,12
22	2	9,12	50	5	1,5	78	6	10	106	7	4,7	134	7	10	162	8	11	190	8	9,12
23	3	1,3	51	5	1,5	79	6	9,12	107	7	4,7	135	7	10	163	8	10,11	191	8	12
24	3	3,4	52	5	5,8	80	6	9,10	108	7	7,8	136	7	9,10	164	8	10,11
25	3	3,7	53	5	1,5	81	6	9	109	7	5,7	137	7	10,11	165	8	11
26	3	3,5	54	5	4,5	82	6	9,11	110	7	2,7	138	7	9,12	166	8	9,11
27	3	3,4	55	5	1,5	83	6	9,10	111	7	2,7	139	7	10,12	167	8	11
28	3	3,8	56	5	2,5	84	6	9	112	7	7	140	7	11,12	168	8	10,11

Symbol AS represents available skills.

Table 3.

The number of technicians k required to set up a service station, $N_{k}^{m}$ .

m	1			2			3			4			5			6			7			8
Required skills	1	10	12	2	11	12	3	9	12	4	10	12	5	11	12	6	9	12	7	10	12	8	11	12
$N_{k}^{m}$	3	2	1	1	3	1	3	3	1	1	2	1	3	3	1	1	3	1	3	2	1	1	3	1

Design of testing problems and computational environment

In this section, five problem types were designed to investigate the performance of the proposed approach and impacts of parameters on the computational results. For each problem type, five test cases were examined in which all parameters are the same as the basic dataset, except one parameter was changed. The number of departments for the five problem types was set from 4 to 8. In addition, for problem types 1 and 2, only the waiting cost was changed, and the cost was set at $(1 + 0.1 (n - 3)) c^{m}$ for the n-th case. For problem type 3, only the cost of unapproved leave was changed and became $(1 + 0.1 (n - 3)) c_{s}^{r}$ for the n-th case. For problem type 4, only the cost of unapproved leave was changed and became $(1 + 0.1 (n - 3)) g_{s}^{m}$ for the n-th case. For problem type 5, only the customer arrival rate was changed and became $(1 + 0.1 (n - 3)) λ_{t}^{m h}$ for the n-th case.

We used symbol HGA to stand for the proposed approach. The Visual C + + programming language was used to code the solution procedure of HGA. All of the test problems were solved by HGA and well-known Lingo optimization solver. The computing platform was implemented on an Intel® Core TM i5-7200 U CPU 2.7 GHz notebook computer with 16.0 GB RAM. The calculation time was set to a maximum of four hours. In HGA, 20 individuals comprised each generation, among which four individuals with the first four best fitness values were retained as the elite group and were directly copied to the next generation without evolution operators. The mating and mutation rates were set to 0.95 and 0.06, respectively. The criteria for the algorithm to stop include the conditions for convergence and when the number of iterations reaches 20,000. The condition of convergence is when the best solution appears continuously for 20 generations and remains unchanged. The comparison result of the HGA and Lingo was used to examine the performance of the proposed method.

Illustrative example

In this subsection, case 3 of problem type 2 was used to explain the on-duty period and working department of each staff in each department. In this case, 72 staff were recorded. We summarized the calculation results according to staff’s belonging departments (S_m), duty days (D), and working periods, including each employee's working departments, as presented in Table 4. The table shows that most staff were on duty in their own departments. However, employee number 21 belonging to department 2 supported department 5 in periods 5–8 of the sixth day, and employee number 48 belonging to department 5 supported department 4 in periods 5–8 from day 2 to day 5. The interdepartmental staff support cost incurred was $400. Although employee numbers 14 and 28 applied for the first day of leave, their applications were not approved. The unapproved leave cost was $500. The total waiting cost was $8807. Summing the three costs, TC = $9707.

Table 4.

Computational result for case 3 of problem type 2.

S	S_m	D	W_h	W_m	s	S_m	D	W_h	W_m
1–12	1	1–5	5–8	1	45,47,49,53,55,65,69	5	2–6	6–9	5
13–20,22	2	1–5	5–8	2	46,51,54,58,61–63,68	5	2–6	7–10	5
21	2	2–5	5–8	2	48,50,52,56,57,59,60,64,66,67,70–72	5	2–6	5–8	5
21	2	6	5–8	5	48	5	2–5	5–8	4
23–36	3	1–5	5–8	3	48	5	6	5–8	5
37–44	4	1–5	5–8	4

Performance of heuristic procedure

All five types of problems were solved through Lingo optimization and HGA. The computational results of the five problem types are shown in Tables 5 –9, in which the percentage gap of the TC between Lingo and HGA was given by the formula of (LS-HS)/LS, where symbols LS and HS stand for the TC of Lingo method and the TC of HGA method, respectively.

Ability to find optimal solutions

Lingo software is a software that can confirm the optimal solution. When the solution it finds is the best, the solution report will show the message of the global optimal solution found. If the optimal solution cannot be found, but a feasible solution can be found, then the solution report will show the message of the feasible solution found. Among the five problems, Lingo can find the optimal solution for all test cases in problem type 1 but can only find feasible solutions for the four other types of problems. Table 4 presents that Lingo and HGA can find the optimal solution for all cases of problem type 1. This feature shows that HGA can also find the optimal solution similar to the Lingo method.

Comparison of solution quality

The number of decision variables increases rapidly with a small increase in the number of departments. When the number of departments increases from five in problem type 2 to eight departments in problem type 5, the scale of the problem also increases rapidly. For problem type 2, the data are the same as those of problem type 1 but only the number of departments increases from four departments in problem type 1 to five departments. The increase in variables makes Lingo unable to find the optimal solution within the limited time. The last column of Table 6 shows that the HGA solution is slightly better than Lingo's solution in all test cases of Problem 2. On average, the HGA solution is better than Lingo's solution by 3.49%. From the last columns of Tables 5–9, we can find that as the problem size increases, the percentage gap of HGA over Lingo method tends to increase.

Table 5.

Computational result of problem type 1.

	Lingo						HEU
No.	CW	CR	CO	CD	TC	CPU	CW	CR	CO	CD	TC	CPU	LA vs. HA
1	6360	600	0	0	6960	35	6360	600	0	0	6960	25	0.0%
2	7154	600	0	0	7754	44	7154	600	0	0	7754	31	0.0%
3	7950	600	0	0	8550	92	7950	600	0	0	8550	25	0.0%
4	8745	600	0	0	9345	56	8745	600	0	0	9345	26	0.0%
5	9540	600	0	0	10,140	36	9540	600	0	0	10,140	31	0.0%

Table 6.

Computational result of problem type 2.

	Lingo					HEU
No.	CW	CR	CO	CD	TC	CW	CR	CO	CD	TC	CPU	LA vs. HA
1	7546	500	0	120	8166	7313	500	0	80	7893	155	3.3%
2	8449	500	0	160	9109	8227	500	0	80	8807	158	3.3%
3	9387	500	0	160	10,047	8807	500	0	400	9707	177	3.4%
4	10,285	500	0	200	10,985	9687	500	0	400	10,587	142	3.6%
5	11,220	500	0	200	11,920	10,568	500	0	400	11,468	195	3.8%
	9378	500	0	168	10,046	8920	500	0	272	9692		3.49%

Table 7.

Computational result of problem type 3.

	Lingo					HEU
No.	CW	CR	CO	CD	TC	CW	CR	CO	CD	TC	CPU	LA vs. HA
1	11,422.52	160	0	320	11,903	10625.51	0	0	560	11186	221	6.0%
2	11422.52	180	0	320	11923	10687.53	0	0	560	11248	216	5.7%
3	11422.52	200	0	320	11943	10625.51	0	0	560	11186	378	6.3%
4	11422.52	220	0	320	11963	10625.51	0	0	560	11186	355	6.5%
5	11693.62	0	0	520	12214	10625.51	0	0	560	11186	417	8.4%
	11477	152	0	360	11989	10638	0	0	560	11198		6.59%

Table 8.

Computational result of problem type 4.

	Lingo					HEU
No.	CW	CR	CO	CD	TC	CW	CR	CO	CD	TC	CPU	LA vs. HA
1	45593.4	200	4800	15048	65641	16572	0	0	192	16764	1542	74.5%
2	37309.2	200	2400	7668	47577	16572	0	0	216	16788	1662	64.7%
3	21088.8	0	0	460	21549	16572	0	0	240	16812	1567	22.0%
4	49777.2	200	0	19404	69381	16572	0	0	264	16836	1532	75.7%
5	20919.9	200	0	540	21660	16572	0	0	288	16860	1621	22.2%
	34938	160	1440	8624	45162	16572	0	0	240	16812		51.81%

Table 9.

Computational result of problem type 5.

	Lingo					HEU
No.	CW	CR	CO	CD	TC	CW	CR	CO	CD	TC	CPU	LA vs. HA
1	36605	300	0	22000	58905	19404	0	0	14220	33624	2100	42.9%
2	59310	300	13000	34580	107190	22159	0	0	14220	36379	2346	66.1%
3	87759	300	2200	36920	127179	25388	0	0	14220	39608	2258	68.9%
4	114099	0	0	33100	147199	38440	0	2200	32880	73520	2347	50.1%
5	327456	0	67000	38990	433446	51546	0	2200	32880	86626	2547	80.0%
	125046	180	16440	33118	174784	39551	0	880	25012	65443	2263	61.58%

Discussions

From The above numerical example results, we can find the following:

From the results of problem types 2 and 3 (last line of Tables 6 and 7), the average percentage gap of the TC between the two methods is only 3% and 6%, respectively. On average, the waiting cost of method Lingo is much higher than the waiting cost of HGA, and the dispatching cost of HGA is only slightly higher than that of Lingo. This result suggests that HGA can better use the manpower between departments to support one another for weighing various costs to achieve the goal of reducing the TC. Therefore, although the dispatching cost of HGA is higher, it can make the waiting cost much lower than that of Lingo. Therefore, TC is lower than that of Lingo.

For small sizing problems, planners can apply Lingo optimization software or HGA to plan manpower arrangements because both approaches can find optimal solutions. However, as problem size increases, planners should choose HGA to efficiently find satisfactory solutions.

For large problems, the Lingo and HGA methods can find feasible solutions. However, from the large gap between the Lingo and the HGA solutions shown in Tables 8 and 9, the quality of the Lingo solution strictly becomes poor with the increase in scale. One of the possible reasons for the HGA method to find a solution superior to the Lingo method in a short time is that the number of service stations and the skills of the personnel on duty by HGA are generated through algorithms. In addition, HGA uses the relationship between variables to further determine the variable of staff’s starting working time. These features greatly reduce the uncertain variables and the solution searching space. Furthermore, through the mechanism of evolutionary algorithm, the solution scheme is continuously improved to produce improved solutions. Thus, HGA approach outperforms the well-known commercial software Lingo solver for large-scale problems.

In the case of changes in waiting costs, unsatisfied vacation costs, and cross-departmental support costs, the proposed algorithm initiates a low-cost scheme first, weighing various costs to avoid a rapid increase in TC. For example, for problem type 2, when the waiting cost rises, the proposed algorithm uses further cross-departmental support, so that the waiting cost does not rapidly increase, and the TC does not increase rapidly. For another example, in problem type 5, when the demand is not high (cases 1–3), only low-cost personnel scheduling is used to properly arrange the department's manpower, but when the demand rises to more than 10% (cases 4–5), high-cost employee overtime programs begin to be launched.

Conclusion

Medical Staff's duty scheduling and leave control are practical problems in many medical institutions. The result of scheduling that does not consider vacation issues may lead to poor on-duty schedule, because the vacation preference of medical staff will affect the actual number of staff that can be arranged. To overcome this problem, this study establishes a mathematical model to simultaneously deal with these two issues and formulate the problem as a constrained mixed-integer programming problem to minimize the sum of customer waiting costs due to insufficient allocation of staff, the overtime cost of medical staff, the cost of failing to meet medical staff’s vacation requirements, and the cost of mutual support between departments. Since the formulated model is a highly complicated combinatorial optimization problem. We propose a hybrid intelligent approach based on a genetic algorithm to efficiently solve the problem. Computational results indicate that our proposed approach outperforms the Lingo optimization software. In addition, when waiting costs and demand rise, the proposed solution procedure can weigh the waiting costs and support costs, and adjust cross-departmental support decisions in a timely manner, so that the total cost will not increase rapidly. In practice, this effect can reduce the operating expenditure of medical institutions.

Footnotes

ORCID iD

Yi-Chih Hsieh

Appendix

References

Venkat

Kekre

Hegde

, et al. Strategic management of operations in the emergency department. Prod Oper Manag 2015; 24: 1706–1723.

Fügener

Schiffels

Kolisch

. Overutilization and underutilization of operating rooms - insights from behavioral health care operations management. Health Care Manag Sci 2017; 20: 115–128.

Zeltyn

Marmor

Mandelbaum

, et al. Simulation-based models of emergency departments: operational, tactical, and strategic staffing. ACM Trans Model Comput Simul 2011; 21: 24.

Griffiths

Ball

Drennan

, et al. Nurse staffing and patient outcomes: strengths and limitations of the evidence to inform policy and practice. A review and discussion paper based on evidence reviewed for the national institute for health and care excellence safe staffing guideline development. Int J Nurs Stud 2016; 63: 213–225.

Aykin

. Comparative evaluation of modeling approaches to the labor shift scheduling problem. Eur J Oper Res 2000; 125: 381–397.

Recio-Saucedo

Dall’Ora

Maruotti

, et al. What impact does nursing care left undone have on patient outcomes? Review of the literature. J Clin Nurs 2018; 27: 2248–2259.

Villarreal

Keskinocak

. Staff planning for operating rooms with different surgical service lines. Health Care Manag Sci 2014 ; 19: 144–169.

Saville

Griffiths

Ball

, et al. How many nurses do we need? A review and discussion of operational research techniques applied to nurse staffing. Int J Nurs Stud 2019; 97: 7–13.

Baker

. Workforce allocation in cyclical scheduling problems: a survey. J Oper Res Soc 1976; 27: 155–167.

10.

Bechtold

Brusco

Showalter

. A comparative-evaluation of labor tour scheduling methods. Decis Sci 1991; 22: 683–699.

11.

Erhard

Schoenfelder

Fügener

, et al. State of the art in physician scheduling. Eur J Oper Res 2018; 265: 1–18.

12.

Hao

Lai

Tan

. A neural network application in personnel scheduling. Ann Oper Res 2004; 128: 65–90.

13.

Akjiratikarl

Yenradee

Drake

. PSO-based algorithm for home care worker scheduling in the UK. Comput Ind Eng 2007; 53: 559–583.

14.

Gutjahr

Rauner

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

15.

Burke

Curtois

van Draat

, et al. Progress control in iterated local search for nurse rostering. J Oper Res Soc 2011; 62: 360–367.

16.

Burke

. A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems. Eur J Oper Res 2010; 203: 484–493.

17.

Johnson

Myers

Wineholt

, et al. Patients who leave the emergency department without being seen. J Emerg Nurs 2009; 35: 105–108.

18.

Bhandari

Scheller-Wolf

Harchol-Balter

. An exact and efficient algorithm for the constrained dynamic operator staffing problem for call centers. Manag Sci 2008; 54: 339–353.

19.

Nah

Kim

. Workforce planning and deployment for a hospital reservation call center with abandonment cost and multiple tasks. Comput Ind Eng 2013; 65: 297–309.

20.

Othman

Hammadi

Quilliot

. Multi-objective evolutionary for multi-skill health care tasks scheduling. IFAC-Papers On Line 2015; 48-3: 704–709.

21.

Mabert V

Raedels

. The detail scheduling of a part-time work force: a case study of teller staffing. Decis Sci 1977; 8: 109–120.

22.

Bechtold

. Implicit optimal and heuristic labor staffing in a multi-objective, multilocation environment. Decis Sci 1988; 19: 353–372.

23.

Dahmen

Rekik

Soumis

, et al. A two-stage solution approach for personalized multi-department multi-day shift scheduling. Eur J Oper Res 2020; 280: 1051–1063.

24.

Schoenfelder

Bretthauer

Wright

, et al. Nurse scheduling with quick-response methods: improving hospital performance, nurse workload, and patient experience. Eur J Oper Res 2020; 283: 390–403.

25.

Van den Bergh

Belien

De Bruecker

, et al. Personnel scheduling: a literature review. Eur J Oper Res 2013; 226: 367–385.

26.

Harper

Powell

Williams

. Modelling the size and skill-mix of hospital nursing teams. J Oper Res Soc 2010; 61: 768–779.

27.

Campbell

. A two-stage stochastic program for scheduling and allocating cross-trained workers. J Oper Res Soc 2011; 62: 1038–1047.