Workload balancing for flight dispatchers
研究了航班签派员的工作量平衡问题，提出基于拉格朗日松弛和遗传算法的启发式方法，在231个实例中平均偏差仅3.5%，对航空调度优化有参考价值。
Flight dispatchers are responsible for flight planning prior to departure and flight monitoring while en-route. Their work involves multi-tasking and their workload is dynamic. We study such a problem under two nonlinear workload balancing measures: minimum peak workload and minimum absolute deviation. In order to solve practical instances efficiently, we use decomposition through Lagrangian relaxation to reduce the problem into easier-to-solve subproblems and prove that the Lagrangian lower bound has a closed-form expression for the peak workload objective. To find feasible solutions, we develop a Focus-Search-and-Improve heuristic with a genetic algorithm core where parts of the feasible solution set are explored and searched by a genetic algorithm, and solutions are further fine-tuned by an improvement heuristic. To test the efficiency of the proposed approach, we generated 231 instances based on 2019 U.S. Bureau of Transportation flight data that involve 17 different carriers and up to 3968 flights per instance. Numerical testing demonstrates the efficiency of the proposed approach in that the Lagrangian lower bound is very tight, and the heuristic finds optimal solutions in 33.4% of the instances and are on average 3.5% away from the Lagrangian lower bound. It also reveals that the difficulty of the problem increases for smaller workstation-to-flight ratios, and that the peak workload objective achieves the goal of balancing the workload at times where peaks occur but does not necessarily balance the workload throughout the workday. On the other hand, the absolute deviation objective achieves better balance between workstations at the expense of a slight increase in peak workload. • Goal: Assign flight dispatchers to workstations to balance workload during the shift. • Means: Minimize peak workload and absolute mean deviation at every time point. • Model: MIP solved through a Focus-Search-and-Improve heuristic. • Testing: 231 instances involving 17 different carriers and up to 3968 flights per instance.