Efficient one-pass synthesis for digital microfluidic biochips

Digital microfluidics biochips are a promising emerging technology that provides fluidic experimental capabilities on a chip (i.e., following the lab-on-a-chip paradigm). However, the design of such biochips still constitutes a challenging task that is usually tackled by multiple individual design steps, such as binding, scheduling, placement, and routing. Performing these steps consecutively may lead to design gaps and infeasible results. To address these shortcomings, the concept of one-pass design for digital microfluidics biochips has recently been proposed - a holistic approach avoiding the design gaps by considering the whole synthesis process as large. But implementations of this concept available thus far suffer from either high computational effort or costly results. In this article, we present an efficient one-pass solution that is runtime efficient (i.e., rarely needing more than a second to successfully synthesize a design) while, at the same time, producing better results than previously published heuristic approaches. Experimental results confirm the benefits of the proposed solution and allow for realizing really large assays composed of thousands of operations in reasonable runtime.