De-Cycling Cyclic Scheduling Problems

Abstract

An elegant way to tackle a problem that you cannot solve is to cast it to a problem that you can solve very well. Cyclic Scheduling problems are very similar to Resource Constrained Project Scheduling Problems (RCPSP), except that the project activities are repeated over time. Due to the similarity, reducing Cyclic Scheduling problems to RCPSPs seems an appealing approach. In this paper we discuss four methods to perform the reduction. The first two are existing techniques. The remaining ones are novel and include the first (to the best of our knowledge) equivalent RCPSP formulation of a cyclic problem. We compare the presented approaches in an experimental evaluation.