Discrete Modeling and Combinatorial Optimization for Task Scheduling

Abstract

This paper investigates centralized scheduling of mobile service agents under staggered multi-wave task arrivals, limited service capacity, service-time windows, and cross-wave capacity reservation requirements. A spatiotemporal candidate-arc representation is developed to discretize the continuous scheduling process, where each arc encodes an agent-task-time triple along with predicted service points, approximate paths, endurance consumption, and execution costs. Based on the feasible arc set, a mixed-integer linear programming (MILP) model is formulated to jointly optimize task coverage, standby-agent activation, coordinated service times, spatiotemporal conflict avoidance, and cross-wave capacity reservation. Numerical experiments are conducted on a 3-wave, 37-task benchmark as well as extended scenarios with varying resource scarcity and task scales. Results show that in multi-wave rolling execution, the MILP strategy achieves a total weighted coverage rate of 71.19%, outperforming the nearest-neighbor greedy baseline by 5.56 percentage points; the advantage is most pronounced in the second-wave peak (+17.07%), directly validating the capacity reservation mechanism. Further sensitivity analysis reveals that the optimization gain of MILP is resource-sensitive—significant under abundant resources and gradually converging under extreme scarcity. The reported results demonstrate how global constrained selection balances current weighted coverage against retained service capacity for subsequent waves, and provide quantitative references for practical parameter tuning.