Scheduling Check-in Staff with Hierarchical Skills and Weekly Rotation Shifts

，，

1.College of Computer Science and Technology，Civil Aviation University of China，Tianjin 300300，P.R.China；2.Information Technology Base of Civil Aviation Administration of China，Civil Aviation University of China，Tianjin 300300，P.R.China

（Received 10 June 2020；revised 30 June 2020；accepted 30 July 2020）

Abstract: The paper aims to schedule check-in staff with hierarchical skills as well as day and night shifts in weekly rotation. That shift ensures staff work at day in a week and at night for the next week. The existing approaches do not deal with the shift constraint. To address this，the proposed algorithm firstly guarantees the day and night shifts by designing a data copy tactic，and then introduces two algorithms to generate staff assignment in a polynomial time.The first algorithm is to yield an initial solution efficiently，whereas the second incrementally updates that solution to cut off working hours. The key idea of the two algorithms is to utilize a block Gibbs sampling with replacement to simultaneously exchange multiple staff assignment. Experimental results indicate that the proposed algorithm reduces at least 15.6 total working hours than the baselines.

Key words:check-in staff scheduling；hierarchical skills；weekly rotation shifts；block Gibbs sampling

0 Introduction

The paper is inspired by the issue of scheduling check-in staff at Air China to serve the flights from ten alien airlines at Beijing Capital International Airport. These airlines include Korean Air，Iranian Airways and so on. That staff assignment should reach the maximum of job satisfaction and meet the requirements of hierarchical skills. The job satisfaction mainly refers to minimum staff hours per week as well as day and night shifts in weekly rotation.That shift ensures staff work at day in a week and at night for the next week，which is an essential constraint for the rostering issues with all-day operators on duty. Skill requirements mean that a flight demands staff with hierarchical skills. Hierarchical skills［1］represent hierarchical structure of skills due to different degree of staff’s expertises and experiences. Higher skilled staff can engage in tasks with lower skills.

The existing workforce planning is manually generated and often cannot fulfil skill requirements.In addition，the method on planning check-in staff［2］could not yet address the practical issue since it was built on binary skills rather than hierarchical ones.Moreover，that algorithm did not consider the constraint of day and night shifts in weekly rotation. To tackle the issue，the proposed algorithm firstly designs a shadow data copy tactic to guarantee the weekly rotation shifts，and then formulates the issue as a nonlinear programming problem. That formulation is optimized via a block Gibbs sampling with replacement to simultaneously exchange multiple staff assignment. More precisely，Kindividuals are randomly removed from a flight afterKstaffs are randomly added to that flight. The replacement would sample a good solution from 22Kcandidates. The time complexity isO(#iteration×#flights×(#staffs+#skills)). The symbols #iteration，#flights，#staffs，#skills denote number of iterations，number of flights，number of personnels and number of skill levels. Experimental results on the dataset from Air China indicate that the improvements over the manual allocation are 25.2% and 18.3% in terms of total working hours，effective working hours，respectively. It is worthwhile noting that the proposed algorithm could be also applied to other scheduling issue constrained by hierarchical skills as well as day and night shifts in weekly rotation，such as nurse rostering and scheduling staff oncalls.

1 Related Work

1.1 Personnel scheduling constrained by skills

Personnel scheduling has gained increasing attention due to its widespread applications for various organizations，such as airlines［2］，retailers［3］and health-care organizations［4］. Personnel scheduling aims at assigning staff efficiently and effectively to tasks. Tasks generally represent the workload in a planning horizon and demand specific skills.Skill is a major component for personnel scheduling［1］. Skill can be interpreted as the expertise of a person performing a task well and is divided into two classes:The categorical class and the hierarchical class. The categorical class indicates no ranked order among skills［5-6］. Krishnamoorthy et al.［6］emphasized importance of shifts by minimizing cost incurred by number of shifts. Golalikhani et al.［7］stated bounds of working time for skilled staff. The hierarchical class implies hierarchical structure for skills due to different degree of staff experiences［1］，which is denoted by skill levels. Staff with higher skill can work on tasks demanding lower skills. Firat et al.［8］proposed a branch-and-price approach to yield a stable schedule that no pairs of person and tasks could be better replaced for the current schedule.

1.2 Personnel scheduling using Monte Carlo methods

Monte Carlo is usually employed to solve personnel scheduling for its easy implementation. Scipione et al.［9］scheduled staff on-call by repeating twophase sampling. The first phase was sampling an unassigned task according to task priorities，while the second was sampling a person for that task according to the objective function. Cheng et al.［10］utilized Monte Carlo tree search to optimize staff scheduling for emergency department in the health care industry. Its advantage lied in better selecting the sampling node based on the upper confidence bound.Zülch et al.［11］attained a solution and tuned it by Monte Carlo simulation.

2 Main Algorithm

2.1 Notation definition

The set ofHalien airlines denotes byΛ={Λ1，…，ΛH}. An alien airlineΛhis specified with a hierarchical skill domainindicates th ekth level of skill，andnhis the number of skill levels. There is relative ranked order among skill levels. Higher skilled staff can take part in tasks at lower levels.

The notationΩ= {(sjk，fjk，γjk)|j=1，…，7；k=1，…，mj} denotes a weekly flight schedule. The indicesj，kdenote the day and the flight，respectively.mjis the number of fights at thejth day.Λjk∈Λis the alien airline.cjk∈{0，1} indicates whether the job of checking-in occurs at day or night，and equals to one if occurrs at daytime. The daytime for check-in staff refers to working time from 06:00 am to 08:00 pm.sjk，fjkdenote starting time and finishing time of checking in.γjkis the required numbers of skill levels.

Hierarchical skills of staff denote byY={∈{0，1}|i=1，…，M；j=1，…，7；k=1，…，mj}.indi cateswhether theith person masters thetth level ofskill fort hekthflight atthejthday.If=1，The optimization variablexijk∈{0，1} indicates whether theith person serves thekth flight at thejth day.

2.2 Modeling day and night shifts

To guarantee day and night shifts in weekly rotation，a data copy tactic is designed. The idea is:（1）Constructing a scheduleΩ′={(Λjk，cjk，sjk，fjk，γjk)|j=8，…，14}from the scheduleΩby conversing the occurring timecjk. That isj∈[8，14]，Λjk=

Λj-7，k，sjk=sj-7，k，fjk=fj-7，k，γjk=γj-7，k，cjk=1-cj-7，k；（2）assigning staff to the schedulesΩ∪Ω′.The day and night shifts would be satisfied if and only if an algorithm works out the flight schedulesΩ∪Ω′. The proof is simply stated as follows. Suppose all staff can be divided into two nonintersecting setsU1andU2，who work at day and night，respectively. It implies that staff inU1spend a week on daytime flights fromΩand fromΩ′at the next week. As the occurring time is opposite forΩ′andΩ，daytime flights fromΩ′are essentially the nighttime flights fromΩ. As a result，staff inU1work for daytime flights fromΩat a week and nighttime flights fromΩat the next week. The above inference also holds true forU2.

2.3 Optimization objective

After modelling weekly rotation shifts in Section 2.2，the scheduling issue can be formulated as a task of assigning staff toΩ∪Ω′by solving the problem in Eqs.（1）—（9）.

Eq.（1）trades off the total working hours in two weeks，working fairness and the penalties for exceeding bounds on working hours and days.Working fairness states staff working hours deviating from the average working hour.α，β∈[0，1] are trading-off parameters and manually tuned. Eq.（2）gives the way to compute working hours for theith person at thejth day，equal to the time interval between the starting time of his/her earliest flight and the finishing time of his/her latest flight. Eq.（3）computes the average working hours in two weeks.Eq.（4）highlights quadratic losses for exceeding the rational working hours and days. Eq.（5）calculates the total working hours or day for theith person.Eq.（6）shows the demand of skill levels for each flight. Eq.（7）figures out that staff assigned for a flight should be equal to the demand. It prevents assigning more persons to flights，which wastes superfluous labors. Eq.（8）ensures that staff alternatively work at day or night for a week. Eq.（9）means that each staff assignment is a binary decision and equals to one if allocated.

The ratio of the feasible solutions for Eqs.（1）—（9）is far less than 2-M×N.M，Ndenote the number of persons and the number of flights in the flight scheduleΩ，respectively. The above statement is easily proved by just considering the constraints in Eqs.（8）—（9）. The data copy tactic in Section 2.1 implies that the number of flights during the day and the night is the sameN. Due to each staff assignment being a binary decision，the total scale of solutions is (22N)M. Meanwhile，weekly rotation shifts in Eq.（8）permits an employee only work daytime or nighttime flights. The scale of feasible solutions is(2N)Mand the ratio is thus 2-M×N. The ratio would decrease by imposing constraints in Eqs.（6）—（7）.

2.4 Optimization using block Gibbs with replacement

To optimize Eqs.（1）—（9），Algorithm 1 gets an initial solution from Algorithm 2，and then iteratively updates that solution until it reaches the maximum iteration. At each iteration it firstly employs the backtracking mechanism to determine the day or night shift of a person，and then utilizes a block Gibbs sampling with replacement to randomly sample assignment ofKpersons with replacement. That replacement results in exchanging assignment of 2Kstaff and then 22Kfeasible solutions. On the contrary，the existing Monte Carlo methods［8-10］sampled from two candidates.

Algorithm 1Scheduling staff using block Gibbs

Input:flight scheduleΩ；staff skillsY；iterations #iter，

trade-off parametersα，β；temperatureT；decay factorλ；block sizeK

Ω′←DataCopy(Ω)in section 2.1

xijk←Algorithm2（Ω）//get an initial solution

forniter=1 to #iter do

fori=1 toMdo

for all flightFjk∈Ω∩Ω′do

end for

end for end for end for

return staff assignment{xijk}

2.5 Quick generation of an initial solution

Algorithm 2 designs a two-phase process to generate an initial solution satisfying constraints in Eqs.（6）—（9）. The first phase is to solve a relaxed problem，referred to Eqs.（10）—（11）. The relaxed problem drops the constraint in Eq.（7），and treats Eq.（6）as optimization objective and Eqs.（8）—（9）as constraints. At that time，the optimization variables for the relaxed problem degenerates from staff assignmentsxijkto staff shiftwi.That formulation highly speeds optimization since the number of variables are cut fromM∑mjtoM.

The indicator functionI[A] in Eq.（11）outputs one ifAis true and otherwise zero. Eq.（10）gets the maximum ∑γjktif all flights are assigned enough skill levels. Otherwise，there is lack of staff to cover skill requirements. Algorithm 2 can thus solve the issue of forecasting the staff demand［1］，which is a popular operational research problem.

As the relaxed solution attained in the first phase does not satisfy the constraint in Eq.（7），the second phase is introduced to ascertain the truth of Eq.（7）by removing unnecessary labors from flights.

Algorithm 2Quick generation of an initial solution

Input:flight scheduleΩ；staff skillsY；iterations #iter，

3 Theoretical Analysis

3.1 Complexity analysis

At each iteration，Algorithm 1 costs Θ(N×max|γjk|) time in sampling the shift of an employee，and then Θ(N) in sampling the assignment for that person. That operation repeats forKemployees and#iter iterations. The time complexity of Algorithm 1 is thus Θ(#iter×N×(M×K+max|γjk|)). Similarly，the computational complexity of Algorithm 2 isO(#iter×N×M×K). The total time complexity of the proposed algorithm isO(#iter×N×(M×K+max|γjk|)).

3.2 Analysis of sampling efficiency

Sampling efficiency is analyzed due to its impact on the goodness of the solutions. Higher sampling efficiency owes to larger scale of feasible solutions but smaller times of sampling，which helps an algorithm find a better solution from large-scale candidates. As Algorithm 2 quickly yields an initial solution，the main component of the sampling efficiency lies in Algorithm 1.

At each iteration Algorithm 1 undertakes a sampling to designate a shift，and then takes a sampling for every daytime or nighttime flight. Since the number of the daytime or nighttime flights are bothN，the total sampling times are #iter×(3N+1). It would outputK，K))feasible solutions. The“2”in that formula is from the binary sampling whether theith person is assigned to the flightFjk.C(Mi-Mjk，K)is the size of selectingKpersons from the set ofMi-Mjkwho do not work on the flightFjkbut possess the same shift.C(Mjk+K，K)is the scale of removingKpersons from a set ofMjk+Kemployees working on flightFjk.Miis the number of employees whose shifts are same to theith person.Mjkis the number of employees required for the flightFjk.

4 Experiment and Results

4.1 Experiment setting

4.1.1 Dataset

The dataset consists of a weekly flight schedule and staff’s skills. The flight schedule is composed of 23 daytime flights and 26 nighttime flights. The flight attributes are flight number，checking-in occurring at day or night，arrival time and departure time and number of skill levels on demand，as listed in Table 1. Skill levels of 39 employees on ten alien airlines are presented in Table 2. These airlines include Korean Air（abbreviated as KE），Iranian Airways（abbreviated as IR）and so on. Meanwhile，the digits three，two，one and zero denote four skill levels:Leader，controller，common and non-skill，respectively. Leader skill is the most priority and non-skill implies absence of skills.

Table 1 Flights from a weekly flight schedule

Table 2 Hierarchical skills of an employee on ten alien airlines

4.1.2 Parameter setting

In the experiments six parameters are manually tuned. The trade-off parametersα，βtake 0.05，0.33，0.5 and 0.95. The maximum iteration #iter is 200，400. The size of block Gibbs with replacementKtakes 1，3，5，10 and 20. The parametersφandφdenote the rational interval of working days in a week. That bound is［32，38］at daytime and［24，32］at nighttime. The preferred working days[φ，φ] for a person at a week is［3，5］. The temperatureTand decay factorλtakes 100 and 0.99，respectively.

4.1.3 Baselines

The first method is a history staff assignment manually generated by Air China，abbreviated as Manual. The second is the latest method of scheduling staff with hierarchical skills by branch-andprice［7］，abbreviated as BP. The third method is personnel scheduling approach using Monte Carlo simulation［8］，abbreviated as MC. MCTS is denoted by the staff rostering using Monte Carlo tree search［9］. It is noting that the methods BP，MC and MCTS do not consider day and night shifts in weekly rotation.Nevertheless，to compare their performance，the baselines conduct the experiments on the flight schedules generated by the data copy tactic in Section 2.1.

4.1.4 Evaluation measures

Four evaluation metrics are total staff working hours（WH），effective working hours（EWH），working fairness（WF）and working days（WD）.Working fairness states staff working hours deviating from the average working hour.

4.2 Performance comparison

The proposed algorithm is tested with four sets of trade-off parametersα，β. The proposed algorithm withα=1，β=0 only minimizes the total working hours. The parameter settingα=0.5，β=0 focuses on the minimization of the total working hours and the penalties for those beyond the bounds.Another parameter settingα=0.95，β=0.05 shows the minimization on the total working hours as well as working fairness，and does not consider the loss incurred by exceeding the reasonable intervals. The last parameter combinationα=β=0.33 considers all loss and gives the same importance.The proposed algorithm with the above parameter settings yield staff assignment with combination of other parameters #iter=200，T=100，λ=0.99，K=1.

Table 3 reports performance comparison. The proposed algorithm withα=1，β=0 achieves the smallest total working hours and the effective working hours. The improvements over the baselines are respectively at least 1.9% and 0.9%. Specifically，the improvements over the manual allocation are 25.2%，18.3% in terms of WH and EWH，respectively. However，it obtains high bias against working fairness and working days. There are 23 persons whose working days are in［11，14］and ten employees in［0，6］.

Table 3 Performance comparison on two-week schedules

The proposed algorithm withα=β=0.33 obtains more attractive performance for the practical issue. The working days within two weeks for staff are bounded in［6，10］. The improvements over the baselines are 0.87% and 0.45% in terms of WH and EWH. Specially，the proposed algorithm shortens at least 15.6 and 7.8 h on WH and EWH.

4.3 Comparison on sampling efficiency

As sampling efficiency impacts on the quality of the solutions，the sampling efficiency is empirically analyzed，shown in Fig.1. Compared to MC and MCTS，Fig.1 shows that the proposed algorithm converges in 10 s，whereas MC and MCTS become steady after 20 s.

Unlike BP allows flights being assigned more persons than the demand，the proposed algorithm sets two quantities equal，referring to Eq.（7）. That equality prevents allocating superfluous labors for flights.

Fig.1 Comparison on sampling efficiency

5 Conclusions

To schedule the check-in staff with hierarchical skills and weekly rotation shifts，a data copy tactic and two algorithms using block Gibbs sampling are designed to solve the issue in a polynomial time.Contrary to Monte Carlo algorithms，the proposed algorithm achieves higher sampling efficiency with the same consumption of time and space. Experimental results show that the proposed algorithm outperforms the traditional methods.