Study On The Problem Of Placement And Scheduling For Digital Microfluidics-based Biochips

Digital microfluidis-based biochips manipulate liquids as discrete droplets, which have the promise of a wide range of applications in biochemical analysis, clinical diagnostics, biomanufactuing, environmental monitoring and military affairs fields. As the use of digital microfluidic biochips increases, their complexity is expected to become significant due to the need for multiple and concurrent assays on the chip, as well as more sophisticated control for resource management. Time-to-market and fault tolerance are also expected to emerge as design considerations. However, current design methodologies for microfluidic biochips are typically full-custom and bottom up in nature. These full-custom methodologies will not scale well for larger designs because of higher complexity and the need for quantifiable performance metrics that can be optimized. There is a pressing need to deliver the intelligent algorithm and the same level of computer-aided design (CAD) support to the biochip designer to relieve biochip users from the burden of manually optimizing a set of assays for increased throughout.Genetic algorithm for project scheduling, Personification Immune Genetic Algorithm and min-cost max-flow are proposed in this paper to solve the problems of placement, scheduling, and droplet routing respectively. The detailed work includes the following parts.1. Study on scheduling problem of digital microfluidics-based biochipsThe minimization of the assay completion time is essential for environmental monitoring applications, which is also necessary for surgery and neonatal clinical diagnostics. The goal of architectural -level scheduling for microfluidic biochips is to select a design that minimizes a certain cost function under resource constraints, so as to maximize parallelism, thereby decreasing response time, scheduling assay functions and binding them to a given number of resources. In this paper, the basic operation of biochemical assay is given; sequencing graph module and mathematic module are constructed as well based on the progress and optimal scheduling strategy of scheduling of microfluidic biochips. Moreover, precedence constraint and complicated resource constraint are analyzed to discover the effect factor of optimal scheduling for digital microfluidic biochips.An optimal genetic algorithm for project scheduling (GAPS) is developed, encoding of the solution and the operations such as crossover, mutation and evaluation are given as well. The example of a real-life biochemical procedure (Multiplexed in-vitro Diagnostics on Human Physiological Fluids) and protein assay are used to evaluate the proposed methodology under Visual C++ simulation environment. The comparison of schedule finish times obtained using our GAPS, GA, and M-LS are shown. Experiments show that for a biomedical assay of large size, the results obtained from GAPS can give standard the optimal scheduling sequences subject to the precedence constraints and the resource constraints for the droplets of digital microfluidics-based biochips and outperforms other scheduling algorithm.Study on resources binding problem of digital microfluidic biochips. A heuristic rule is developed into modified genetic algorithm for project scheduling to solve the dynamic resource binding.2. Study on the placement problem of digital microfluidics-based biochipsThe placement problem of digital microfluidics-based biochips creates a physical representation at the geometrical level, that is, the finally out of the biochip consisting of the configuration of the microfluidic array, locations of reservoirs and dispensing ports, and other geometric details. The personification heuristic algorithm is used in this paper to study microfluidic module physical placement, described the method of personification. This personification heuristic algorithm is inspired by the strategy of building wall in the daily life. The point-finding way and the rules of horizontal and vertical reference line are developed to control the packing process.Immune genetic algorithm is designed in this paper, which is used to multi-objective optimize the placement results. The antibody encoding, fitness function, population search strategy, the affinity of antibodies and concentration, immune selection operator and the spread of antibodies are described in detail. The process of microfluidic module physical placement in multiplexed in-vitro diagnostics on human physiological fluids is simulated, and the comparative analysis with the parallel simulated annealing algorithm is shown in the third chapter. The experiment results show that personification immune genetic algorithm can achieve not only the smallest biochip area, but also the shortest of completion time of all operations.The failure reasons of digital microfluidics-based biochips are analyzed in this paper, and the principle of partial reconfiguration is described as well. Based on this reconfiguration technique, a simple numerical measure termed the fault-tolerance index is defined to estimate the fault-tolerance capability of the biochip. We further extend the definition of this index to handle multiple faults. We also present an efficient algorithm to determine the fault-tolerance index of a biochip configuration based on the notion of maximal-empty rectangles, and simulate the fault tolerance process of multiplexed in-vitro diagnostics on human physiological fluids placement. 3. Study on the droplet routing of digital microfluidics-based biochipsThe droplet routing problem is to find droplet routes with minimum lengths, where route length is measured by the number of cells in the path from the starting point to the destination. The microfluidic array consists of primary cells that are used in assay operations, and spare cells that can replace faulty primary cells for fault tolerance. Thus, for a microfluidic array of fixed size, minimum-length droplet routes lead to the minimization of the total number of cells used in droplet routing, thus freeing up more spare cells for fault tolerance. This is especially important for safety-critical systems, an important application area for digital microfluidic biochips.The droplet routing problem of digital microfluidics-based biochips is analyzed in this paper, and droplet routing process and the optimal objective is given as well. Moreover, the modeling of routing constraints is constructed based on the analysis of fluidic constraints and time constraints.In this paper, we propose the first network-flow based routing algorithm for the droplet routing problem on digital microfluidic biochips. We adopt a two-stage technique of global routing followed by detailed routing. In global routing, we first identify a set of non-interfering nets and then adopt the network flow approach to generate optimal global-routing paths for the identified nets. In detailed routing, we present the routing tree for simultaneous routing and scheduling with a negotiation based routing scheme based on the global-routing paths. Our algorithm was simulated for the in-vitro diagnostic and the protein assay respectively. We also implemented the two-stage routing algorithm and the prioritized A*-search algorithm. Our algorithm can successfully route all benchmarks while previous works cannot. Moreover, our algorithm can achieve better solution quality with less CPU time than previous works. Experimental results demonstrate the robustness and efficiency of network-flow based routing algorithm.4. The computer aid design system of digital microfluidics-based biochipsWe design and development of the intelligent design platform of digital microfluidics-based biochips for the first time. This intelligent design platform can implement the chip design optimization and intelligent control of biochemical assay operations based on the input of biochemical assay.The research results can provide the technical support for the intelligent design and biomanufactuing of digital microfluidics-based biochips. Moreover, the intelligent design algorithm and platform can improve the development of theory of digital microfluidics-based biochips mechanical design.