可拆分工作平行机排序问题地研究

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

1、复旦大学硕士毕业论文可拆分工作的·f￡行机排序问题研究摘要本文以现代制造业中标准化产品大规模生产中的工作分配为背景，将平行机排序问题(PMS)拓展，研究了一类具有可拆分工作的平行机排序问题(己[setup&splitco)。在准备时间不为0的情况下，该问题是NP．难问题。因此本文将重点放在启发式算法的设计和改进上，并用学术界公认的“竞争比分析"来判别算法的优劣。本文的贡献主要如下所示：对于有独立准备时间的可拆分平行机排序问题：1．提出针对SmallBatch问题的新算法机制N。算法N改进了已有算法的第二阶段即工作的拆分规则，并证明了N在任何情况下都不差于原来的算法

2、。具体地，把LSU算法的竞争比由max{3／2—1／(4M一4)，5／3—1／M)改进到NLSU算法的l34519／3I，3M3M一4、maXl三一—4M—-2，一3一五F忑f；把LBT算法的竞争比由max{荔i鬲’芴v-历-j改进到3MNLBT算法的—2M—+l。2．分析了一类特殊情况：针对M=2时SmallBatch问题，创新性地提出了一类Ll(T算法，按照q+乃(七≥1)来构造初始排序，并提出后：3时，等：号，这一结果比M=2时已有最好结果要更优。3．分析了一类特殊情况，即M=2时LargeBatch问题的解法。提出：任何无耽搁拆分的算法都能取得LargeB

3、atch问题的最优解。任何SmallBatch算法的最坏情况对M=2时可拆分平行机排序问题都适用。4．充实了针对LargeBatch问题的研究成果(表格5．2所示)，提出了算法LSLSU，7l其最坏情况比为～4M，但时间复杂度比ML算法要好。证明了ML算法的竞争比f3151ygmaxl互一—4M—-4，一3一万f，统一了SmallBatch问题和LargeBatch问题的竞争比。对于有非独立准备时间的可拆分平行机排序问题：5．提出了两类启发式算法，并简单给出了最坏情况分析。若呀s口Pj，DLSS算法的最坏情况比为(1+口)(2一亩)，DLll算法的最坏情况比为(1

4、+口)(2一亩)。对复旦大学硕：E毕业论文可拆分工作的，f￡行机排序问题研究Soy20，勺

5、Swithsplittingjobstosolveproblemsinmassproductionofstandardproducts．WiththreeparamatersmeⅡlod，theprobl锄isnotedas己Isetup&sp圳C咄．Withthesetuptimenotequal0，theproblemisNP．hard．Thepaperfocusesontheimprovementandanalysisofheuristicsandweemploycompetitiveratiomethodtoevaluatetheperformaceofo

6、urheuristics，whichiswellacceptedbythescholars．Theresearchhasseveralfollowingcontributions：AstoPMSwithsplittingjobsandindependentsetuptime,1．Thepaperprovidesabettermechanismtosolvethesmallbatchproblembyimprovingthesecondperiodoftheoriginalmethod．Withthesameschedulingrulesofthefirstperi

7、od，weimprovetheworstcaseofexistingmethods．Concretely,weimproveLSU，scompertiveratio‰max{3／2—1／(4M一4)，5／3—1／M)toNLSU，sI34519／3lm觚1—4M-，一33M+2，，LBT24M23’sl。，s．3M3M一4．3M---m觚t丽，‘_2．toNLBT’—2M—+12M12M2tONLl5S2．、+’·2．ForSmallBatchproblemswhenM=2，webringouttheLKTmethod，schedulingaCcordingt0鸣

8、+Pj(七