Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 18, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Berit Johannes
AND/OR-networks are an intriguing generalization of ordinary precedence constraints and occur in various scheduling contexts. AND/OR-networks consist of traditional AND-precedence constraints, where a job can only be started after all its predecessors are completed, and OR-precedence constraints, where a job is ready to be scheduled as soon as any one of its predecessors is completed. The earliest start time scheduling problem consists of finding the non-negative component-wise minimal schedule that satisfies all AND/OR- constraints. The corresponding feasibility problem is known to be in NP and co-NP, but its actual complexity status has remained unknown. We will discuss some special cases for which polynomial-time algorithms have been proposed and provide some insights into the difficulties of the general problem.
Automatic MiSe System Software Version 1.4803M | admin login