The Terminological Scheduling Language RS and its Complexity

Abstract

We define a language RS, a subclass of the scheduling language RSV (resource constrained project scheduling with variant processes). RS involves the determination of the starting times for ground activities of a project satisfying precedence and resource constraints, in order to minimize the total project duration. In RS ground activities and two structural symbols (operators) ‘seq’ and ‘pll’ are used to construct activity-terms representing scheduling problems. We consider three different variants for formalizing the RS-scheduling problem, the optimizing variant, the number variant and the decision variant. Using the decision variant we show that the problem RS is NP-complete. Further we show that the optimizing variant (or number variant) of theRS-problem is computable in polynomial time iff the decision variant is computable in polynomial time.