Schedulinglarge-scalemicro/nanobiochemicaltesting: Exact andheuristicalgorithms

Weconsideramicro/nanofluidictoolbitthatconsistsof a setofidenticaltestingunits,eachofwhichcontains a microchannelthathasanarrayofequallyspacednanoporesopenedalongit.Ineachmicrochannel,same equallyspacedchemicalliquidplugsshiftbackandforthunderpneumaticpressure.Beloweachnanoporeisa testing tubethatacceptsappropriatenanoscalechemicaldropletsfromthemicrochannelabovetoperform biochemicaltests.Eachtubemayrequireseveraldifferentchemicalsinsequencetogetproperresults.Liquid chemicalsrequiredindifferenttubesmaybedroppedsimultaneouslyinaroundiftheliquidplugsequencein themicrochannelabovematchesthechemicalrequirementsinthesetubes.Thesizesoftestingproblemsin terms ofthenumbersoftubes,liquidchemicalsrequiredineachtubeandliquidplugsinthemicrochannelare large, efficienttestingprocedurerequirescareful‘‘round’’schedulinginordertoshortenthetestingtimespan. In thisresearch,wemodelthebiochemicaltestschedulingasthefixedplugsequenceproblem(FPSP),where the liquidpluglayoutinthemicrochannelisgiven.WeshowthattheFPSPisNP-hardingeneral,andthen develop bothexactandheuristicalgorithms.Thecomputational performancesoftheproposedalgorithmsare provided andcontrasted.