具有不同释放时间的单机重新排序问题的近似算法

发布时间：2017-09-22 01:11

  本文关键词：具有不同释放时间的单机重新排序问题的近似算法

  更多相关文章： 重新排序 释放时间 时间错位 加权时间总和 近似算法

【摘要】：近年来,重新排序问题研究开始引起广泛的关注.本文以工厂机器加工工件(工件与任务表示相同的概念)作为实际背景,主要考虑有一批工件已经按照某种规则进行了排序并使得目标函数达到了最优,其中有一些工件由于各种各样的原因要推迟到某个时间点后才可以开始加工,此时,决策者需要对原来的排序进行调整,即在原来最优排序的基础上,在工件的时间错位不至于太大的限制下进行重新排序,并使得原来的目标函数达到最优的单机问题.本文研究的问题的目标函数是经典的加权完工时间总和.对于这个问题Nicholas G.Hall不Chris N.Potts已经提供了一种复杂度是伪多项式时间的动态规划最优算法TWCOA,并给出了其时间复杂度的分析,随后给出了GAA近似算法,其最坏情况误差比为2.本文对该近似算法进行改善,得到了更好的SR近似算法并给出了其最坏情况误差比比GAA近似算法小的证明.同时对该问题进行了拓展,将条件中的重排工件共有的一个释放时间变成两个不同的释放时间,使问题变得更一般化,然后进行讨论从而得到该问题的一个近似算法SRT.
【关键词】：重新排序 释放时间 时间错位 加权时间总和 近似算法
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O223
【目录】：

• 中文摘要3-4
• 英文摘要4-6
• 第一章 引言6-8
• 1.1 研究背景6
• 1.2 研究现状6-7
• 1.3 研究内容及结构7-8
• 第二章 TWCOA算法8-13
• 2.1 基本概念及相关结论8-11
• 2.1.1 问题概述8-9
• 2.1.2 相关结论9-11
• 2.2 TWCOA算法11-12
• 2.3 GAA近似算法12-13
• 第三章 SR算法13-18
• 3.1 SR算法的思路13-14
• 3.2 SR算法14-16
• 3.2.1 SR算法及其算法复杂度14-15
• 3.2.2 SR算法的最坏情况误差比15-16
• 3.3 实例16-18
• 第四章 具有两个不同释放时间的单机重排问题18-27
• 4.1 问题概述及相关结论18-21
• 4.2 SRT算法及其算法复杂度21-25
• 4.3 实例25-27
• 第五章 总结和展望27-28
• 参考文献28-30
• 致谢30

【相似文献】

中国期刊全文数据库 前10条

1 魏麒;蒋义伟;;一类两阶段杂交流水作业的近似算法(英文)[J];软件学报;2012年05期

2 刘振宏;组合最优化问题的近似算法[J];数学的实践与认识;1983年03期

3 马绍汉;一类限制树问题的复杂性及其近似算法[J];山东大学学报(自然科学版);1984年01期

4 杨延龄,戚文发;关于最优备件问题的近似算法的研究[J];工程数学学报;1989年01期

5 杜林古;;带风向投递员问题的一个多项式1—近似算法[J];山东纺织工学院学报;1992年01期

6 苏纯洁;带服务器的三台平行机排序问题的复杂性和近似算法[J];应用数学学报;2003年03期

7 刘光聪;朱大铭;姜海涛;;有向基因组反转和转位排序最小权重问题的1.5k近似算法[J];小型微型计算机系统;2010年07期

8 何勇;带核集分划问题的一个线性(1/7)-近似算法[J];高校应用数学学报A辑(中文版);1997年04期

9 季敏,何勇;带核集分划问题的一个改进近似算法[J];系统工程理论与实践;2003年12期

10 何晓琼;陈冲;李荣珩;;工厂地址集中的k-种产品选址问题的近似算法[J];计算机工程与应用;2010年08期

中国重要会议论文全文数据库 前9条

1 刘声田;朱大铭;;基因序列翻转排序的一种近似算法[A];山东省计算机学会2005年信息技术与信息化研讨会论文集（一）[C];2005年

2 梅生伟;洪奕光;秦化淑;翁绍鹏;;非线性H_∞控制的粘性解及其近似算法[A];1996年中国控制会议论文集[C];1996年

3 田世俊;李建;朱洪;;多需求目标的UFL问题及其近似算法[A];2005年全国理论计算机科学学术年会论文集[C];2005年

4 梁国宏;郭云霞;郑明发;;最大化下模函数的近似算法及其性能保证[A];第十届中国不确定系统年会、第十四届中国青年信息与管理学者大会论文集[C];2012年

5 保利勇;赵东风;丁洪伟;;双服务器异步控制策略轮询系统性能的近似算法分析[A];2009年中国高校通信类院系学术研讨会论文集[C];2009年

6 任建峰;张玉忠;孙国;;一种新的柔性车间排序问题[A];中国企业运筹学学术交流大会论文集[C];2005年

7 李灏;张春路;丁国良;;对多层墙体反应系数的一种近似算法的讨论[A];上海市制冷学会一九九七年学术年会论文集[C];1997年

8 李灏;张春路;丁国良;;对多层墙体反应系数的一种近似算法的讨论[A];全国暖通空调制冷1998年学术年会论文集（2）[C];1998年

9 周露;吴瑶华;黄文虎;闻新;;一种推广卡尔曼滤波的近似算法[A];1995中国控制与决策学术年会论文集[C];1995年

中国重要报纸全文数据库 前1条

1 PALADIN;近似算法[N];电脑报;2003年

中国博士学位论文全文数据库 前5条

1 杨朝霞;超图嵌入圈问题的近似算法[D];山东大学;2010年

2 潘锐;设施选址与K-中间点问题的复杂性与近似算法[D];山东大学;2007年

3 陈仕平;若干组合优化问题的近似算法设计与分析[D];浙江大学;2002年

4 柳楠;基因组片段填充问题的算法研究[D];山东大学;2013年

5 姜海涛;基因组比较算法研究[D];山东大学;2011年

中国硕士学位论文全文数据库 前10条

1 陈崇琛;多色点集直线划分的复杂性及其近似算法[D];复旦大学;2014年

2 王敏;基于图特征的介度中心近似算法研究[D];曲阜师范大学;2015年

3 张亚平;最小赋权连通k-子图覆盖问题的近似算法[D];新疆大学;2015年

4 张永俊;广义非线性分式规划问题的近似算法[D];河南师范大学;2015年

5 朱婷婷;具有不同释放时间的单机重新排序问题的近似算法[D];兰州大学;2016年

6 王克红;均匀限制NP-完备间题及其近似算法设计[D];云南大学;2016年

7 李彦杰;连通控制吸收集的近似算法[D];新疆大学;2013年

8 张峰;漫射光化通量的二流四流混合近似算法求解[D];中国气象科学研究院;2010年

9 刘海;非光滑问题的三次近似算法[D];北京工业大学;2014年

10 张诸俊;异构车辆路径问题近似算法的研究[D];华东师范大学;2014年

，

本文编号：897916