This paper is devoted to the study of a resource-constrained scheduling problem which arises in relation to the operability of certain high availability real-time distributed systems. After a brief survey of the literature, we prove the NP-hardness of the problem and exhibit a few polynomial special cases. We then present a branch-and-bound algorithm for the general case along with computational results demonstrating its practical relevance. The paper is concluded by a discussion on further research.
Citation
Report no PE/BSC/INF/015593, Nortel GSM Access R&D, october 2006. To appear in the European Journal of Operational Research.