可拆分工作的平行机排序问题分析

《可拆分工作的平行机排序问题分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、复旦大学硕：E毕业论文可拆分工作的，f￡行机排序问题研究％，20，勺≤口巧的一类特殊问题，提出算法D，其最坏情况比为芳坠≤l+口。oⅢ关键字：可拆分工作、平行机排序、近似算法、最坏情况分析、竞争比中图分类号：C932复旦人学硕上毕业论文可拆分rT作的、F行机排序问题研究AbstractParallelmachinescheduling(PMS)iswidelyusedinmemodenlmanufactu—ngindusny柚dserviceindustⅨESpecially’t11eproblemisextelldedtoPMSwimsplitting

2、jobstosolVeproblemsinmaSsproductionofstandardproducts．wimt11reepa豫matersmetllod，theprobl锄isnotedas己IsP却&印圳C咄．Witllt11ese呻timenotequalO，tlleprobl锄isNP-h砌胁epaperfocusesonmeimproV锄ent锄daIlalySisofh砌SticsandweelIlployComp“tiVemtiomethodtoeValuatemeperf．0彻aceofourhe嘶stics，、池iChiswella

3、cc印tedbymescholars．T}leresearchh嬲seVeralfollowingcontributions：AstoPMSwimSplittingjobs锄dind印eIldentsetuptime’1．Thep印erproVidesabe钍ermechallismtosolVethesmaUbatchproblembyiIIlproVingnlesecondperiodoftlleori舀nalmemod．witllmes锄eschedulingmlcSofmefirStperiod，weimpr0VenleworstcaseofeX

4、istingmetllods．Concretely'weimproveLsu，scompertiveratio缸衄ma)【{3／2一l／(4M一4)，5／3—1／M)toNLsu，sI34519／3lm觚1互一ij历’；一j万五f，LBT，sl24M一2。33M+2J，L廿ls，3M3M一4、3Mm觚t互而，互砀i

5、}t0NLBT’s互而．、2M+l’2M一2’【o州L廿ls2M+l·2．ForSmallBatchpfoblemswheIlM=2，webringouttlleLKTmemod，schedulingaCcordingto鸣+p，(七≥1)i

6、nme6rstp舐od，tllecompetitiveratioofwllichisrelatedt0后(七≥n．w11ilekequals3，wederiveacompetitiverati。。f号，whichisbettermaIlthatofa11yeXistingmemodwheIlM=2．3．ForLa唱eBatchproblemswhellM=2，tllepaperproposesnlataIlyn0一delyschededulinga11dSplittingmethodc柚reachtheoptimals01utiont0La略eBatch

7、problem．4．Thepaperbringsoutmoremetllodsa11dreSultsforLa玛eBatchProbl锄ingeneralcase．Besides，wedevelopmew。rStcasetomaX{3／2—1／(4M一4)，5／3一l／M)，a11dmal【eitthes锄eforbothSmallBatChaIldLa略eBatchproblems．AstoPMSwilhsplittingjobsaIldindependentsetuptime，5．T11ep印erd嘶Vessevemlheuristicsa11d百V

8、egeneralworst—case觚alysisa11ddrawsmeconclusionthatfortheproblemwitll勘≤口乃，DLSSmetllodhaSa复旦大学硕上毕业论文可拆分工作的平行机排序问题研究c。mpetitiverati。lessm觚(1+口)(2一击)a11d。L1Tmeth。dhasac。mpetitiverati。lessmaIl(1+口)(2一云备)．F。raspecialcasewheIl嘞=。，DmetllodhaSacompetitiveratiolessman(1+训．Keywords：splittin

9、gjobs，parallelmacllinesscheduling(PMS)，h