中国科技论文在线wwpaper.edu无界平行分批机器上的最小化最大流程的在线排序李文华1，原晋江11郑州大学数学系，郑州450001摘要：本文研究无界平行分批机器上的最小化最大流程的在线排序。研究表明，不存在竞争比小于1+αm的在线算法。其中，αm是方程α2+(m+1)α−1=0的正根。这一下界对工件具有相同加工时间的情形仍然适用。本文给出了一个竞争比为1+1/m的在线算法。对工件具有相同加工时间的情形进一步给出了争比为1+αm的最佳可能在线算法。关键词：运筹学、在线排序、平行批机器、最大流程、竞争比：O223Onlineschedulingonunboundedparallel-batchmachinestominimizemaximumflow-timeWenhuaLiand激n激angYuanDepartmentofMathematics,ZhengzhouUniversity,Zhengzhou,Henan450001Abstract:Thispaperconsidersonlineschedulingonmunboundedparallel-batchmachinestominimizemaximumflow-timeofthejobs.Theresearchshowsthatnoonlinealgorithmcanhaveacompetitiveratiolessthan1+αm,whereαmisthepositiverootofα2+(m+1)α−1=0,andthislowerboundisstillvalidevenwhenalljobshavethesameprocessing.Anonlinealgorithmofcompetitiveratio1+1/mispresentedinthepaper.Whenthejobshavethesameprocessing,abestpossibleonlinealgorithmofcompetitiveratio1+αmisestablished.Keywords:operationsresearch;onlinescheduling;parallel-batchmachines;maximumflow-time;competitiveratio.0IntroductionBatchschedulinghasbeenextensivelystudiedinthelasttwodecades.Inparallel-batchscheduling,amachinecanprocessseveraljobsasabatchsimultaneouslyaslongasthebatchcapacityisnotexceeded.Heretheprocessingtimeofabatchisdefinedtobethemaximumprocessingtimeofjobsinthebatch,andalljobsinabatchhavethesamestartingtimeandthesamecompletiontime,respectively.Thismodeliswidelyappliedinsemiconductormanufac-turing.Intheliterature,forexample,Uzsoyetal.[1,2],Avramidisetal.[3]andMathirajanResearchsupportedbySRFDP(20070459002),NSFC(10971201),NSFC(10901142)andNSFHN(082300410070).李文华（1965-），女，教授，主要研究方向：组合最优化。通信作者：原晋江（1965-），男，教授，主要研究方向：组合最优化。邮箱：yuanjj@zzu.edu-1-whenb=∞.PoonandYu[12]furtherestablishedabestparameterizedcompetitiveratiob=2.ForproblemPm|p-batch,b=∞,online|Cmax,Zhangetal.[11]gavealowerboundofwithcompetitiveratios1+ξmandforunboundedcaseandboundedcase,respectively,√√中国科技论文在线wwpaper.eduandSivakumar[4],therehavebeendetaileddescriptionsofthesemiconductormanufacturingprocess.Therearetwoversionsaboutparallel-batchscheduling:oneisunboundedmodelwithb=∞;theotherisboundedmodelwithb<∞,wherebdenotesthecapacityofeachbatch.Inonlinescheduling,thejobs’informationbecomesknowntotheschedulerbystages.Toomanyversionsaboutonlinearegivenintheliterature.Here,onlinemeansthatjobsarriveovertime.Thequalityofanonlinealgorithmisusuallymeasuredbyitscompetitiveratio.Wesayanonlinealgorithmisρ-competitiveif,foranyinstance,itproducesanobjectivevalueatmostρtheobjectivevaluegivenbyanoff-lineoptimalschedule.Weconsideronlineschedulingonmunboundedparallel-batchmachinestominimizethemaximumflow-timeofthejobs.Intheproblem,wehavemunboundedparallel-batchmachines.EachjobJjhasanarrivaltimerjandaprocessingtimepj,whichareunknowninadvance.Cj=Cj(π)isusedtodenotethecompletiontimeofjobJjinagivenscheduleπ.Theflow-timeofjobJjinscheduleπisdefinedtobeFj(π)=Cj(π)−rj.Themaximumflow-timeofthejobsinπisdefinedbyFmax(π)=maxjFj(π).UsingthestandardschedulingclassificationschemeofLawleretal.[5],theproblemiswrittenasPm|p-batch,b=∞,online|Fmax.Thereareplentyofachievementsonparallel-batchsch...