Scheduling algorithms for reservoir- and mixer-aware sample preparation with microfluidic biochips

In recent years, microfluidic biochips are being dominantly used for implementing a wide range of biochemical laboratory protocols (bioprotocols) on hand-held devices. Accurate preparation of fluid-samples is a fundamental preprocessing step that is needed in many bioprotocols. Oftentimes, for point-of-service microfluidic devices, the number of reservoirs built on-chip may be far less than that of the reactant fluids to be used in an assay. Hence, during the execution of an assay, several fluids are to be unloaded from the reservoirs to make room for loading new fluids stored off-line. Such unload-wash-load steps (switching) may be required several times, and these steps, being manual, significantly impact assay-completion time. In this paper, we address the problem of biochemical mixture preparation and propose Reservoir- and Mixer-constrained Scheduling (RMS) algorithm that executes a given mixing tree aiming to minimize the number of reactant-switching from input reservoirs. We also consider certain constraints on the availability of concurrent mixing modules. The proposed scheduling scheme can not only be applied to a number of mixture preparation algorithms but also to a general class of microfluidic devices such as digital, paper-based, and flow-based biochips. Simulation results over a large number of target ratios show that given the mixing trees obtained by standard mixing algorithms such as MinMix/RMA/CoDOS, RMS reduces switching steps (on average by 40.3%/41.9%/33%) at the cost of increasing mixing time (by only 3.5%/6.2%/4.8%), compared to an existing scheduling scheme invoked with reservoir constraints.