### Inhalt des Dokuments

# Modeling and Control of HTS Systems

### 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 maximization) sequence and timing for all operations during a screening run. We have focused on cyclic schedules, which considerably reduces the number of degrees of freedom. We have shown that within the developed framework globally optimal schedules can be computed efficiently for industrial size problems. Recent extensions concern the treatment of so-called pooling resources, the hierarchical nesting of cycles, and the design of feedback control using dioid methods.

## People involved

- Eckart Mayer (now with Robert Bosch GmbH)
- Kai Wulff (now with TU Ilmenau)
- Thomas Brunsch (now with IAV, Berlin)
- Jörg Raisch

## Cooperation

- CyBio AG, Jena, Germany
- Laurent Hardouin (Laboratoire d'Ingénierie des Systèmes Automatisés, Université d'Angers, France)

## Description

High-throughput screening (HTS) has become an important technology to rapidly test thousands of biochemical substances. In the pharmaceutical industries, for example, HTS is often used for a first screening in the process of drug discovery. In general, high-throughput screening plants are fully automated systems containing a fixed set of devices performing liquid handling, storage, reading, plate handling, and incubation steps. All operations which have to be conducted to analyse one set of substances are combined in a so-called batch. A set of substances consists of up to 1536 compounds which are aggregated on one microplate. Additional microplates may be included in a batch to convey reagents or waste material. To compare the screening results of different compound sets, the single batch time scheme, i.e., the sequence and the timing of activities for one batch, needs to be identical for all batches.

This project has been a long-running one involving several partners, most notably CyBio AG, a leading
manufacturer of HTS plants. The project was first concerned with solving a specific scheduling
task for HTS plants, namely to determine a sequence and a time scheme for all operations that will
lead to maximal throughput or, equivalently, will need minimal time to achieve a desired throughput.
The scheduling problem is characterized by a number of HTS specific requirements: (i) a single
batch may pass the same machine more than once while progressing through several operations; (ii)
more than one batch will be present in the system at the same time; (iii) there are no buffers between
the machines; (iv) a single batch may occupy two or more resources simultaneously, e.g.,
when being transferred from one resource to another; (v) there will be lower and upper bounds
(minimal and maximal processing times) defined by the user. In many cases, due to the specific
nature of substances to be screened, operating schemes in HTS have to be cyclic, i.e., the time distance
between two corresponding activities in consecutive batches (“cycle time”) is required to be
constant. Throughput maximization is then equivalent to minimization of cycle time. To formalize
this scheduling problem, it can be written as a (generally very large) mixed integer non-linear optimization
problem (MINLP)
^{[1]}
^{[2]}. 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
^{[3]}.
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
^{[4]}
^{[5]}
^{[6]}.
The developed algorithm to determine
the globally optimal schedule for HTS systems has been implemented in CyBio’s current software.

The described method has been successfully applied to sample scheduling problems for HTS systems, where screening runs involve up to 150 resource allocations per batch. The Gantt chart of an optimized HTS screening run performed by CyBio AG can be seen in the figure below.

The approach outlined above essentially constitutes an offline method, i.e., the generated schedule
is a static one. In practice, however, unforeseen disturbances will frequently occur during run-time.
To handle these, we have also investigated feedback approaches for HTS systems. This
part of the project was based on a cooperation with CyBio AG and the University of Angers,
France, (Laurent Hardouin), and was funded through the EU FP7 project DISC. Our feedback
approach builds on the available off-line schedule. The resulting feedback synthesis problem
is (non-benevolently) nonlinear when considered in standard algebra. However, reformulating the
problem in certain “tropical algebras” provides a linear representation
^{[7]}
^{[8]}
^{[9]}. Formally, a tropical algebra
is an idempotent semiring (also called dioid), i.e., a set **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): \mathcal{D}**

endowed with two binary operationsFailed to parse (PNG conversion failed;

**check for correct installation of latex, dvips, gs, and convert): \oplus**

(addition) and **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): \otimes**

(multiplication), where addition is associative, commutative, and idempotent and

multiplication is associative and distributive with respect to addition. The zero and unit element in
dioids are usually denoted by **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): \varepsilon**

andFailed to parse (PNG conversion failed;

**check for correct installation of latex, dvips, gs, and convert): e**
, respectively. Due to the idempotency property of dioids a
natural (partial) order can be defined, i.e., **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): a \oplus b = a, a \succeq b**
. A widely known example for an idempotent
semiring is the so-called (max,+)-algebra, where **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): \oplus**

is defined to be the standard maximum

and **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): \otimes**

is the conventional addition in standard algebra. The zero (unit) element of (max,+)-algebra

is **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): \varepsilon = -\infty \,\,(e = 0)**
.

For the modelling and control of HTS processes, it is convenient to use the dioid **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): \mathcal{M}_{in}^{ax} \lbrack\lbrack \gamma,\delta\rbrack\rbrack**
. Formally,
this is the dioid of equivalence classes (quotient dioid) in **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): \mathbb{B}\lbrack\lbrack\gamma,\delta\rbrack\rbrack**
, where **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): \mathbb{B}\lbrack\lbrack\gamma,\delta\rbrack\rbrack**

is the set

of formal power series in two variables **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): (\gamma,\delta)**

with Boolean coefficients, i.e.,Failed to parse (PNG conversion failed;

**check for correct installation of latex, dvips, gs, and convert): \mathbb{B} = \{\varepsilon,e\}**

and exponents inFailed to parse (PNG conversion failed;

**check for correct installation of latex, dvips, gs, and convert): \overline{\mathbb{Z}} = \mathbb{Z}\cup\{-\infty, \infty\}**
. One advantage of using this dioid is that it allows an efficient and compact way to formulate complex dependencies between starting and finishing times of activities
in different batches
^{[10]}.

A **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): \mathcal{M}_{in}^{ax} \lbrack\lbrack \gamma,\delta\rbrack\rbrack**
-model of an HTS process includes the user specifications for a single batch, i.e.,
the minimal and maximal processing times and the sequencing of activities of different batches on
each resource (provided by the optimal schedule determined offline). The model does, however,
not encode the overall time scheme provided by the optimal schedule, as these degrees of freedom
are necessary to implement feedback control. In general a multiplicative inverse may not exist in
dioids. However, least upper bounds for the solution sets of a **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): \otimes x \preceq y**

andFailed to parse (PNG conversion failed;

**check for correct installation of latex, dvips, gs, and convert): x \otimes b \preceq y**

are uniquely defined. They are called residuals and can be used to determine appropriate control. In particular, it is possible to determine feedback controllers such that the closed-loop system is less or equal (in the sense of the partial order defined by the dioidFailed to parse (PNG conversion failed;

**check for correct installation of latex, dvips, gs, and convert): \mathcal{M}_{in}^{ax}\lbrack\lbrack\gamma,\delta\rbrack\rbrack**
) to a given reference model. For HTS systems the start events of all activities are usually chosen to be the control inputs **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): u**
, i.e., the controller is able to delay the start of every activity. The control output **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): y**

is the finish event of the

batch, and the state variables **Failed to parse (PNG conversion failed;
check for correct installation of latex, dvips, gs, and convert): x**

model all internal events that occur during the screening of a single

batch. For a given reference system, residuation theory provides the largest feedback controller (in
the above sense) such that the controlled system is less or equal to the reference model, i.e., the
controller starts every activity as late as possible while maintaining the throughput of the reference
model. Thus, the controller implements a just-in-time policy. If the reference model is chosen
to achieve the maximal possible throughput, for example the throughput of the optimal schedule
determined off-line, the closed-loop system will operate with the highest possible throughput as
well. Furthermore, the controller can react to unforeseen disturbances and is easily implemented in
an industrial PLC
^{[11]}
^{[12]}
^{[13]}.

In ^{[14]}, it was argued that, in terms of
synchronization and control, a large class of manufacturing systems
exhibits identical properties as HTS systems, and a suitable
dioid-based control approach was developped.

Funding for this project was mainly through the EU-FP7 project DISC. Additional financial support was provided by the bilateral French-German PROCOPE programme.

## Publications

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

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

- E. Mayer, J. Raisch.
- ↑
- E. Mayer, J. 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| PDF | DOI
**Author :**E. Mayer, J. Raisch**Title :**Time-optimal scheduling for high throughput screening processes using cyclic discrete event models**In :***MATCOM - Mathematics and Computers in Simulation*,**Date :**2004

- E. Mayer, J. Raisch.
- ↑
- E. Mayer.
**Globally optimal schedules for cyclic systems with non-blocking specification and time window constraints**. Technische Universität Berlin, 2007. - Bibtex
**Author :**E. Mayer**Title :**Globally optimal schedules for cyclic systems with non-blocking specification and time window constraints**In :****Date :**2007

- E. Mayer.
- ↑
- E. Mayer, K. Wulff, C. Horst, J. Raisch.
**Optimal Scheduling of Cyclic Processes with Pooling-Resources**.*at - Automatisierungstechnik*, 56 (4):181–188, 2008. - Bibtex| PDF | DOI
**Author :**E. Mayer, K. Wulff, C. Horst, J. Raisch**Title :**Optimal Scheduling of Cyclic Processes with Pooling-Resources**In :***at - Automatisierungstechnik*,**Date :**2008

- E. Mayer, K. Wulff, C. Horst, J. Raisch.
- ↑
- E. Mayer, U.-U. Haus, J. Raisch, R. Weismantel.
**Throughput-Optimal Sequences for Cyclically Operated Plants**.*Discrete Event Dynamic Systems - Theory and Applications*, 18 (3):355–383, 2008. - Bibtex| PDF | DOI
**Author :**E. Mayer, U.-U. Haus, J. Raisch, R. Weismantel**Title :**Throughput-Optimal Sequences for Cyclically Operated Plants**In :***Discrete Event Dynamic Systems - Theory and Applications*,**Date :**2008

- E. Mayer, U.-U. Haus, J. Raisch, R. Weismantel.
- ↑
- T. Brunsch, J. Raisch.
**Max-Plus Algebraic Modeling and Control of High-Throughput Screening Systems**. In*Preprints of the 2nd IFAC Workshop on Dependable Control of Discrete Systems*, pages 103–108, Bari, Italy, 2009. - Bibtex
**Author :**T. Brunsch, J. Raisch**Title :**Max-Plus Algebraic Modeling and Control of High-Throughput Screening Systems**In :**In*Preprints of the 2nd IFAC Workshop on Dependable Control of Discrete Systems*,**Date :**2009

- T. Brunsch, J. Raisch.
- ↑
- T. Brunsch, J. Raisch.
**Max-Plus Algebraic Modeling and Control of High-Throughput Screening Systems with Multi-Capacity Resources**. In*Preprints of the 3rd IFAC Conference on Analysis and Design of Hybrid Systems (ADHS'09)*, pages 132–137, Zaragoza, Spain, 2009. - Bibtex
**Author :**T. Brunsch, J. Raisch**Title :**Max-Plus Algebraic Modeling and Control of High-Throughput Screening Systems with Multi-Capacity Resources**In :**In*Preprints of the 3rd IFAC Conference on Analysis and Design of Hybrid Systems (ADHS'09)*,**Date :**2009

- T. Brunsch, J. Raisch.
- ↑
- T. Brunsch, J. Raisch.
**Modeling and control of high-throughput screening systems in a max-plus algebraic setting**.*Engineering Applications of Artificial Intelligence*, 25 (4):720–727, 2012. - Bibtex| PDF | DOI
**Author :**T. Brunsch, J. Raisch**Title :**Modeling and control of high-throughput screening systems in a max-plus algebraic setting**In :***Engineering Applications of Artificial Intelligence*,**Date :**2012

- T. Brunsch, J. Raisch.
- ↑
- T. Brunsch, L. Hardouin, J. Raisch.
**Control of cyclically operated High-Throughput Screening Systems**. In*Preprints of the 10th International Workshop on Discrete Event Systems (WODES'10)*, pages 177–182, Berlin, Germany, 2010. - Bibtex
**Author :**T. Brunsch, L. Hardouin, J. Raisch**Title :**Control of cyclically operated High-Throughput Screening Systems**In :**In*Preprints of the 10th International Workshop on Discrete Event Systems (WODES'10)*,**Date :**2010

- T. Brunsch, L. Hardouin, J. Raisch.
- ↑
- T. Brunsch, L. Hardouin, J. Raisch.
**Modeling and control of nested manufacturing processes using dioid models**. In*Preprints of the 3rd International Workshop on Dependable Control of Discrete Systems (DCDS11)*, pages 78–83, Saarbrücken, Germany, 2011. - Bibtex| PDF | DOI
**Author :**T. Brunsch, L. Hardouin, J. Raisch**Title :**Modeling and control of nested manufacturing processes using dioid models**In :**In*Preprints of the 3rd International Workshop on Dependable Control of Discrete Systems (DCDS11)*,**Date :**2011

- T. Brunsch, L. Hardouin, J. Raisch.
- ↑
- T. Brunsch, J. Raisch, L. Hardouin.
**Modeling and Control of High-Throughput Screening Systems**.*Control Engineering Practice*, 20 (1):14–23, 2012. - Bibtex| PDF | DOI
**Author :**T. Brunsch, J. Raisch, L. Hardouin**Title :**Modeling and Control of High-Throughput Screening Systems**In :***Control Engineering Practice*,**Date :**2012

- T. Brunsch, J. Raisch, L. Hardouin.
- ↑
- T. Brunsch, L. Hardouin, C. A. Maia, J. Raisch.
**Duality and interval analysis over idempotent semirings**.*Linear Algebra and its Applications*, 437 (10):2436–2454, November 2012. - Bibtex| PDF | DOI
**Author :**T. Brunsch, L. Hardouin, C. A. Maia, J. Raisch**Title :**Duality and interval analysis over idempotent semirings**In :***Linear Algebra and its Applications*,**Date :**November 2012

- T. Brunsch, L. Hardouin, C. A. Maia, J. Raisch.
- ↑
- T. Brunsch, L. Hardouin, J. Raisch.
**Modelling Manufacturing Systems in a Dioid Framework**. In J. Campos and C. Seatzu and X. Xie, editor,*Formal Methods in Manufacturing*, 2, pages 29-74. CRC Press, 2014. - Bibtex
**Author :**T. Brunsch, L. Hardouin, J. Raisch**Title :**Modelling Manufacturing Systems in a Dioid Framework**In :**In J. Campos and C. Seatzu and X. Xie, editor,*Formal Methods in Manufacturing*,**Date :**2014

- T. Brunsch, L. Hardouin, J. Raisch.