On the Complexity of Scheduling with Elastic Times

Celso Ribeiro (celsoinf.puc-rio.br)
Eric Sanlaville (eric.sanlavillemath.univ-bpclermont.fr)

Abstract: 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.

Keywords: Scheduling, hypermedia documents, elastic times

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Integer Programming (0-1 Programming )

Citation: Research report, 2002.

Download: [Postscript]

Entry Submitted: 10/12/2003
Entry Accepted: 10/12/2003
Entry Last Modified: 10/12/2003

Modify/Update this entry