Balancing Workload Fairness in Task Assignment: Modeling via Piecewise Linear Approximation

This paper investigates a fairness-aware task assignment problem, where traditional models prioritize operational effectiveness while overlooking workload fairness. Motivated by real-world airport operations, we propose a multi-objective task assignment model that penalizes deviations between actual and expected workloads. Expected workloads are computed from the aggregated task density over each shift’s time window. To capture the nonlinear nature of perceived unfairness, we define the imbalance cost using a quadratic penalty function. We develop three piecewise linear approximations to solve the model efficiently and further simplify them by exploiting convexity to remove binary variables. Experiments on real-world data from a major airport in China show that the proposed methods significantly reduce solution time while preserving solution quality. Under a one-hour time budget, the piecewise linear approximation models achieve up to 5.12% cost savings in large-scale instances compared to the original nonlinear model. Moreover, our proposed fairness-aware task assignment model yields substantial improvements in workload balance (over 90%) at a limited cost to service quality (approximately 20%), even with small imbalance penalties.