Lagrangian relaxation-based lower bound for resource-constrained modulo scheduling

In this work we propose a Lagrangian relaxation of a time indexed integer programming formulation to compute a lower bound for the resource-constrained modulo scheduling problem (RCMSP). Solving the RCMSP consists in finding a 1-periodic schedule minimizing the period subject to both temporal and resource constraints. This work is inspired by Möhring et al results [Möhring, R.H., A. S. Schulz, F. Stork and M. Uetz Solving Project Scheduling Problems by Minimum Cut Computations, Management Science. 49 (2003), 330–350] for the (non cyclic) resource constrained project scheduling problem, where each subproblem solved within the subgradient optimization is equivalent to a minimum cut problem. Experimental results, presented on instruction scheduling instances from the STMicroelectronics ST200 VLIW processor family, underline the interest of the proposed method.