Optimization Online


On the Complexity of Scheduling with Elastic Times

Celso Ribeiro (celso***at***inf.puc-rio.br)
Eric Sanlaville (eric.sanlaville***at***math.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society