Resource-Constrained Scheduling for Digital Microfluidic Biochips

• DOI: 10.1145/3093930
• Publication Date: 2017-10-16T12:37:42Z
• Authors: Kenneth O'neal; Daniel Grissom; Philip Brisk
• Keywords: Digital Microfluidics; Biochip; Heuristics

Digital microfluidics based on electrowetting-on-dielectric technology is poised to revolutionize many aspects of chemistry and biochemistry through miniaturization, automation, software programmability. microfluidic biochips (DMFBs) offer ample spatial parallelism, which then exposed the compiler. The first problem that a DMFB compiler must solve resource-constrained scheduling, NP-complete. If applied off-line, long-running algorithms produce solutions high quality, such as iterative improvement or branch-and-bound search, can be applied; in an online context, where biochemical reaction executed soon it specified by programmer, heuristics sacrifice solution quality attain fast runtime are used. This article describes detail have been proposed for focusing several recent contributions: path scheduling force-directed list scheduling. It also discusses shortcomings limitations existing optimal formulations Integer Linear Programming presents updated formulation addresses these issues. compared evaluated extensive benchmark suite assays used applications, vitro diagnostics, protein crystallization, automated sample preparation.