کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652729 | 1632595 | 2010 | 8 صفحه PDF | دانلود رایگان |
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.
Journal: Electronic Notes in Discrete Mathematics - Volume 36, 1 August 2010, Pages 191-198