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

Dong Tang, Udatta S. Palekar

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)942-953
Number of pages12
JournalComputers and Operations Research
Issue number6
StatePublished - Jun 2011
Externally publishedYes


  • Heuristic
  • Mathematical programming models
  • Micro/nano biochemical testing
  • Scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'Scheduling large-scale micro/nano biochemical testing: Exact and heuristic algorithms'. Together they form a unique fingerprint.

Cite this