资源描述：
《工件可拒绝及加工时间可变的排序问题研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、分类号:O22学校单位代码:10446曲阜师范大学博士学位论文论文题目:工件可拒绝及加工时间可变的排序问题研究万方数据研究生姓名:学科、专业:研究方向:导师姓名、职称:论文完成时间:邹娟数学、应用数学组合最优化张玉忠教授2014年3月曲阜师范大学博士学位论文原创性声明本人郑重声明：所呈交的博士学位论文《工件可拒绝及加工时间可变的排序问题研究》,是本人在导师指导下,在曲阜师范大学攻读博士学位期间独立进行研究工作所取得的成果.论文中除注明部分外不包含他人已经发表或撰写的研究成果.对本文的研究工作做出重要贡献的个
2、人和集体,均已在文中以明确的方式注明.本声明的法律结果将完全由本人承担.作者签名：日期：曲阜师范大学博士学位论文使用授权书《工件可拒绝及加工时间可变的排序问题研究》系本人在曲阜师范大学攻读博士学位期间在导师指导下完成的博士学位论文.本论文的研究成果归曲阜师范大学所有,本论文的研究内容不得以其他单位的名义发表,本人完全了解曲阜师范大学关于保存、使用学位论文的规定,同意学校保留并向有关部门送交论文的复印件和电子版本,允许论文被查阅和借阅.本人授权曲阜师范大学,可以采用影印或其他复制手段保存论文,可以公开发表论文的
3、全部或部分内容.万方数据作者签名：导师签名：日日期：期：曲阜师范大学博士学位论文工件可拒绝及加工时间可变的排序问题研究摘要排序问题是组合优化的一个重要分支,它广泛地应用于工农业生产、运输业、管理科学和计算机科学等诸多领域.分批排序、工件加工时间可变、工件可拒绝以及工件可外包的排序都是新型的排序问题,因此吸引了国内外众多学者的关注.本文对这几类问题进行了研究,做了如下工作.第一章介绍了排序问题的相关基本知识,并简要概括了本论文的研究成果.第二章考虑了工件的加工时间是开工时间的线性增加函数的同类机排序问题.目标
4、函数分别是极小化总完工时间和极小化机器上的总负载.当退化率(恶化率)相同时,这两个问题是多项式时间可解的.当加工时间是其开工时间的一般线性增加函数时,对于极小化机器上的总负载问题,给出了一个全多项式时间近似方案.当加工时间是其开工时间的简单线性函数时,对于极小化所有工件被送到目的地的时间这一目标函数,也给出了一个全多项式时间近似方案.第三章研究的是工件可拒绝的继列分批排序问题.每个工件或者安排在单机上成批加工或者被拒绝,需要支付拒绝费用.考虑两种拒绝模型,第一种模型是极小化接受工件的排序目标值与拒绝工件的拒绝总费
5、用之和.其中,排序目标分别是最大完工时间,总完工时间,最大延迟以及加权总误工工件数.对于前两个问题,给出了两个多项式时间算法来求解.对于后两个问题,给出了有效的伪多项式时间算法.第二种模型是在拒绝费用有约束的条件下,极小化接受工件的最大完工时间,对于该问题,给出了一个全多项式时间近似方案.第四章考虑了工件具有就绪时间、加工时间可退化以及工件可拒绝的排序问题.机器环境分别是单机和平行机.工件的加工时间是其开工时间的简单线性函数.对于单机问题,目标函数是极小化接受工件的最大延迟与拒绝工件的拒绝总费用之和.证明了该问题
6、是强NP-困难的.当工件的就绪时间与交货期一致时,给出了一个全多项式时间近似方案.对于平行机问题,目标函数是极小化所有接受工件被送到目的地的时间与拒绝工件的拒绝总费用之和.当工件具有相同的就绪时间,给出了一个全多项式时间近似方案.特别地,当所有工件都被接受时,给出了一个启发式算法.第五章考虑了工件具有就绪时间、工件加工时间可退化以及工件可拒绝的无界平行批排序问题.工件或者被接受在批处理机上加工或者被拒绝支付一定的拒绝费用.工件的加工时间是其开工时间的简单线性函数.目标函数是极小化接受工件的最大完工时间与拒绝工件的
7、拒绝总费用之和.首先,证明了该问题在一般意义下i万方数据曲阜师范大学博士学位论文是NP-困难的.其次,给出了两个动态规划算法和一个全多项式时间近似方案.最后,给出了一种特殊情形的多项式时间算法.第六章考虑了工件可外包的继列批排序问题.每个工件或者在制造商处加工,或者外包加工.目标函数是极小化排序目标值与外包总费用的加权和.讨论了三种经典的排序目标函数.第一个是总完工时间,第二个是最大延迟,第三个是加权总误工工件数.对于每个问题,给出了有效的动态规划算法来求解.关键词:排序;同类机;线性恶化;全多项式时间近似方案;
8、继列分批;拒绝;动态规划;平行分批;外包.ii万方数据曲阜师范大学博士学位论文SchedulingproblemswithdeteriorationandrejectionABSTRACTSchedulingisanimportantbranchofcombinatorialoptimization.Theschedulingtheoryextensivelyhasbee
