Placement of Digital Microfluidic Biochips via a New Evolutionary Algorithm
- 28 June 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Design Automation of Electronic Systems
- Vol. 26 (6), 1-22
- https://doi.org/10.1145/3460230
Abstract
Digital microfluidic biochips (DMFBs) have been a revolutionary platform for automating and miniaturizing laboratory procedures with the advantages of flexibility and reconfigurability. The placement problem is one of the most challenging issues in the design automation of DMFBs. It contains three interacting NP-hard sub-problems: resource binding, operation scheduling, and module placement. Besides, during the optimization of placement, complex constraints must be satisfied to guarantee feasible solutions, such as precedence constraints, storage constraints, and resource constraints. In this article, a new placement method for DMFB is proposed based on an evolutionary algorithm with novel heuristic-based decoding strategies for both operation scheduling and module placement. Specifically, instead of using the previous list scheduler and path scheduler for decoding operation scheduling chromosomes, we introduce a new heuristic scheduling algorithm (called order scheduler) with fewer limitations on the search space for operation scheduling solutions. Besides, a new 3D placer that combines both scheduling and placement is proposed where the usage of the microfluidic array over time in the chip is recorded flexibly, which is able to represent more feasible solutions for module placement. Compared with the state-of-the-art placement methods (T-tree and 3D-DDM), the experimental results demonstrate the superiority of the proposed method based on several real-world bioassay benchmarks. The proposed method can find the optimal results with the minimum assay completion time for all test cases.Keywords
Funding Information
- National Natural Science Foundation of China (61976111)
- Guangdong Provincial Key Laboratory (2020B121201001)
- Program for Guangdong Introducing Innovative and Entrepreneurial Teams (2017ZT07×386)
- Shenzhen Science and Technology Program (KQTD2016112514355531, and JCYJ20180504165652917)
This publication has 20 references indexed in Scilit:
- Tabu search-based synthesis of digital microfluidic biochips with dynamically reconfigurable non-rectangular devicesDesign Automation for Embedded Systems, 2010
- Fast and reliable droplet transport on single-plate electrowetting on dielectrics using nonfloating switching methodBiomicrofluidics, 2010
- Integrated droplet routing and defect tolerance in the synthesis of digital microfluidic biochipsACM Journal on Emerging Technologies in Computing Systems, 2008
- High-level synthesis of digital microfluidic biochipsACM Journal on Emerging Technologies in Computing Systems, 2008
- Placement of defect-tolerant digital microfluidic biochips using the T-tree formulationACM Journal on Emerging Technologies in Computing Systems, 2007
- Digital microfluidics: is a true lab-on-a-chip possible?Microfluidics and Nanofluidics, 2007
- An integrated digital microfluidic lab-on-a-chip for clinical diagnostics on human physiological fluidsLab on a Chip, 2004
- Scheduling of microfluidic operations for reconfigurable two-dimensional electrowetting arraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2001
- Electrowetting-based actuation of liquid droplets for microfluidic applicationsApplied Physics Letters, 2000
- Fast template placement for reconfigurable computing systemsIEEE Design & Test of Computers, 2000