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. Mixers and storage units, composed of electrodes, are two important functional resources. Mixers perform droplet mixing and splitting operations, while storage units store droplets that have been produced for subsequent mixings. In this paper, we focus on minimizing the completion time of biochemical analyses by exploiting the binary tree representation of analyses to schedule mixing operations. Using pipelining, we overlap mixing operations with input and transportation operations. We find the lower bound of the mixing completion time based on the tree structure of input analyses, and calculate the minimum number of mixers required to achieve the lower bound. We present a scheduling algorithm for the case with a specified number of mixers, 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 just one mixer, we prove that all schedules that keep the mixer busy at all times result in the same mixing completion time and then design algorithms for scheduling and to minimize the number of storage units. For the case with zero storage units, we find the minimum number of mixers required. We extend our analyses and algorithms assuming identical mixing durations to the case of different mixing durations. Finally, we illustrate the benefits of our scheduling methods on an example of DNA polymerase chain reaction (PCR) analysis. Note to Practitioners-This paper presents scheduling techniques for DMFS, a new class of lab-on-a-chip devices. These chips execute chemical analyses by moving, mixing, and splitting droplets of different chemicals. Our primary goal is to automate and optimize the scheduling of droplet input, mixing, and output operations to minimize the completion time of DMFS applications. This paper presents new scheduling algorithms that are efficient, easy to implement, and proven to be optimal in completion time. The algorithms exploit the full binary tree structure of biochemical analyses to minimize the completion time. To develop cost-efficient biochips, we present algorithms that reduce the required resources (e.g., mixers, storage units) on DMFS chips to complete the biochemical analyses. Our scheduling algorithms when combined with droplet routing algorithms can create completely automated software controllers for DMFS.