MULTI-PERIOD STAFFING SCHEDULING OPTIMIZATION BASED ON COLUMN GENERATION AND NETWORK FLOW ALGORITHMS
Keywords:
Column generation, Network flow, Staffing scheduling, Mixed integer programming, Branch-and-priceAbstract
This study develops an algorithmic staffing-scheduling framework for multi-day, multi-group, and multi-period service systems. The model minimizes temporary workforce size while satisfying hourly demand, eight-hour work-pattern rules, and individual assignment restrictions. A fixed-group mode is first modeled through column generation, where a restricted master problem is iteratively expanded by work patterns with negative reduced cost. A flexible mode is then formulated for single-group-per-day service with cross-day reassignment. It introduces employment variables, group assignment variables, pattern variables, and a pricing subproblem represented as a minimum-cost maximum-flow network with node-capacity constraints. MATLAB implementation and branch-and-price obtain a 406-worker solution for the flexible mode, reducing the benchmark workforce by 18 workers and improving allocation efficiency by 4.25%. Visual results verify demand coverage, feasible work calendars, mode-frequency alignment with demand peaks, and balanced workforce distribution across groups and days.References
[1] Qiu Z, Hu X, An S. Robust collaborative scheduling optimization for multiple electric bus routes under stochastic traffic conditions. Transportation Research Part C: Emerging Technologies, 2026, 182: 105455.
[2] Cheng H, Zhang X, Yang P, et al. Scheduling optimization of a regionally integrated energy system based on an improved multi-objective particle swarm algorithm. Energy Reports, 2025, 14: 3888-3904.
[3] Huang C, Wang S, Zheng J, et al. Corrigendum to “Ship formation scheduling optimization for the multi-compound channel with deterministic and uncertain arrivals” [Ocean Engineering 342 2 30 (2025) 122815]. Ocean Engineering, 2025, 340(P1): 123114.
[4] Zhou X, Chen Z, Huang M, et al. A collaborative evolution algorithm for unmanned equipment project distributed scheduling optimization with grouping and due window constraints. Expert Systems with Applications, 2026, 296: 129143.
[5] Cao Z, Qian T, Zhang S, et al. Multi-Port Liner Ship Routing and Scheduling Optimization Using Machine Learning Forecast and Branch-And-Price Algorithm. Journal of Marine Science and Engineering, 2025, 13(11): 2163.
[6] Lin P. Fuzzy based priority aware task scheduling optimization for mobile edge computing environments. Scientific Reports, 2025, 15(1): 39998.
[7] Du B, Tang A, Ye H, et al. Collaborative Vehicle-Mounted Multi-UAV Routing and Scheduling Optimization for Remote Sensing Observations. Drones, 2025, 9(11): 783.
[8] Wu Y, Li C, Li X, et al. Battery energy storage system scheduling optimization based on temperature difference mitigation within module. Journal of Energy Storage, 2025, 140(PB): 119159.
[9] Zhou Y, Jiang J, Shi Q, et al. GA-HPO PPO: A Hybrid Algorithm for Dynamic Flexible Job Shop Scheduling. Sensors, 2025, 25(21): 6736.
[10] Chen Q, Lu J, Dang C. Multi-Timescale Scheduling Optimization of Hospital Integrated Energy Systems for Intelligent Energy Management. Electronics, 2025, 14(21): 4273.