考虑机器随机中断且具有时间相关恶化效应的平行机调度问题

发布时间：2017-09-09 15:46

  本文关键词：考虑机器随机中断且具有时间相关恶化效应的平行机调度问题

  更多相关文章： 调度 随机干扰 维护 恶化效应 伪多项式时间算法 完全多项式时间近似方案

【摘要】：在一些经典调度问题中,通常假设工件的加工时间为常数,并且在加工过程中机器可以持续加工工件。但在许多实际生产过程中,由于机器的老化或其他原因会导致机器的加工效率下降,从而使得工件所需的实际加工时间随其开始加工时间的推迟而增大,这种现象称为机器具有恶化效应。同时,由于一些内部或外部原因,会使机器在加工过程中发生中断,往往不能持续工作。因此,需要对机器进行维护以提高机器的加工效率或防止机器发生中断。本文主要研究考虑机器可随机中断且具有时间相关恶化效应的平行机调度问题。在该问题中,由于机器恶化效应的影响,工件的实际加工时间定义为其开始加工时间的非减函数。此外,由于一些内部或外部原因,部分机器会发生随机干扰,其中中断的开始时刻是已知的,但中断是否发生具有一定的随机性且中断时长服从一定的概率分布。机器中断发生后,有两类决策可以考虑。一类是在机器中断发生后立即对机器进行维护,维护后的机器将恢复初始状态。另一类是不进行维护。目标是确定一个最优调度以最小化工件完工时间和的数学期望。本文的主要研究内容和创新点如下：(1)对于工件不可中断的情形,证明了当机器数为输入变量时相应问题是强NP-难的,当机器数为固定量时则是NP-难的。在机器数固定的条件下,针对中断发生后是否对机器进行维护两种情形,分别设计了伪多项式时间动态规划算法,进而说明了相应问题是一般NP-难的,进一步证明了当中断仅发生在其中一台机器上时,相应问题存在完全多项式时间近似方案。(2)对于工件可中断的情形,证明了当机器数为输入变量时相应问题是强NP-难的,当机器数为固定量且中断发生在其中至少两台机器上时相应问题是NP-难的。在机器数固定的条件下,针对中断发生后是否对机器进行维护两种情形,分别设计了伪多项式时间动态规划算法,进而说明当中断发生在其中至少两台机器上时相应问题是一般NP-难的。然而,当机器数为固定量且中断仅发生在其中一台机器上,相应问题是否是NP-难的仍是未知的。
【关键词】：调度 随机干扰 维护 恶化效应 伪多项式时间算法 完全多项式时间近似方案
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O223
【目录】：

• 摘要6-7
• Abstract7-11
• 第一章 引言11-19
• 1.1 调度的基本概念与符号说明11-13
• 1.2 研究概况13-18
• 1.2.1 机器具有不可用时间区间的调度问题14-15
• 1.2.2 具有恶化效应的调度问题15-16
• 1.2.3 研究现状分析16-18
• 1.3 本文的结构安排18-19
• 第二章 问题与分析19-22
• 2.1 问题描述19-20
• 2.2 结构性质20-22
• 第三章 工件不可中断的模型22-40
• 3.1 伪多项式时间算法22-33
• 3.1.1 模型Pm,l|nr-a,M,DE,PDR|E(∑_(j=1)~nC_j)22-29
• 3.1.2 模型Pm,l|nr-a,M,DE,PDR|E(∑_(j=1)~nC_j)29-33
• 3.2 当l=1、s_0=0时的完全多项式时间近似方案(FPTAS)33-40
• 第四章 工件可中断的模型40-45
• 4.1 模型Pm,l|nr-a,M,DE,PDR|E(∑_(j=1)~nC_j)41-43
• 4.2 模型Pm,l|nr-a,M,DE,PDR|E(∑_(j=1)~nC_j)43-45
• 第五章 总结与展望45-48
• 5.1 总结45-46
• 5.2 展望46-48
• 参考文献48-51
• 致谢51-52
• 攻读学位期间发表的学术论文目录52

【相似文献】

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

1 郭艳东;黄敏;王庆;;锁定初始调度的紧急工作单机重调度问题[J];东北大学学报(自然科学版);2013年05期

2 席裕庚,王长军;控制、规划和调度问题中的博弈论应用[J];中国计量学院学报;2005年01期

3 胡扬;桂卫华;;人工代谢算法在多对象调度中的应用[J];系统工程学报;2011年01期

4 刘鹏;周晓晔;衣娜;;带有减少线性恶化效应的双代理调度问题[J];系统工程学报;2011年03期

5 董平;机器调度问题及求解方法[J];物流技术与应用;1997年01期

6 张仁忠;一类串行生产线的最优调度问题的注记[J];黄淮学刊(自然科学版);1998年S3期

7 刘红,张强,杜瑜;全国大学生数学建模竞赛中公交车调度问题的求解[J];成都航空职业技术学院学报;2002年02期

8 黎鹤;孙广中;许胤龙;;未知网络中可分负载的分布式调度[J];中国科学技术大学学报;2009年08期

9 王冰;动态单机调度的一种滚动时域策略及全局性能分析[J];系统工程理论与实践;2004年09期

10 左燕;薛安克;王建中;;单机调度问题对偶集结迭代算法[J];控制理论与应用;2010年12期

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

1 李建更;涂凍生;马海涛;;单机拖后时间总和问题交付期扰动时最优调度不变范围的一种求法[A];第十九届中国控制会议论文集（一）[C];2000年

2 刘海龙;黄小原;;总的未完工费用最小的多机调度问题[A];1995中国控制与决策学术年会论文集[C];1995年

3 沈吟东;曾西洋;;公共交通驾驶员调度的复杂性及解决方法[A];’2004计算机应用技术交流会议论文集[C];2004年

4 李兵;蒋慰孙;;Job shop问题的建模及调度[A];1996中国控制与决策学术年会论文集[C];1996年

5 王海星;申金升;;智能蚁群算法解决公交区域调度问题研究[A];2006年首届ICT大会信息、知识、智能及其转换理论第一次高峰论坛会议论文集[C];2006年

6 王成尧;汪定伟;;模糊加工时间的单机调度问题[A];1996中国控制与决策学术年会论文集[C];1996年

7 齐向彤;涂奉生;;双交付期E／T调度问题[A];1997年中国控制会议论文集[C];1997年

8 吴斌;方叶祥;崔志勇;;基于人工蜂群算法的越库调度问题研究[A];第25届中国控制与决策会议论文集[C];2013年

9 方涛;吴受章;;FMS的自适应调度:结构与算法研究[A];1992年中国控制与决策学术年会论文集[C];1992年

10 刘兴初;赵千川;郑大钟;;具有不同准备时间和交付期的单机E／T调度问题研究[A];1998年中国控制会议论文集[C];1998年

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

1 本报记者 贾科华;火电机组叫苦调度不合理[N];中国能源报;2012年

2 本报记者 高芳;牵住“牛鼻子” 巧解“推进难”[N];湖南经济报;2008年

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

1 郭鹏;具有分段恶化效应生产过程的智能优化调度研究[D];西南交通大学;2014年

2 元野;基于图着色模型的零担物流调度优化问题研究[D];哈尔滨工业大学;2015年

3 李雪松;模糊环境下若干单机批加工调度问题的模型及其算法研究[D];哈尔滨工业大学;2015年

4 汤雅连;关联物流运输调度问题研究[D];广东工业大学;2015年

5 周理;高效可重构阵列计算：体系结构，设计方法与程序映射技术研究[D];国防科学技术大学;2014年

6 冯大光;一类批处理机调度的理论和方法研究[D];东北大学;2011年

7 孟盈;钢铁企业并行批生产决策与调度问题研究[D];东北大学;2011年

8 杨磊;内容网络中内容调度技术研究[D];重庆大学;2015年

9 李亚志;流水制造单元调度智能优化方法[D];东南大学;2015年

10 丁宁;若干调度问题的算法研究[D];大连理工大学;2016年

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

1 张亮;云计算环境下的资源调度技术的研究[D];江南大学;2015年

2 冯卓鹏;重载运输卸车组织优化研究[D];西南交通大学;2015年

3 闫志超;基于人工蜂群算法的拖轮调度优化[D];大连海事大学;2015年

4 石雪飞;维护时长随机器负载线性递增的单机调度问题[D];东华理工大学;2014年

5 苏玮;含风电场电力系统的风险调度[D];东南大学;2015年

6 李晓浩;蚁群优化算法在平行机批调度问题中的应用与研究[D];安徽大学;2016年

7 陈琳;基于衰老机制的群智能算法及其在跨单元调度问题中的应用[D];北京理工大学;2016年

8 赵海丹;有模具限制的并行机台调度问题研究[D];吉林大学;2016年

9 王如雪;项目多目标模糊调度优化模型及算法研究[D];吉林大学;2016年

10 沈睿;基于实时需求的夜间柔性公交调度研究[D];西南交通大学;2016年

，

本文编号：821334