Management Information Systems, University of Arizona
|Topic:||'Strong' - 'Weak' Precedence in Job Scheduling|
|Date:||Tuesday, January 16, 2001|
|Place:||Gould-Simpson, Room 701|
Abstract : It is common knowledge that most applied combinatorial problems which involve partial orders are NP-hard. Special cases of partial orders have been considered in great detail, permitting us to focus on a particular interesting order distinction. We will analyze the partial order delineation of 'strong' and 'weak' precedence in chain and tree structures.
In this talk we present a summary of recent results regarding NP-hardness and polynomial time solvability for the distinction between 'strong' and 'weak' precedence in scheduling. In many cases, NP-hardness for weak precedence imples NP-hardness for the strong precedence. However, this is not universally true, and the 'strong' - 'weak' distinction is proper at least for the case of chains. We primarily focus on the results for chains and trees but extend the strong - weak precedence distinction to more general digraphs grounded in and motivated by actual real-life dispatching in multiprocessing systems which require stable schedules.