Colloquium Speaker

Speaker: Moshe Dror
Management Information Systems, University of Arizona
Topic:'Strong' - 'Weak' Precedence in Job Scheduling
Date:Tuesday, January 16, 2001
Time:11:00 AM
Place:Gould-Simpson, Room 701


Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 10:45 AM


ABSTRACT


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.