Modeling and Control of HTS Systems

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.

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 started investigating feedback approaches for HTS systems. This current part of the project is based on a cooperation with CyBio AG and the University of Angers, France, (Laurent Hardouin), and has been 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 \varepsilon 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].

So far we have mainly investigated the monolithic case, where all available information is centrally processed and fed back. However, as HTS systems (and the corresponding feedback control) tend to be complex, distributed control schemes are an attractive option. Within the EU-FP7 project DISC, we investigate to what extent available decentralized and distributed control concepts carry over to the dioid setting used in this project.

Current funding for this project is mainly through the EU-FP7 project DISC. Additional financial support has been provided by the bilateral French-German PROCOPE programme.

Publications

  1. E. Mayer, J. Raisch - Throughput-optimal scheduling for cyclically repeated processes
    Proc. MMAR2003 - 9th IEEE International Conference on Methods and Models in Automation and Robotics pp. 871–876, Miedzyzdroje, Poland,2003
    Bibtex
    Author : E. Mayer, J. Raisch
    Title : Throughput-optimal scheduling for cyclically repeated processes
    In : Proc. MMAR2003 - 9th IEEE International Conference on Methods and Models in Automation and Robotics -
    Address : Miedzyzdroje, Poland
    Date : 2003
  2. E. Mayer, J. Raisch - Modelling and optimization for high-throughput screening systems
    Proc. ADCHEM2003 - International Symposium on Advanced Control of Chemical Processes pp. 513–518, Hong-Kong,2003
    Bibtex
    Author : E. Mayer, J. Raisch
    Title : Modelling and optimization for high-throughput screening systems
    In : Proc. ADCHEM2003 - International Symposium on Advanced Control of Chemical Processes -
    Address : Hong-Kong
    Date : 2003
    | PDF
  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
    Bibtex
    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 -
    Address :
    Date : 2004
    | PDF | DOI
  4. E. Mayer - Globally optimal schedules for cyclic systems with non-blocking specification and time window constraints
    Ph.D. Thesis, 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 : Ph.D. Thesis, Technische Universität Berlin -
    Address :
    Date : 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
    Bibtex
    Author : E. Mayer, K. Wulff, C. Horst, J. Raisch
    Title : Optimal Scheduling of Cyclic Processes with Pooling-Resources
    In : at - Automatisierungstechnik -
    Address :
    Date : 2008
    | PDF | DOI
  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
    Bibtex
    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 -
    Address :
    Date : 2008
    | PDF | DOI
  7. T. Brunsch, J. Raisch - Max-Plus Algebraic Modeling and Control of High-Throughput Screening Systems
    Preprints of the 2nd IFAC Workshop on Dependable Control of Discrete Systems pp. 103–108, Bari, Italy,2009
    Bibtex
    Author : T. Brunsch, J. Raisch
    Title : Max-Plus Algebraic Modeling and Control of High-Throughput Screening Systems
    In : Preprints of the 2nd IFAC Workshop on Dependable Control of Discrete Systems -
    Address : Bari, Italy
    Date : 2009
    | PDF
  8. T. Brunsch, J. Raisch - Max-Plus Algebraic Modeling and Control of High-Throughput Screening Systems with Multi-Capacity Resources
    Preprints of the 3rd IFAC Conference on Analysis and Design of Hybrid Systems (ADHS'09) pp. 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 : Preprints of the 3rd IFAC Conference on Analysis and Design of Hybrid Systems (ADHS'09) -
    Address : Zaragoza, Spain
    Date : 2009
    | PDF
  9. T. Brunsch, J. Raisch - Modeling and control of high-throughput screening systems in a max-plus algebraic setting
    Engineering Applications of Artificial Intelligence ,2010
    Bibtex
    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 -
    Address :
    Date : 2010
    | PDF | DOI
  10. T. Brunsch, L. Hardouin, J. Raisch - Control of cyclically operated High-Throughput Screening Systems
    Preprints of the 10th International Workshop on Discrete Event Systems (WODES'10) pp. 177–182, Berlin, Germany,2010
    Bibtex
    Author : T. Brunsch, L. Hardouin, J. Raisch
    Title : Control of cyclically operated High-Throughput Screening Systems
    In : Preprints of the 10th International Workshop on Discrete Event Systems (WODES'10) -
    Address : Berlin, Germany
    Date : 2010
    | PDF
  11. T. Brunsch, L. Hardouin, J. Raisch - Modeling and control of nested manufacturing processes using dioid models
    Preprints of the 3rd International Workshop on Dependable Control of Discrete Systems (DCDS11) pp. 78–83, Saarbrücken, Germany,2011
     Bibtex
    Author : T. Brunsch, L. Hardouin, J. Raisch
    Title : Modeling and control of nested manufacturing processes using dioid models
    In : Preprints of the 3rd International Workshop on Dependable Control of Discrete Systems (DCDS11) -
    Address : Saarbrücken, Germany
    Date : 2011
     | PDF | DOI 
  12. T. Brunsch, J. Raisch, L. Hardouin - Modeling and Control of High-Throughput Screening Systems
    Control Engineering Practice 20(1):14–23,2012
     Bibtex
    Author : T. Brunsch, J. Raisch, L. Hardouin
    Title : Modeling and Control of High-Throughput Screening Systems
    In : Control Engineering Practice -
    Address :
    Date : 2012
     | PDF | DOI 
  13. T. Brunsch, L. Hardouin, C. A. Maia, J. Raisch - Duality and interval analysis over idempotent semirings
    Linear Algebra and its Applications (accepted for publication)
     Bibtex
    Author : T. Brunsch, L. Hardouin, C. A. Maia, J. Raisch
    Title : Duality and interval analysis over idempotent semirings
    In : Linear Algebra and its Applications -
    Address :
    Date :
     
Go to Editor View