带拒绝和释放时间的单机批调度问题-计算机科学与技术专业毕业论文.pdf

《带拒绝和释放时间的单机批调度问题-计算机科学与技术专业毕业论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分类号：TP393密级：单位代码:10422学号：201213221硕士学位论文ThesisforMasterDegree论文题目：带拒绝和释放时间的单机批调度问题SINGLEMACHINEBATCHINGPROBLEMWITHPENTATIESANDRELEASETIME作者姓名张勇培养单位计算机科学与技术学院专业名称计算机科学与技术指导教师冯好娣教授合作导师2015年6月30日Y279345E一———原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中己经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究

2、作岀重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名：口期：20以6、咒关于学位论文使用授权的声明本人同意学校保留或向国家有关部门或机构送交论文的印刷件和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以釆用影印、缩印或其他复制手段保存论文和汇编本学位论文。（保密论文在解密后应遵守此规定）论文作者签名：乜逸_导师签名：磁紘—日期：2仍・心摘要ABSTRACTII第一章绪论-“・・・11」研究的背景与意义11.2问题介绍21.3论文所做的工作1.4论文结构第二章研究现状与研究方法2」三元组的介绍2

3、.2不含拒绝的调度问题的研究2.2.1FBLPT规则2.2.2对于包含到达时间的调度问题6223对于包含工件尺寸的调度问题72.3包含拒绝的调度问题的研究72.3.1对于最小化最大完成时间问题的研究72.3.2关于完成时间之和问题的研究82.5解决调度问题的常用的一些研究方法82.5.1优化算法92.5.2启发式算法92.6本章小结13第—章项式时间方・・••••♦•••・••••♦・・・》•♦・・・•・・・・・♦・・・・・・•・・・•・・・•••♦・・•••・・・・・•・・•・•《・・・•・・•・•••・・》•«143」预备知识与相关引理143.1」预备知识143.1.2相关引理153.

4、2.1算法的动态规划公式213.2多项式时间算法193.2.2将长短工件分开3.2.3对于短工件的分批处理223.2.4对于长工件的处理方法263.2.5在多项式时间内计算f,U、V的选择283.2.6在多项式时间内计算313.3本章小结33第皿戴灯结39TABLEOFCONTENTSAbstractinChinese1AbstractinEnglishIIChapter1Introduction1[1]Backgroundandsignificance1[1]Introductionofwork2[1]Mainwork3[1]Organization4Chapter2Researchst

5、atusandmethods5[27]IntroductionofThreetuple5[28]Schedulingwithoutrejection6FBLPTrule6Jobshavereleasetime6223Jobshavesize62.3Schedulingwithoutrejection73.2.2Minimumthecompletiontime72.3.2Minimumthetotalcompletiontime82.4Researchmethods82.4.1Optimizationalgorithm82.4.2Theheuristicalgorithm92.5Summy1

6、3Chapter3Thepolynomialapproximatealgorithm143」Preliminariesandlemmas143」.1Preliminaries14Lemmas153.2Thepolynomialapproximatealgorithm19321TheFormulaofDynamicprogramming19Splittheshortandlongjobs21•••UlProcessingshortjobs22Processinglongjobs263.2.5selectingt、U7inpolynomialtime283.2.6ComputingWi+i(t

7、,t',a-aU-V)313.3Summary33Cbapter4SummaryandProspect34References36Acknowledgement39摘要随着科技的日益革新与制造业的发展，调度问题的重要性得到了加强。有许多相关的研究者对于调度问题进行了大量的研究。大部分的研究都是在工件必须被加工这一前提条件下进行的，但是有些情况下可以选择拒绝加工一些工件，本文就是在这一前提条件下进行研究的。调度问题的研究