### Scheduling

Sequencing and scheduling is motivated by questions that arise in production planning, in computer control, and generally in all situations in which scarce resources have to be allocated to activities over time. Currently, we investigate deterministic machine scheduling, project scheduling with varying processing times, and applications in chemical engineering.

*Machine scheduling* belongs to the classical models in
scheduling. A machine (or processor) is a resource that can
perform at most one activity at a time. The activities are
commonly referred to as jobs (or tasks), and it is also assumed
that a job is worked on by at most one machine at a time.
Moreover, we assume that all information that defines a problem
instance is known with certainty in advance. Our research on this
model follows essentially two lines. First, we apply the
methodology of polyhedral combinatorics
which is one of the major and most successful approaches to
understand and to solve combinatorial optimization problems.
Second, we develop approximation algorithms
for machine scheduling problems by using polyhedral results,
suitable LP-relaxations, and randomization. Results in this area
also cover more complex scheduling models, e.g. those
incorporating communication delays, a
characteristic encountered frequently in real-world scheduling or
parallel processors.

The urge for flexible scheduling tools requires the study of
*scheduling problems with varying processing times*. We
consider two scenarios: controllable processing times and random
influences. In the first model, the time of processing that a job
receives is controlled via the amount of resources allocated to
it. We study here the discrete version of the classical Time-Cost Tradeoff Problem. In the other model,
random influences lead to stochastic project
scheduling problems, which are of great practical importance,
but very hard to evaluate. We here aim at developing algorithms
that can cope with random influences even in the presence of
resource constraints and to some extend also with stochastic
dependencies. The research on these topics is funded by the German
National Science Foundation (DFG). In another project on stochastic machine scheduling, we
develop approximation algorithms for machine scheduling problems
when processing times are uncertain. In this model, it is generally
assumed that the random variables, or at least their expected values,
are known beforehand.

In another model that deals with limited information, the online scheduling model, the assumption is instead that the instance is presented to the scheduler only piecewise. Hence, decisions must be made without any knowledge of the jobs to come while the job characteristics such as weight and (deterministic) processing time are usually disclosed upon arrival of the job. With the stochastic online scheduling model we introduce a model that generalizes both, the stochastic scheduling model as well as the online scheduling models. Although, it is not obvious whether these strong restrictions allow any online policy to perform well at all, we can prove that such policies exist with performance guarantees matching the currently best known ones of the single settings.

An important feature in *chemical engineering* is the
allocation of scarce resources to very time sensitive production
processes that typically involve schedule dependent time-windows
and due dates. In a collaboration
with BASF Ludwigshafen, we develop algorithms for the
allocation of personnel in such an environment for large-scale
problems.