On the Complexity of Scheduling with Elastic Times
Celso Ribeiro (celsoinf.puc-rio.br)
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.
Entry Submitted: 10/12/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|