{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T04:58:41Z","timestamp":1768453121323,"version":"3.49.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["IIS-0312352CCF-0541055"],"award-info":[{"award-number":["IIS-0312352CCF-0541055"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0312352CCF-0541055"],"award-info":[{"award-number":["IIS-0312352CCF-0541055"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>Microfluidic biochips offer a promising platform for massively parallel DNA analysis, automated drug discovery, and real-time biomolecular recognition. Current techniques for full-custom design of droplet-based \u201cdigital\u201d biochips do not scale well for concurrent assays and for next-generation system-on-chip (SOC) designs that are expected to include microfluidic components. We propose a system design methodology that attempts to apply classical high-level synthesis techniques to the design of digital microfluidic biochips. We focus here on the problem of scheduling bioassay functions under resource constraints. We first develop an optimal scheduling strategy based on integer linear programming. However, because the scheduling problem is NP-complete, we also develop two heuristic techniques that scale well for large problem instances. A clinical diagnostic procedure, namely multiplexed in-vitro diagnostics on human physiological fluids, is first used to illustrate and evaluate the proposed method. Next, the synthesis approach is applied to a protein assay, which serves as a more complex bioassay application. The proposed synthesis approach is expected to reduce human effort and design cycle time, and it will facilitate the integration of microfluidic components with microelectronic components in next-generation SOCs.<\/jats:p>","DOI":"10.1145\/1324177.1324178","type":"journal-article","created":{"date-parts":[[2008,2,8]],"date-time":"2008-02-08T15:32:16Z","timestamp":1202484736000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":164,"title":["High-level synthesis of digital microfluidic biochips"],"prefix":"10.1145","volume":"3","author":[{"given":"Fei","family":"Su","sequence":"first","affiliation":[{"name":"Intel Corporation, Folsom, CA"}]},{"given":"Krishnendu","family":"Chakrabarty","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}]}],"member":"320","published-online":{"date-parts":[[2008,1,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Aarts E. and Korst J. 1989. Simulated Annealing and Boltzmann Machines. John Wiley.   Aarts E. and Korst J. 1989. Simulated Annealing and Boltzmann Machines. John Wiley.","DOI":"10.1111\/j.1467-9574.1989.tb01245.x"},{"key":"e_1_2_1_2_1","unstructured":"Advanced Liquid Logic Inc. www.liquid-logic.com.  Advanced Liquid Logic Inc. www.liquid-logic.com."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/54.124513"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.6.2.154"},{"key":"e_1_2_1_5_1","volume-title":"lpsolve","author":"Berkelaar M.","unstructured":"Berkelaar , M. lpsolve . Eindhoven University of Technology , Eindhoven, Netherlands . ftp:\/\/ftp.ics.ele.tue.nl\/pub\/lp_solve. Berkelaar, M. lpsolve. Eindhoven University of Technology, Eindhoven, Netherlands. ftp:\/\/ftp.ics.ele.tue.nl\/pub\/lp_solve."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1308031"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.282.5388.484"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/240518.240524"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 32--52","author":"Cho S. K.","unstructured":"Cho , S. K. , Fan , S. K. , Moon , H. , and Kim , C. J . 2002. Toward digital microfluidic circuits: Creating, transporting, cutting and merging liquid droplets by electrowetting-based actuation . In Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 32--52 . Cho, S. K., Fan, S. K., Moon, H., and Kim, C. J. 2002. Toward digital microfluidic circuits: Creating, transporting, cutting and merging liquid droplets by electrowetting-based actuation. In Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 32--52."},{"key":"e_1_2_1_10_1","unstructured":"CoventorWare. Micro-electro-mechanical systems. http:\/\/www.coventor.com.  CoventorWare. Micro-electro-mechanical systems. http:\/\/www.coventor.com."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/996070.1009902"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.969439"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.2007.8"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the SPIE Lab-on-a-Chip: Platforms, Devices, and Applications. L. A. Smith and D. Sobek, Eds. 5591","author":"Fair R. B.","unstructured":"Fair , R. B. , Khlystov , A. , Srinivasan , V. , Pamula , V. K. , and Weaver , K. N . 2004. Integrated chemical\/biochemical sample collection, pre-concentration, and analysis on a digital microfluidic lab-on-a-chip platform . In Proceedings of the SPIE Lab-on-a-Chip: Platforms, Devices, and Applications. L. A. Smith and D. Sobek, Eds. 5591 , 113--124. Fair, R. B., Khlystov, A., Srinivasan, V., Pamula, V. K., and Weaver, K. N. 2004. Integrated chemical\/biochemical sample collection, pre-concentration, and analysis on a digital microfluidic lab-on-a-chip platform. In Proceedings of the SPIE Lab-on-a-Chip: Platforms, Devices, and Applications. L. A. Smith and D. Sobek, Eds. 5591, 113--124."},{"issue":"5","key":"e_1_2_1_15_1","first-page":"1","article-title":"Electrowetting-based on-chip sample processing for integrated microfluidics","volume":"32","author":"Fair R. B.","year":"2003","unstructured":"Fair , R. B. , Srinivasan , V. , Paik , P. , Ren , H. , and Pamula , V. K. 2003 . Electrowetting-based on-chip sample processing for integrated microfluidics . In Proceedings of the IEEE International Electronic Devices Meeting (IEDM). 32 . 5 . 1 -- 32 .5.4. Fair, R. B., Srinivasan, V., Paik, P., Ren, H., and Pamula, V. K. 2003. Electrowetting-based on-chip sample processing for integrated microfluidics. In Proceedings of the IEEE International Electronic Devices Meeting (IEDM). 32.5.1--32.5.4.","journal-title":"Proceedings of the IEEE International Electronic Devices Meeting (IEDM)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/82.799682"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.283.5398.57"},{"key":"e_1_2_1_18_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability---A Guide to the Theory of NP-Completeness. Freeman New York NY.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability---A Guide to the Theory of NP-Completeness. Freeman New York NY."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Workshop on the Algorithmic Foundations of Robotics.","author":"Griffith E.","unstructured":"Griffith , E. and Akella , S . 2004. Coordinating multiple droplets in planar array digital microfluidics systems . In Proceedings of the Workshop on the Algorithmic Foundations of Robotics. Griffith, E. and Akella, S. 2004. Coordinating multiple droplets in planar array digital microfluidics systems. In Proceedings of the Workshop on the Algorithmic Foundations of Robotics."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2143(03)00144-6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.288.5471.1624"},{"key":"e_1_2_1_22_1","unstructured":"International Technology Roadmap for Semiconductors (ITRS). http:\/\/public.itrs.net\/Files\/2003ITRS\/Home2003.htm.  International Technology Roadmap for Semiconductors (ITRS). http:\/\/public.itrs.net\/Files\/2003ITRS\/Home2003.htm."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1332799"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/996070.1009901"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/344588.344618"},{"key":"e_1_2_1_26_1","volume-title":"Synthesis and Optimization of Digital Circuits","author":"Micheli G.","unstructured":"Micheli , G. De . 1994. Synthesis and Optimization of Digital Circuits . McGraw-Hill, New York , NY. Micheli, G. De. 1994. Synthesis and Optimization of Digital Circuits. McGraw-Hill, New York, NY."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the IEEE Conference on VLSI System Level Design. 96--101","author":"Mukherjee T.","unstructured":"Mukherjee , T. and Fedder , G. K . 1998. Design methodology for mixed-domain systems-on-a-chip {MEMS design} . In Proceedings of the IEEE Conference on VLSI System Level Design. 96--101 . Mukherjee, T. and Fedder, G. K. 1998. Design methodology for mixed-domain systems-on-a-chip {MEMS design}. In Proceedings of the IEEE Conference on VLSI System Level Design. 96--101."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Paik P. Pamula V. K. and Fair R. B. 2003. Rapid droplet mixers for digital microfluidic systems. Lab on a Chip 3 253--259.  Paik P. Pamula V. K. and Fair R. B. 2003. Rapid droplet mixers for digital microfluidic systems. Lab on a Chip 3 253--259.","DOI":"10.1039\/B307628H"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 722--725","author":"Pamula K.","unstructured":"Pamula , K. , Srinivasan , V. , Chakrapani , H. , Fair , R. B. , and Toone , E. J . 2005. A droplet-based lab-on-a-chip for colorimetric detection of nitroaromatic explosives . In Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 722--725 . Pamula, K., Srinivasan, V., Chakrapani, H., Fair, R. B., and Toone, E. J. 2005. A droplet-based lab-on-a-chip for colorimetric detection of nitroaromatic explosives. In Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 722--725."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382577"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1308534"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Pollack M. G. Shenderov A. D. and Fair R. B. 2002. Electrowetting-based actuation of droplets for integrated microfluidics. Lab on a Chip 2 96--101.  Pollack M. G. Shenderov A. D. and Fair R. B. 2002. Electrowetting-based actuation of droplets for integrated microfluidics. Lab on a Chip 2 96--101.","DOI":"10.1039\/b110474h"},{"key":"e_1_2_1_34_1","unstructured":"Ren H. and Fair R. B. 2002. Micro\/nano liter droplet formation and dispensing by capacitance metering and electrowetting actuation. Technical Digest of IEEE-NANO 36--38.  Ren H. and Fair R. B. 2002. Micro\/nano liter droplet formation and dispensing by capacitance metering and electrowetting actuation. Technical Digest of IEEE-NANO 36--38."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe. 329--334","author":"Ricketts J.","unstructured":"Ricketts , J. Irick , K. Vijaykrishnan , N. and Irwin , M. J . 2006. Priority scheduling in digital microfluidics-based biochips . In Proceedings of the Conference on Design, Automation and Test in Europe. 329--334 . Ricketts, J. Irick, K. Vijaykrishnan, N. and Irwin, M. J. 2006. Priority scheduling in digital microfluidics-based biochips. In Proceedings of the Conference on Design, Automation and Test in Europe. 329--334."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690450215"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0009-8981(02)00093-1"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the International Conference on Sold-State Sensors and Actuators (Transducers). 11--16","author":"Senturia S.","year":"1987","unstructured":"Senturia , S. 1987 . Microfabricated structures for the measurement of mechanical properties and adhesion of thin films . In Proceedings of the International Conference on Sold-State Sensors and Actuators (Transducers). 11--16 . Senturia, S. 1987. Microfabricated structures for the measurement of mechanical properties and adhesion of thin films. In Proceedings of the International Conference on Sold-State Sensors and Actuators (Transducers). 11--16."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 201--205","author":"Shapiro H.","unstructured":"Shapiro , H. , Moon , H. , Garrell , R. , and Kim , C. J . 2003. Modeling of electrowetted surface tension for addressable microfluidic systems: dominant physical effects, material dependences, and limiting phenomena . In Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 201--205 . Shapiro, H., Moon, H., Garrell, R., and Kim, C. J. 2003. Modeling of electrowetted surface tension for addressable microfluidic systems: dominant physical effects, material dependences, and limiting phenomena. In Proceedings of the IEEE Conference on Micro-Electro-Mechanical Systems. 201--205."},{"key":"e_1_2_1_40_1","unstructured":"Silicon Biosystems. What is DEPArrayTM&quest; http:\/\/www.siliconbiosystems.com\/technology\/DEPArray.htm.  Silicon Biosystems. What is DEPArray TM &quest; http:\/\/www.siliconbiosystems.com\/technology\/DEPArray.htm."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the International Conference on Genetic Algorithms. 230--236","author":"Spears W. M.","unstructured":"Spears , W. M. and Dejong , K. A . 1991. On the virtues of parameterized uniform crossover . In Proceedings of the International Conference on Genetic Algorithms. 230--236 . Spears, W. M. and Dejong, K. A. 1991. On the virtues of parameterized uniform crossover. In Proceedings of the International Conference on Genetic Algorithms. 230--236."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.294849"},{"key":"e_1_2_1_43_1","unstructured":"Srinivasan V. Pamula V. K. and Fair R. B. 2004. An integrated digital microfluidic lab-on-a-chip for clinical diagnostics on human physiological fluids. Lab on a Chip 310--315.  Srinivasan V. Pamula V. K. and Fair R. B. 2004. An integrated digital microfluidic lab-on-a-chip for clinical diagnostics on human physiological fluids. Lab on a Chip 310--315."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.580145"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the International Conference on Micro Total Analysis Systems. 1287--1290","author":"Srinivasan V.","unstructured":"Srinivasan , V. , Pamula , V. K. , Pollack , M. G. , and Fair , R. B . 2003. Clinical diagnostics on human whole blood, plasma, serum, urine, saliva, sweat, and tears on a digital microfluidic platform . In Proceedings of the International Conference on Micro Total Analysis Systems. 1287--1290 . Srinivasan, V., Pamula, V. K., Pollack, M. G., and Fair, R. B. 2003. Clinical diagnostics on human whole blood, plasma, serum, urine, saliva, sweat, and tears on a digital microfluidic platform. In Proceedings of the International Conference on Micro Total Analysis Systems. 1287--1290."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142980.1142987"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.855956"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the Design, Automation and Test in Europe (DATE) Conference. 323--328","author":"Su F.","unstructured":"Su , F. , Hwang , W. and Chakrabarty , K . 2006. Droplet routing in the synthesis of digital microfluidic biochips . In Proceedings of the Design, Automation and Test in Europe (DATE) Conference. 323--328 . Su, F., Hwang, W. and Chakrabarty, K. 2006. Droplet routing in the synthesis of digital microfluidic biochips. In Proceedings of the Design, Automation and Test in Europe (DATE) Conference. 323--328."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the IEEE International Test Conference. 883--892","author":"Su F.","unstructured":"Su , F. , Ozev , S. , and Chakrabarty , K . 2004. Concurrent testing of droplet-based microfluidic systems for multiplexed biomedical assays . In Proceedings of the IEEE International Test Conference. 883--892 . Su, F., Ozev, S., and Chakrabarty, K. 2004. Concurrent testing of droplet-based microfluidic systems for multiplexed biomedical assays. In Proceedings of the IEEE International Test Conference. 883--892."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSEN.2005.848127"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1076996"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1047-8477(03)00049-2"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0924-8579(02)00366-7"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2003.813570"},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Walker R. A. and Camposano R. 1991. A Survey of High-Level Synthesis Systems. Kluwer Academic Publishers Boston MA.  Walker R. A. and Camposano R. 1991. A Survey of High-Level Synthesis Systems. Kluwer Academic Publishers Boston MA.","DOI":"10.1007\/978-1-4615-3968-1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/28.703965"},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","unstructured":"Zeng J. and Korsmeyer F. T. 2004. Principles of droplet electrohydrodynamics for lab-on-a-chip. Lab on a Chip 4 265--277.  Zeng J. and Korsmeyer F. T. 2004. Principles of droplet electrohydrodynamics for lab-on-a-chip. Lab on a Chip 4 265--277.","DOI":"10.1039\/b403082f"},{"key":"e_1_2_1_58_1","volume-title":"Microelectrofluidic Systems: Modeling and Simulation","author":"Zhang T.","year":"2002","unstructured":"Zhang , T. , Chakrabarty , K. , and Fair , R. B . 2002 . Microelectrofluidic Systems: Modeling and Simulation . CRC Press , Boca Raton, FL . Zhang, T., Chakrabarty, K., and Fair, R. B. 2002. Microelectrofluidic Systems: Modeling and Simulation. CRC Press, Boca Raton, FL."},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Zhao Y. and Cho S. K. 2006. Microparticle sampling by electrowetting-actuated droplet sweeping. Lab on a Chip 6 137--144.  Zhao Y. and Cho S. K. 2006. Microparticle sampling by electrowetting-actuated droplet sweeping. Lab on a Chip 6 137--144.","DOI":"10.1039\/B511645G"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1324177.1324178","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1324177.1324178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:15Z","timestamp":1750254975000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1324177.1324178"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":58,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1145\/1324177.1324178"],"URL":"https:\/\/doi.org\/10.1145\/1324177.1324178","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"value":"1550-4832","type":"print"},{"value":"1550-4840","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-01-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}