Lectures and Colloquia during the semester

**June 11, 2001**

Technische Universität Berlin

Straße des 17. Juni 136, 10623 Berlin

Math building - Room MA 042

** Lecture - 14:15**

### Cliff Stein - Dartmouth College

### Scheduling to simultaneouly optimize two criteria

*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**

### Vanessa Kääb - Technische Universität Berlin

### Critical Sets in AND/OR-Networks

*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.

[top]