### Inhalt des Dokuments

# Throughput Maximisation for Screening Processes

### From Fachgebiet Regelungssysteme TU Berlin

## Contents |

### Abstract

High Throughput Screening (HTS) plants are used for analysis of chemical or biological substances, where, for a large number of sample batches, several operations have to be executed in the same specific time scheme. This project addresses the scheduling problem for HTS processes, i.e., it aims at determining the optimal (in the sense of throughput maximisation) sequence and timing for all operations during a screening run. Similar problems of throughput maximisation arise in other laboratory automation contexts, and one such problem is currently being investigated with a partner from industry.

### Cooperation

### People involved

- Eckart Mayer (now with Robert Bosch GmbH)
- Jörg Raisch
- Kai Wulff (now with TU Ilmenau)
- Christoph Horst (now with dSpace GmbH)
- Tom Brunsch

### Description

High Throughput Screening (HTS) plants are used for analysis of chemical or biological substances. Although several hundreds of substances are usually aggregated on a single microplate ("batch"), a large number of batches have to pass through the plant resources, e.g. incubators, liquid handling devices, transport devices, etc., in the same specific time scheme. This motivates the specific scheduling task for HTS plants, namely to determine a sequence and time scheme for all operations that will lead to maximal throughput or, equivalently, will need minimal time to achieve a desired throughput. The task is set apart from scheduling problems in other applications areas by a number of requirements: while progressing through several operations, each single batch may pass the same machine more than once; more than one batch will be present in the system at the same time, and there are no buffers between the machines; a batch may occupy two or more machines simultaneously when being transferred from one machine to another; additionally, there will be upper time bounds ("due dates") defined by the user.

A number of scheduling approaches have been suggested for specialized
HTS plants. However, as development goes towards large flexible HTS plants (an example is shown the following figure), a general scheduling approach is needed which can be used independently of the specific combination of machines and transport devices.
The motivation for this project came from a cooperation with
with Cybio AG, a leading manufacturer of HTS plants. In many cases, due
to the specific nature of the substances to be screened,
operating schemes in their plants have to be strictly cyclic, i.e. the time
distance between two consecutive batches ("cycle time") is required to be
constant. Throughput maximisation is then equivalent to minimisation of cycle time.
To formalise this scheduling problem, we need a mathematical model for cyclic
processes and for all constraints to be satisfied. A key
ingredient is a compact and effective formulation for the so called
disjunctive constraints, which state that no resource of the plant can be used
by more than one batch simultaneously ^{[1]}. Based on this, the scheduling problem
can be reformulated as a (generally very large) mixed integer nonlinear optimisation problem
(MINLP). Next, the size of the problem formulation can be reduced
considerably by using a suitable parametrisation for the degrees of freedom
of the scheduling task. However, even small MINLPs may be extremely hard to
solve, hence an important step within this project was the discovery of a
transformation that makes the problem a linear one ^{[1]},^{[2]}. The resulting MILP (mixed integer linear problem) is an exact representation of the underlying scheduling problem and can be solved using, for example, branch and bound methods.

The result is guaranteed to be a globally optimal solution. An illustrative example is given in the figure below, where the top part shows a cyclic operating scheme for a problem requiring six allocations on three resources per batch. The lower part shows the corresponding minimal cycle-time scheme. Interestingly, completion of a single batch takes longer in the optimal scheme.

The proposed method has been successfully applied to a sample scheduling
problem for a modern, fully automated flexible HTS system, where screening
runs involve up to 150 resource allocations per batch.
Extensions such as variable switching times and resources with multiple
capacity have been treated in ^{[3]}.

Special types of multi-capacity resources are considered in ^{[4]},^{[5]}. These so-called pooling resources can process several entities in
parallel. However in contrast to multipe capacity resources the associated
activities on pooling resources start and end at the same time for all entities. This
requires a relaxation of the strict cyclicity and the integration of several batches into some higher-order batch. Cyclicity will then be insured on this higher level.
Another extension, the hierarchical nesting of cycles, which often allows for schedules with improved throughput, has been investigated in cooperation with **U.U. Hauss** from Otto-von-Guericke Universität Magdeburg.

### Publications

- ↑
^{1.0}^{1.1}- Eckart Mayer, Jörg Raisch.
**Time-optimal scheduling for high throughput screening processes using cyclic discrete event models**.*MATCOM - Mathematics and Computers in Simulation*, 66 (2–3):181–191, 2004. - Bibtex| Abstract
**Author :**Eckart Mayer, Jörg Raisch**Title :**Time-optimal scheduling for high throughput screening processes using cyclic discrete event models**In :***MATCOM - Mathematics and Computers in Simulation*,**Date :**2004

- Eckart Mayer, Jörg Raisch.
- ↑
- Eckart Mayer, Jörg Raisch.
**Modelling and optimization for high-throughput-screening systems**. In*ADCHEM2003 - International Symposium on Advanced Control of Chemical Processes*, pages 513–518, Hong-Kong, 2003. - Bibtex| Abstract
**Author :**Eckart Mayer, Jörg Raisch**Title :**Modelling and optimization for high-throughput-screening systems**In :**In*ADCHEM2003 - International Symposium on Advanced Control of Chemical Processes*,**Date :**2003

- Eckart Mayer, Jörg Raisch.
- ↑
- Eckart Mayer, Jörg Raisch.
**Throughput-optimal scheduling for cyclically repeated processes**. In*Proc. MMAR2003 - 9th IEEE Int. Conf. on Methods and Models in Automation and Robotics*, pages 871–876, Miedzyzdroje, Poland, 2003. - Bibtex| Abstract
**Author :**Eckart Mayer, Jörg Raisch**Title :**Throughput-optimal scheduling for cyclically repeated processes**In :**In*Proc. MMAR2003 - 9th IEEE Int. Conf. on Methods and Models in Automation and Robotics*,**Date :**2003

- Eckart Mayer, Jörg Raisch.
- ↑
- Christoph Horst.
**Throughput-Optimal Cyclic Scheduling With Pooling Resources**. Diploma thesis, 2006. - Bibtex
**Author :**Christoph Horst**Title :**Throughput-Optimal Cyclic Scheduling With Pooling Resources**In :****Date :**2006

- Christoph Horst.
- ↑
- Eckart Mayer, Kai Wulff, Christoph Horst, Jörg Raisch.
**Optimal Scheduling of Cyclic Processes with Pooling-Resources**.*at, Automatisierungstechnik*, 56 (4):181–188, 2008. - Bibtex
**Author :**Eckart Mayer, Kai Wulff, Christoph Horst, Jörg Raisch**Title :**Optimal Scheduling of Cyclic Processes with Pooling-Resources**In :***at, Automatisierungstechnik*,**Date :**2008

- Eckart Mayer, Kai Wulff, Christoph Horst, Jörg Raisch.