We created the IBM Crew Pairing and Rostering Optimization (C-PRO) solution for air crew scheduling. It was deployed at El Al in 2013 and at Aeroflot in 2020. The core of the system is an optimization flow, which models the problem using mixed integer linear programming (MILP) with millions of integer variables. The solution is derived iteratively using heuristics. Most recently, we applied Markov Decision Process (MDP) in place of the heuristics orchestrator and realized a 30% improvement in performance.