Research On Algorithms For Personnel Scheduling In Airport Transit Service With Multiple Peaks

There is an inevitable tradeoff between coverage of tasks and utilization of human resources in service industrials that experiences multi-peak in a day.To cover all tasks in peak period,a large number of staff are required and many of them are idle during off-peak time.To fully utilize every staff will leave some of the tasks uncovered.A large airport in China resolve this issue by introducing bi-part shifts,where some staff will first serve some tasks in a peakperiod,then return home and take a rest and come back again to serve other tasks in another peak-period.The optimization objective is to reduce the number of unassigned task while keep the number of bi-part shifts under a specified threshold.This study adopts a two stage solves the personnel scheduling problem with bi-part shifts in two stages.A mixed integer linear programming model is employed to generate shifts in first stage,where the model is capable to handle both normal shifts and bi-part shifts.The shift generation stage must generate not only high quality normal shifts but also a specific number of high quality bi-part shifts.To generate a normal shift,the task with highest priority according to some measures are selected as the beginning of the shift,an algorithm similar to shortestpath are employed to select as many tasks as possible and insert them into the shift.We then proceed to concatenate normal tasks into bi-part shifts until a specified number of bi-part shifts are generated.Based on the shifts generated in first stage,a set-cover model is employed to assign shifts to personnel in second stage.To minimize the number of unassigned tasks,this stage attempt to maximize the number of shifts assigned to personnel under two constraints:first,each person must have certain number of days off;second,there must be enough rest time between every two consecutive shifts.Three algorithms are proposed in this study: 1)greedily assign shifts to staffs;2)greedily assign staffs to shifts;3)simultaneously assign shifts and staffs.The first two algorithm will process either staff or shifts according to a priority list,whereas the third algorithm seeks for globally optimal solution by considering shifts and staffs at the same time.Numerical experiments are conduct to evaluates the effectiveness of proposed algorithms based on 24 sets of real data and 72 sets of Generated data from airport.First,the four different prioritization polices in shift generation are tested by 24 sets of real data.Given different thresholds of bi-part shifts,trying all three algorithms for assign shifts,the police of prioritizing tasks by number of simultaneous tasks achieves the smallest number of unassigned tasks.Second,the three algorithms for assigning shifts are tested.Among the 24 sets of real data and72 sets of Generated data,Computational results suggest that simultaneously assignment shifts to staffs performs better than the other two algorithms when there are many bi-part shifts.When the number of bi-part shifts increases from 0 to 30,the result of the real example of the airport is to reduce the number of 56 unassigned person of tasks,which is of great significance to improve the management efficiency.