We consider the problem of scheduling hypermedia documents with elastic times. The objects have variable durations characterized by ideal, minimum, and maximum values. A schedule is a set of tensions on the arcs of the precedence graph which also represents synchronization constraints. We consider the problem of deciding if there exists a schedule in which the durations of at most a given number of objects is not set at their ideal values. We prove the NP-completeness of this problem, which is also NP-complete for series-parallel graphs.
Citation
Research report, 2002.