Synthesis of digital microfluidic biochips with reconfigurable operation execution

Microfluidic biochips are replacing the conventional biochemical analyzers, and are able to integrate on-chip all the basic functions for biochemical analysis. The “digital ” microfluidic biochips are manipulating liquids not as a continuous flow, but as discrete droplets on a two-dimensional array of electrodes. Basic microfluidic oper-ations, such as mixing and dilution, are performed on the array, by routing the corresponding droplets on a series of electrodes. So far, researchers have assumed that these operations are executed on rectangular virtual devices, formed by grouping several adjacent electrodes. One drawback is that all electrodes are considered oc-cupied during the operation execution, although the droplet uses only one electrode at a time. Moreover, the operations can actually execute by routing the droplets on any sequence of electrodes on the array. Hence, in this paper, we eliminate the concept of virtual modules and allow the droplets to move on the chip on any route during operation execution. Thus, the synthesis problem is trans-formed into a routing problem. We propose an approach derived from a Greedy Randomized Adaptive Search Procedure (GRASP) and we show that by considering routing-based synthesis, signifi-cant improvements can be obtained in the application completion time