direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Throughput Maximisation for Screening Processes

From Fachgebiet Regelungssysteme TU Berlin

Jump to: navigation, search

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

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.

Flexible scheduling plant (CyBio AG, Jena).

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.

Examples for cyclic operating scheme (Gantt charts). Individual batches are shown in different colours.

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. 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.
  2. 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.
  3. 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.
  4. Christoph Horst. Throughput-Optimal Cyclic Scheduling With Pooling Resources. Diploma thesis, 2006.
  5. Eckart Mayer, Kai Wulff, Christoph Horst, Jörg Raisch. Optimal Scheduling of Cyclic Processes with Pooling-Resources. at, Automatisierungstechnik, 56 (4):181–188, 2008.

Recommend this page