Optimal scheduling of biochemical analyses on digital microfluidic systems

Digital microfluidic systems (DMFS) are an emerging class of lab-on-a-chip systems that manipulate individual droplets of chemicals on a planar array of electrodes. The biochemical analyses are performed by repeatedly moving, mixing, and splitting droplets on the electrodes. In this paper, we focus on minimizing the completion time of biochemical analyses by exploiting the parallelism among the operations. We consider a binary tree representation of chemical analyses to schedule operations. Using pipelining, we overlap mixing operations with input and transportation operations. We find the lower bound of the mixing completion time according to the tree structure of given reactions, and calculate the minimal number of mixers S required to achieve the lower bound. We present a scheduling algorithm for the case with a specified number of mixers no more than S, and prove it is optimal to minimize the mixing completion time. We also analyze resource constraint issues for two extreme cases. For the case with one mixer, we prove that all schedules result in the same mixing completion time as long as the mixer is kept busy at all times and then design a scheduling algorithm to minimize the number of storage units. For the case with zero storage units, we find the minimum number of mixers required. Finally, we demonstrate the benefits of our scheduling methods on an example of DNA polymerase chain reaction (PCR) analysis.