On integer linear programming formulations for the resource-constrained modulo scheduling problem.

36p.The resource-constrained modulo scheduling problem (RCMSP) is a general periodic cyclic scheduling problem, abstracted from the problem solved by compilers when optimizing inner loops at instruction level for very long instruction word parallel processors. Since solving the instruction scheduling problem at compilation phase in less time critical than for real time scheduling, integer linear programming (ILP) is a relevant technique for the RCMSP. This paper shows theoretical evidence that the two ILP formulations used by practitioners are equivalent in terms of linear programming (LP) relaxation. Stronger formulations issued from Dantzig-Wolfe decomposition are presented. All formulations are compared experimentally on problem instances generated from real data. In terms of LP relaxation, the experiments corroborates the superiority of the new formulations on problems with non binary resource requirements