Scheduling large-scale micro/nano biochemical testing: Exact and heuristic algorithms

We consider a micro/nano fluidic toolbit that consists of a set of identical testing units, each of which contains a microchannel that has an array of equally spaced nanopores opened along it. In each microchannel, same equally spaced chemical liquid plugs shift back and forth under pneumatic pressure. Below each nanopore is a testing tube that accepts appropriate nanoscale chemical droplets from the microchannel above to perform biochemical tests. Each tube may require several different chemicals in sequence to get proper results. Liquid chemicals required in different tubes may be dropped simultaneously in a round if the liquid plug sequence in the microchannel above matches the chemical requirements in these tubes. The sizes of testing problems in terms of the numbers of tubes, liquid chemicals required in each tube and liquid plugs in the microchannel are large, efficient testing procedure requires careful "round" scheduling in order to shorten the testing time span. In this research, we model the biochemical test scheduling as the fixed plug sequence problem (FPSP), where the liquid plug layout in the microchannel is given. We show that the FPSP is NP-hard in general, and then develop both exact and heuristic algorithms. The computational performances of the proposed algorithms are provided and contrasted.