Multi-objective optimization algorithm for efficient pin-constrained droplet routing technique in digital microfluidic biochip

Design automation for digital microfluidic biochip comprises of many combinatorial optimization problems, which are NP-complete in nature. Efficient optimization algorithms to solve them is in dearth till date. In this paper, we propose a multi-objective optimization algorithm that simultaneously minimizes several resources during bioassay operations in a digital microfluidic biochip. We design the progressive droplet routing as a constrained multi-objective optimization problem considering three objective functions to be optimized, named (i) electrode usages, (ii) routing completion time, or latest arrival time, and (iii) control pin allocation. A composite objective function is constructed by a weighted sum of the first two objective functions. This composite function is minimized pertaining to an upper bound on the third objective function, control pin allocation. A fractional constant weight factor (λ) is chosen to confer upon the necessary weightage on the two factors involved in the composite objective function for accurate optimization procedure. We perform experimentations with several existing benchmarks, and experimental results are quite encouraging.