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.

Projects: