An Efficient 2D Genetic Algorithm for Optimal Shift Planning Considering Daily-Wise Shift Formats: A Case of Airport Ground Staff Scheduling

摘要

Owing to the computational efficiency in dealing with combinatorial optimization problems, the genetic algorithms (GAs) have been widely applied to human resource planning and scheduling. Shift planning is of particular importance for personnel scheduling when practical concerns must be taken into account. Daily-wise shift formats are often introduced in practical operations in order to facilitate execution of the planned tasks and accommodate certain managerial convenience. However, the highly repetitive nature of running daily-wise shift formats entails an extreme imbalance of set covering between the tasks and staff availability, which leads to tremendous computational challenges in solving the combinatorial optimization problem that is subject to large redundancy of zero elements. In line with the inherent two-dimensions of shift planning in terms of shift formats and days, this paper proposes a two-dimensional (2D) encoding scheme to implement the GA for efficient shift planning. An application to a real-life airport Ground Staff Scheduling (GSS) problem is presented to illustrate the feasibility and potential of the proposed 2D GA for efficient handling of daily-wise shift formats.