A simple continuous-time process scheduling formulation and a novel solution algorithm

We present a simple, yet general mathematical programming formulation for optimal scheduling of processes represented as Resource-Task Networks. The formulation is based on a continuous representation of time and leads to a mixed integer linear programming (MILP) problem. In common with other continuous-time scheduling formulations, this exhibits a large integrality gap that renders its solution using standard branch-and-bound algorithms highly problematic. A novel branch-and-bound algorithm that branches on both discrete and continuous variables is proposed to address this complication.