Solving a dynamic remote operations scheduling problem: a multi-level periodic predictive-reactive rescheduling policy.

We present an effective and efficient solution approach for addressing a dynamic scheduling problem encountered by a large international company. The company needs to assign projects to remote technicians and schedule the associated tasks over a shifting planning horizon while minimizing changes to the plans agreed upon with customers, as new projects and tasks arrive over time and need to be allocated within the existing schedule. This process must take into account technician skills, project families, task release dates, deadlines and precedence constraints, and the joint execution of common tasks requiring multiple technicians. We formulate the static problem as a mixed-integer linear program (MILP), aiming to minimize makespan in a parallel and identical machine system. Following the three-field notation by Graham et al. (1979) we are interested in the P_m | fmls, r_j , d_j , M_j , prec | Cmax problem. To address the dynamic aspect, we propose a periodic predictive-reactive rescheduling policy Vieira et al. (2003), based on a rolling horizon approach (Chand et al., 2003), that focuses on generating a baseline schedule and then, in a periodical reactive way, “repairing” it to accommodate new incoming tasks. The rescheduling repair process involves a multi-level approach with four levels of adjustments to systematically integrate new information with increasing degrees of perturbation in the current schedule. To align with the company’s goal of minimizing plan changes, we progressively attempt partial reschedules before resorting to full rescheduling. For instance, in the first level, no disruptions are permitted when integrating new arrival tasks, while in the fourth level changes in start times and assignments are admitted, but at the cost of a penalty. To assess scalability, we validate our algorithm using both real-world and synthetic instances, demonstrating its efficiency and effectiveness in reaching optimality in most cases. Additionally, we provide valuable managerial insights for the company.