具有不可用区间平行机排序问题近似算法

《具有不可用区间平行机排序问题近似算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学位论文独创性声明本人所呈交的学位论文是在导师的指导下取得的研究成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示了谢意。作者签名：日期：学位论文使用授权声明本人授权沈阳师范大学研究生处，将本人硕士学位论文的全部或部分内容编入有关数据库进行检索；有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，允许论文被查阅和借阅；有权可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密的

2、学位论文在解密后适用本规定。作者签名：日期：具有不可用区间的平行机排序问题的近似算法摘要近几年来，排序问题由于其深刻的实际背景和广泛的应用前景而受到了极大关注。在经典的排序模型中，机器是一直可用的。然而，在实际生活中机器也需要维修，工人也需要休息，这就导致了机器在使用过程中不可能是一直可用的。所以很多人研究了机器带有不可用约束的排序问题。同时我们也考虑了工件带有运输时间的问题，这是因为在具有很多工件数的大型排序问题中，往往在工件加工完之后还需要在一定的时间内将其运送到指定的生产地方。这就使得我们不仅要单纯

3、考虑工件的完工时间也要把运输时间计划在内，使其更符合实际意义。本文主要讨论在机器具有不可用约束的情形下的平行机排序问题。文章主要分为四个部分，第一章中介绍了排序问题的背景，描述及表示方法，并对机器的不可用区间和工件的运输时间做了陈述。第二章中主要讨论了机器具有不可用区间的平行机排序问题。其中第一台机器上有一段不可用区间，第二台机器是可以连续使用的，工件在加工过程中是不允许中断的，目标函数是极小化时间表长。首先介绍了与之相关问题的发展情况，然后通过图例解释了这个问题的动态规化算法，并给出了该问题的全多项式近

4、似方案和时间复杂性。第三章中主要讨论了在机器具有不可用区间的同时，工件还带有运输时间的平行机排序问题，目标函数是极小化最大运输完工时间，同样给出了这一问题的全多项式近似方案和时间复杂性。最后针对以上这两个问题做出了总结。关键词：排序,不可用约束,平行机,时间表长,全多项式近似方案Approximationalgorithmforparallelmachinewithanon-availabilityconstraintAbstractInrecentyears,schedulingproblemhasat

5、tractedagreatattentionbecauseofitsdeepbackgroundintherealworldandbrightfutureinvariousapplicationenvironments.Theclassicalschedulingproblemusuallyassumesthatthemachinesareavailablesimultaneouslyatalltime.However,machinesalsoneedmaintenanceduringtheprocess

6、ingperiod,whichleadstothemachinesarenotavailableatalltime.Somanypeopleconsideredtheschedulingproblemswithafixednon-availabilityintervalonmachines.Atthesametime,wealsoconsidertheproblemwheneveryjobhasadeliverytime,thereasonfortheproblemisthatinthelargesetjo

7、bsofschedulingproblems,wehavetosendthejobstotheconsumersaftertheirprocessing.Sowenotonlyconsiderthejobs’processingtimebutalsoconsiderthedeliverytime,sothattheschedulingproblemshavemorepracticalsignificance.Thispaperfocusesonschedulingasetofjobsonparallelm

8、achineswhichhasanon-availabilityconstraint.Therearefourpartsinthispaper.Inchapter1,weintroducethedefinition,expressionandclassificationofthescheduling,aswellasthenon-availableconstraintonmachinesandthejob’sdeliveryt