Abstract: Scheduling algorithms are designed to optimize many optimality criteria in a wide variety of scheduling models. To design an algorithm that is specialized to one paricular problem/object is well-motivated and justified, as an algorithm that works well for one scheduling problem/objective may perform poorly on a different scheduling problem/objective.
We give very general results about the existence of schedules which simultaneously minimize two criteria. We will focus mainly on results that apply to almost any scheduling environment, and apply to all pairs of metrics in which the first metric is one of maximum flow time, makespan, or maximum lateness and the second metric is one of average flow time, average completion time, average lateness, or number of on-time jobs. We will show that for almost all such pairs of metrics there exist schedules which are simultaneously close to optimal for both metrics.
We will also discuss algorithms for simultaneously optimizing two metrics.
Colloquium - 16:00
Abstract: An instance of the resource-constrained project scheduling problem can be represented by a set V of jobs, with integral processing times, a precedence digraph D=(V,A), and a set F={F_1,..., F_k} of minimal forbidden sets, representing various resource constraints. Every such minimal forbidden set F in F is a set of precedence-unrelated jobs that cannot be scheduled simultaneously but every proper subset can. The objective is to minimize the makespan, i.e. the latest completion time of any job. To resolve the resource conflicts, we select a waiting job j in F for every minimal forbidden set. Such a selection s=(j_1,...,j_k) can be represented by a so-called AND/OR-network N, which contains the precedence digraph D as a subgraph. If the selection s is feasible it induces a well defined schedule, which can be computed efficiently in the network N. Ignoring the resource conflicts, the problem reduces to finding the makespan subject to the precedence constraints represented by D. In an acyclic digraph the makespan is determined by at least one "longest path" in the graph. The jobs on such a path are often called critical. These critical jobs have the property that any increase in the processing time of one of them results in an increase of the makespan. Unfortunately one cannot identify a simple longest path or a single critical job in an AND/OR-network in general. However it is possible to detect critical sets of jobs. We will present three different definitions of "criticality" and show the connections between them. It turns out that two of these definitions form a blocking pair of clutters.