{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T07:50:01Z","timestamp":1767772201381,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,10,14]],"date-time":"2017-10-14T00:00:00Z","timestamp":1507939200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"UC Riverside Dissertation Year Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1035603"],"award-info":[{"award-number":["CNS-1035603"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation Graduate Research Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2018,1,31]]},"abstract":"<jats:p>\n            Digital microfluidics based on electrowetting-on-dielectric technology is poised to revolutionize many aspects of chemistry and biochemistry through miniaturization, automation, and software programmability. Digital microfluidic biochips (DMFBs) offer ample spatial parallelism, which is then exposed to the compiler. The first problem that a DMFB compiler must solve is resource-constrained scheduling, which is NP-complete. If the compiler is applied off-line, then long-running algorithms that produce solutions of high quality, such as iterative improvement or branch-and-bound search, can be applied; in an online context, where a biochemical reaction is to be executed as soon as it is specified by the programmer, heuristics that sacrifice solution quality to attain a fast runtime are used. This article describes in detail the algorithms and heuristics that have been proposed for resource-constrained scheduling, focusing on several recent contributions: path scheduling and force-directed list scheduling. It also discusses shortcomings and limitations of existing optimal scheduling problem formulations based on Integer Linear Programming and presents an updated formulation that addresses these issues. The algorithms are compared and evaluated on an extensive benchmark suite of biochemical assays used for applications, such as\n            <jats:italic>in vitro<\/jats:italic>\n            diagnostics, protein crystallization, and automated sample preparation.\n          <\/jats:p>","DOI":"10.1145\/3093930","type":"journal-article","created":{"date-parts":[[2017,10,16]],"date-time":"2017-10-16T12:37:42Z","timestamp":1508157462000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Resource-Constrained Scheduling for Digital Microfluidic Biochips"],"prefix":"10.1145","volume":"14","author":[{"given":"Kenneth","family":"O'neal","sequence":"first","affiliation":[{"name":"University of California, Riverside, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Grissom","sequence":"additional","affiliation":[{"name":"Azusa Pacific University, Azusa, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip","family":"Brisk","sequence":"additional","affiliation":[{"name":"University of California, Riverside, Riverside, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,10,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2015.02.004"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.6.2.154"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/1-4020-5123-9_12"},{"key":"e_1_2_1_4_1","unstructured":"Stephen P. Bradley Arnoldo C. Hax and Thomas L. Magnanti. 1977. Applied Mathematical Programming. Addison-Wesley 272--319.  Stephen P. Bradley Arnoldo C. Hax and Thomas L. Magnanti. 1977. Applied Mathematical Programming. Addison-Wesley 272--319."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISED.2012.73"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISED.2013.22"},{"key":"e_1_2_1_7_1","unstructured":"Giovanni De Micheli. 1994. Synthesis and Optimization of Digital Circuits. McGraw-Hill Inc.  Giovanni De Micheli. 1994. Synthesis and Optimization of Digital Circuits. McGraw-Hill Inc."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tsf.2010.12.094"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Jie Ding Krishnendu Chakrabarty and Richard B. Fair. 2001. Scheduling of microfluidic operations for reconfigurable two-dimensional electrowetting arrays. IEEE TCAD 20 12 (Dec. 2001) 1463--1468.  Jie Ding Krishnendu Chakrabarty and Richard B. Fair. 2001. Scheduling of microfluidic operations for reconfigurable two-dimensional electrowetting arrays. IEEE TCAD 20 12 (Dec. 2001) 1463--1468.","DOI":"10.1109\/43.969439"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380445.2380510"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228367"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2290582"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Daniel Grissom Christopher Curtis and Philip Brisk. 2014. Interpreting assays with control flow on digital microfluidic biochips. ACM JETC 10 3 Article 24 (Apr. 2014).  Daniel Grissom Christopher Curtis and Philip Brisk. 2014. Interpreting assays with control flow on digital microfluidic biochips. ACM JETC 10 3 Article 24 (Apr. 2014).","DOI":"10.1145\/2567669"},{"volume-title":"Proceedings of VLSI-SoC. 7--12","year":"2012","author":"Grissom Daniel","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2015.01.004"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1039\/c2lc40273d"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Juinn-Dar Huang Chia-Hung Liu and Huei-Shan Lin. 2013. Reactant and waste minimization in multi- target sample preparation on digital microfluidic biochips. IEEE TCAD 32 10 (Oct. 2013) 1484--1494.  Juinn-Dar Huang Chia-Hung Liu and Huei-Shan Lin. 2013. Reactant and waste minimization in multi- target sample preparation on digital microfluidic biochips. IEEE TCAD 32 10 (Oct. 2013) 1484--1494.","DOI":"10.1109\/TCAD.2013.2263035"},{"volume-title":"Proceedings of IEEE MEMS Conference. 428--431","year":"2012","author":"Huang Lian-Xin","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/VTS.2015.7116246"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593135"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SOCC.2013.6749681"},{"volume-title":"Retrieved","year":"2016","author":"Sourceforge Solve","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Lingzhi Luo and Srinivas Akella. 2011. Optimal scheduling of biochemical analyses on digital microfluidic systems. IEEE T-ASE 8 1 (Jan. 2011) 216--227.  Lingzhi Luo and Srinivas Akella. 2011. Optimal scheduling of biochemical analyses on digital microfluidic systems. IEEE T-ASE 8 1 (Jan. 2011) 216--227.","DOI":"10.1109\/TASE.2010.2053201"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2012.2211104"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2014.2303948"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10617-010-9059-x"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Elena Maftei Paul Pop and Jan Madsen. 2013. Module-based synthesis of digital microfluidic biochips with droplet-aware operation execution. ACM JETC 9 1 Article 2 (Feb. 2013).  Elena Maftei Paul Pop and Jan Madsen. 2013. Module-based synthesis of digital microfluidic biochips with droplet-aware operation execution. ACM JETC 9 1 Article 2 (Feb. 2013).","DOI":"10.1145\/2422094.2422096"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1039\/C1LC20851A"},{"volume-title":"Proceedings of VLSI-SoC","year":"2012","author":"O'Neal Kenneth","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1039\/B307628H"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.31522"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1039\/b110474h"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2006.244178"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2061790"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Fei Su and Krishnendu Chakrabarty. 2006. Module placement for fault-tolerant microfluidics-based biochips. ACM TODAES 11 3 (July 2006) 682--710.  Fei Su and Krishnendu Chakrabarty. 2006. Module placement for fault-tolerant microfluidics-based biochips. ACM TODAES 11 3 (July 2006) 682--710.","DOI":"10.1145\/1142980.1142987"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Fei Su and Krishnendu Chakrabarty. 2008. High-level synthesis of digital microfluidic biochips. ACM JETC 3 4 Article 1 (Jan. 2008).  Fei Su and Krishnendu Chakrabarty. 2008. High-level synthesis of digital microfluidic biochips. ACM JETC 3 4 Article 1 (Jan. 2008).","DOI":"10.1145\/1324177.1324178"},{"volume-title":"Proceedings of DATE","year":"2006","author":"Su Fei","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","unstructured":"UCRa. Digital Microfluidic Biochip Static Synthesis Simulator. Retrieved from http:\/\/microfluidics.cs.ucr.edu\/staticsim.html.  UCRa. Digital Microfluidic Biochip Static Synthesis Simulator. Retrieved from http:\/\/microfluidics.cs.ucr.edu\/staticsim.html."},{"key":"e_1_2_1_39_1","unstructured":"UCRb. Dilution Framwork. Retrieved from http:\/\/microfluidics.cs.ucr.edu\/DilutionFramework.html.  UCRb. Dilution Framwork. Retrieved from http:\/\/microfluidics.cs.ucr.edu\/DilutionFramework.html."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.402495"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Tao Xu and Krishnendu Chakrabarty. 2008. Integrated droplet routing and defect tolerance in the synthesis of digital microfluidic biochips. ACM JETC 4 3 Article 11 (Aug. 2008).  Tao Xu and Krishnendu Chakrabarty. 2008. Integrated droplet routing and defect tolerance in the synthesis of digital microfluidic biochips. ACM JETC 4 3 Article 11 (Aug. 2008).","DOI":"10.1145\/1389089.1389091"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBCAS.2008.918283"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Ping-Hung Yuh Chia-Lin Yang and Yao-Wen Chang. 2007. Placement of defect-tolerant digital microfluidic biochips using the T-tree formulation. ACM JETC 3 3 Article 13 (Nov. 2007).  Ping-Hung Yuh Chia-Lin Yang and Yao-Wen Chang. 2007. Placement of defect-tolerant digital microfluidic biochips using the T-tree formulation. ACM JETC 3 3 Article 13 (Nov. 2007).","DOI":"10.1145\/1295231.1295234"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2012.2183369"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3093930","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3093930","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3093930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:16Z","timestamp":1750217416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3093930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,14]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1,31]]}},"alternative-id":["10.1145\/3093930"],"URL":"https:\/\/doi.org\/10.1145\/3093930","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"type":"print","value":"1550-4832"},{"type":"electronic","value":"1550-4840"}],"subject":[],"published":{"date-parts":[[2017,10,14]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}