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 (C) 2010 Elsevier Ltd All rights reserved
scheduling micro/nano biochemical testing heuristic mathematical programming models