资源描述：
《加权分批运送排序问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、华东理工大学硕士学位论文第I页加权分批运送排序问题的研究摘要这篇论文主要研究单机加权分批运送排序问题(SchedulingwithWeightedBatchDelivery，简记为SWBD)，并把一些结果推广至平行机加权分批运送排序问题。在SWBD中，一组独立的工件均在零时刻到达，每个工件有相应的加工时间和权重，且加工不允许中断，当所在批中最后一个工件完工后一起运走。问如何把这些工件安排在一台机器上加工，并适当地分批运送，使得总费用最小?这里，总费用包括两部分:一部分是运送费用，为分批数的非减函数，设为分批数的常数倍:另一部分是由于
2、不及时运送而导致的附加费用，是工件运走时间总权和的非减函数，设为工件运走时间总权和。本文证明了SWBD是NP困难的，并用动态规划方法给出了一个算法，当分批数有固定上界时，即r<_U时，该算法为拟多项式的。并将该算法推广至平行机加权分批运送排序问题。我们给出一个复杂度为O(n')的近似算法，数值检验说明该算法效果较好。我们引进了最优顺序的概念，并在此基础上证明了目标函数关于分批数的凸性。作为SWBD的一种可解情形，当最优顺序已知时，我们给出一个多项式时间算法。本文的最后给出一个优化模型，把SWBD与广义指派问题联系起来。关键词:分批运
3、送，排序，NP困难，动态规划华东理工大学硕士学位论文第n页TheStudyofSchedulingwithWeightedBatchDeliveryAbstractInthispaper,westudySchedulingwithWeightedBatchDelivery(abbreviatedasSWBD).Therearenjobstobeprocessedonasinglemachineandpreemptionisnotallowed.Howtoscheduleandbatchthemsuchthatthetotalcost
4、isminimized?Thetotalcostis艺w;D;+cr,whereD;isthedeliverytimeofjobi,whichisequaltocompletiontimeofthelastjobinthebatchtowhichjobibelongs;wiistheweightofjobi;risthenumberofbatches;cisthedeliverycostofeachbatch,whichisdefinedasaconstant.WeproveSWBD,whetheronsinglemachineor
5、parallelmachine,isNP-hard.Togettheoptimalsolutiononsinglemachine,wedevelopaDynamicProgrammingAlgorithm,andweextendthealgorithmtoparallelmachine.Whenthebatchnumberhasafixedupperbound,thealgorithmispseudopolynomial.Wealsopresentanapproximationalgorithmwithcomplexity0(n')
6、.WefirstintroducetheconceptofOptimalSequence,andwhentheOptimalSequenceisgiven,asasolvablecaseofSWBD,wepresentapolynomialalgorithmwithcomplexityO(n0).BasedontheOptimalSequence,theoptimalvalueoftotalcost,asafunctionoftheprescribednumberofbatches,isprovedtobeconvex.Finall
7、y,amodelisgiven,whichconnectsSWBDwithGeneralizedAssignmentProblem.Keywords:BatchDelivery,Scheduling,NP-hard,DynamicProgramming作者声明我郑重声明:本人格守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的结果。除文中明确注明和引用的内容外，本论文不包含任何他人已经发表或撰写过的内容。论文为本人亲自撰写，并对所写内容负责。论文作者签名:称4,名2,003年b}么日华东理工大
8、学硕士学位论文第1页加权分批运送排序问题的研究第一节引言1.1排序问题介绍排序理论与应用是组合最优化中一个十分活跃的研究分支，同时也是实际中应用最广的运筹学分支之一排序间题产生的背景主要是机器制造，后来广泛应用于计算机系统、运输调度和
