Learning-based Scheduling

Authors: Siddharth Nayak

Integer programs provide a powerful abstraction for representing a wide range of realworld scheduling problems. Despite their ability to model general scheduling problems, solving large-scale integer programs (IP) remains a computational challenge in practice. The incorporation of more complex objectives such as robustness to disruptions further exacerbates the computational challenge. With the advent of deep learning in solving various hard problems, this thesis aims to tackle different computationally intensive aspects of scheduling with learning-based methods. First, we apply reinforcement learning (RL) to the Air Force crew-scheduling problem and compare it against IP formulations which explicitly optimize for minimization of overqualification and maximization of training requirements completed. We show that the RL agent is equally effective as its IP counterpart when the reward function is engineered according to the objective we want to optimize. We also show that the RL formulation is able to optimize for multiple objectives with simple modifications to the reward structure, whereas the IP methods require separate formulations for their objective functions. Then we present Neural network IP Coefficient Extraction (NICE), a novel technique that combines reinforcement learning and integer programming to tackle the problem of robust scheduling. More specifically, NICE uses reinforcement learning to approximately represent complex objectives in an integer programming formulation. We use NICE to determine assignments of pilots to a flight crew schedule so as to reduce the impact of disruptions. We compare NICE with (1) a baseline integer programming formulation that produces a feasible crew schedule, and (2) a robust integer programming formulation that explicitly tries to minimize the impact of disruptions. Our experiments show that NICE produces schedules that are more robust to disruptions than the baseline formulation, with computation times that are lower than those of the corresponding robust integer program. [PDF]