contents
|
|
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 on
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.
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.
More detailed information on our scheduling projects:
|
top