资源描述：
《最小化最大流程的平行机分批在线排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、学校代码学号或申请号密级硕士学位论文最小化最大流程的平行机分批在线排序问题作者姓名：焦成文导师姓名：李文华教授学科门类：理学专业学位名称：运筹学与控制论培养院系：数学系完成时间：年月AthesissubmittedtoZhengzhouUniversityforthedegreeofMasterOnlineSchedulingonParallelBatchMachinestoMinimizetheMaximumFlow-timeByChengwenJiaoSupervisor:Prof.WenhuaLiOperationsResearchandCyberneticsDepartmen
2、tofMathematicsMay2012原创性声明本人郑重声明：所呈交的学位论文,是本人在导师的指导下,独立进行研究所取得的成果。除文中已经注明引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体,均已在文中以明确方式标明。本声明的法律责任由本人承担。学位论文作者：日期：年月学位论文授权使用声明本人在导师指导下完成的论文及相关的职务作品,知识产权归属郑州大学。根据郑州大学有关保留、使用学位论文的规定,同意学校保留或向国家有关部门或机构送交论文是复印件和电子版,允许论文被査阅和借阅；本人授权郑州大学可以将本学位论文的全部或部分编
3、入有关数据库进行检索,可以釆用影印、缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文或与该学位论文直接相关的学术论文或成果时,第一署名单位仍然为郑州大学。保密论文在解密后应遵守此规定。学位论文作者：〗日期：年月摘要平行机在线分批排序是现代排序领域中的一类重要问题平行机在线排序是指共有台机器,工件依次到达,工件到达之前关于该工件的所有信息都不知道或者只知道部分信息,我们要对已经到达的工件做出加工安排,即将工件安排在哪台机器上加工,将哪些工件形成一批来加工批处理是指处理机可以同时将若干个工件作为一批在某一台处理机上进行加工,每一批中的工件具有相同的开工时间和加工
4、时间批容量有两种不同的类型一种是每一批中只能同时加工有限个工件,一种是每一批中可以同时加工任意多个工件本文主要研究的是平行机在线分批排序,目标函数为极小化工件的流程的排序模型本论文的主要内容如下第一章简要介绍了排序问题的一些相关定义、记号及相关知识在第二章中,我们考虑的是工件按照加工长度不增的顺序到达,并且只有一台机器的情形对于批容量有限的情形,用等人(引入的的三参数法,该问题可以表述为：■■该排序问题实际上为一个半在线排序问题我们先给出了该问题的一个下界这里是方程的正根接着给出了一个竞争比为的在线算法,从而所给出的算法为最好可能的在线算法对于批容量无限的情形,用等人(弓入的三参数法
5、：该问题可以表述为：■■■该排序问题实际上为一个半在线排序问题我们先给出了该问题的一个下界其中接着给出了一个竞争比为的在线算法,从而所给出的算法为最好可能的在线算法在第三章中,我们考虑的是所有工件加工长度都相同的平行机分批排序情形,用等人(引入的三参数法,该问题可以表示为：我们给出了一个下界这里是方程的正根接着给出了一个竞争比为的在线算法,从而所给出的算法为最好可能的在线算法在第四章中,我们考虑所有工件加工长度都相同并且工件至多有两个到达时间的平行机分批排序情形,用等人(引入的三参数法：该问题可以表示为：―我们先给出了该问题的一个下界§接着给出了一个竞争比为的在线算法,从而所给出的算
6、法为最好可能的在线算法最后,我们总结全文并指出了下一步要研究的问题关键词：在线排序；分批；最大流程AbstractBatchschedulingisanimportantproblemofschedulingresearch.Therearemma?chinesintheparallelmachineonlinescheduling.Thejobscomeonebyone.beforethejobscomingweknownothingorlittleoftheinformationofthejobs.Weneedtoschedulethejobsthathavebeencome,t
7、hatisputtingajobonwhichmachineandwhichjobsshouldbescheduledasabatch.Abatchmachinecanschedulesomejobssimultaneouslyonsomemachineandthejobsthatareinasamebatchhavethesamestartingtimesandfinishingtimes.Therearetwodifferentkindsoftheca
