# Modeling and Control of HTS Systems

## 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.

High-throughput screening plant (CyBio AG, Jena).

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.

Gantt chart of an optimized HTS operation (CyBio AG, Jena). The different colors indicate different batches.

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 $\mathcal{D}$ endowed with two binary operations $\oplus$ (addition) and $\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 ε and e, respectively. Due to the idempotency property of dioids a natural (partial) order can be defined, i.e., $a \oplus b = a, a \succeq b$. A widely known example for an idempotent semiring is the so-called (max,+)-algebra, where $\oplus$ is defined to be the standard maximum and $\otimes$ is the conventional addition in standard algebra. The zero (unit) element of (max,+)-algebra is $\varepsilon = -\infty \,\,(e = 0)$.

For the modelling and control of HTS processes, it is convenient to use the dioid $\mathcal{M}_{in}^{ax} \lbrack\lbrack \gamma,\delta\rbrack\rbrack$. Formally, this is the dioid of equivalence classes (quotient dioid) in $\mathbb{B}\lbrack\lbrack\gamma,\delta\rbrack\rbrack$, where $\mathbb{B}\lbrack\lbrack\gamma,\delta\rbrack\rbrack$ is the set of formal power series in two variables (γ,δ) with Boolean coefficients, i.e., $\mathbb{B} = \{\varepsilon,e\}$ and exponents in $\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 $\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 $\otimes x \preceq y$ and $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 dioid $\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 u, i.e., the controller is able to delay the start of every activity. The control output y is the finish event of the batch, and the state variables 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

1. 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.
2. 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.
3. 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.
4. E. Mayer. Globally optimal schedules for cyclic systems with non-blocking specification and time window constraints. Technische Universität Berlin, 2007.
5. E. Mayer, K. Wulff, C. Horst, J. Raisch. Optimal Scheduling of Cyclic Processes with Pooling-Resources. at - Automatisierungstechnik, 56 (4):181–188, 2008.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
12. T. Brunsch, J. Raisch, L. Hardouin. Modeling and Control of High-Throughput Screening Systems. Control Engineering Practice, 20 (1):14–23, 2012.
13. 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.
14. 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.