ABC-GNX: A Hybrid Algorithm for Scheduling of Digital Microfluidic Biochip Operations

摘要

Digital microfluidic biochips (DMFB) are a part of lab-on-a-chip (LOC) devices. DMFBs are designed to carry out biochemical analysis efficiently. Scheduling DMFB operations is a constrained optimization problem, and the respective decision problem is NP-complete. We propose a hybrid artificial bee colony (ABC) algorithm using generalized N-point crossover (GNX) based Scheduling for DMFB operations. There are several schedules possible for a given set of microfluidic operations. Heuristic algorithms are capable of finding one such possible schedule from search space (possible schedules) while our proposed ABC-GNX perturbs through search space, evaluates several possible schedules, and outputs optimal schedule among the evaluated schedules. While several iterative improvement based algorithms exist, which can do the same but, the proposed ABC-GNX algorithm finds the optimal solution in less execution time as compared to existing algorithms. ABC-GNX produces a higher number of optimal assay completion times and less execution time on evaluated benchmarks.