ABSTRACT
In this chapter, the authors investigate test planning and test resource optimization problems for droplet-based microfluidic arrays. They outline an optimal solution based on integer linear programming (ILP). The authors describe the problem of test planning and test resource optimization. This problem is shown to be NP-hard. The authors propose an optimal solution based on ILP. They present several heuristic algorithms, which are evaluated through simulation experiments. The authors present an analysis of the test planning problem for digital microfluidic biochips. They formulate the test planning problem in terms of graph partitioning and the Hamiltonian path problem from graph theory. The authors develop the test planning problem for multiple sources and multiple sinks. They attempt to partition the directed graph representing the microfluidic array into subgraphs, such that in each subgraph there exists a Hamiltonian path from one source to one sink.
