A heuristic neighbourhood search-based algorithm for the solution of resource-task network scheduling problems

There are many challenges facing the widespread industrial deployment of scheduling solutions. These include to find a generic scheduling model that can be applied to a broad variety of scenarios, and to design algorithms that can provide good quality solutions in industrially relevant time frames. The discrete-time Resource-Task Network (RTN) is a generic scheduling framework that has been successfully applied to many different problems. However, RTN models can quickly become intractable as problem size increases. In this work, an iterative neighbourhood-search based algorithm is developed in order to speed-up the solution of RTN scheduling models. The speedup is achieved by limiting the binary variables of a subproblem to a specific neighbourhood in a way that allows the algorithm to iteratively move towards better solutions. Results show that this approach is able to tackle problems that are intractable for a full-space model while still finding near optimal solutions.