两种有维护要求的单机和平行机调度问题研究

发布时间：2017-08-19 22:25

  本文关键词：两种有维护要求的单机和平行机调度问题研究

  更多相关文章： 维护时长 启发式算法 最坏情况界 数学规划模型 数值实验

【摘要】：调度问题一直以来是组合优化问题领域里最具有前景的方向之一,在过去的几十年里带有维护的调度问题更是吸引了大量研究者的目光。在这篇论文里,我们主要研究了两种带有维护的调度问题。第一个问题是一个维护时长随负载量可变的单机调度问题,即机器的维护时长是由一个随维护之前的负载量单调不减的函数f(x)所决定的,维护的开始时刻在时间窗[u,v]内,这里的0?u?v。本文所研究问题的目标是在机器上加工完所有工件并决定维护的开始时刻使得最大延迟maxL最小化。本文证明了此调度问题是NP-难的,基于经典的EDD算法提出了近似算法EDDMW并分析了它的最坏情况界。第二个问题是一个带有工具更换和固定周期维护的混合环境下的平行机最小化时间表长调度问题,其中需要工具更换的机器有1m台,需要固定周期维护的机器有1m?m台。工件均不可中断。为了解决这个调度问题,本文给出了该问题的一个数学规划模型和两个分别基于经典的LPT算法和LS算法的启发式算法LPTP和LSP。此数学规划模型的建立背后所隐含的思想是通过将多台平行机改变成一台机器。大量数值实验显示这个模型求解工件数在10以内的实例的求解时间是合理的。同时,为了方便分析这些算法的性能,本文因此还给出了最优时间表长的一个下界。本文通过设计一系列计算机数值实验,发现所给出的启发式算法能够在1s内求解具有2000个工件的实例且平均误差不超过10%,由此证明了本文设计的启发式算法十分适合求解大规模本文所研究的实例。
【关键词】：维护时长 启发式算法 最坏情况界 数学规划模型 数值实验
【学位授予单位】：东华理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O221
【目录】：

• 摘要4-5
• ABSTRACT5-8
• 第1章 引言8-14
• 1.1 调度的发展历史和任务8-9
• 1.2 调度问题的基本概念及符号说明9-10
• 1.3 国内外带有维护的调度问题的研究现状10-12
• 1.4 本文的结构安排12-14
• 第2章 维护时长随负载量可变的单机调度问题14-22
• 2.1 问题引出14
• 2.2 计算复杂性14-15
• 2.3 近似算法15
• 2.4 算法EDDMW最坏情况界分析15-21
• 2.5 小结21-22
• 第3章 带有工具更换和固定周期维护的平行机调度问题22-36
• 3.1 问题引入22-23
• 3.2 数学规划模型23-26
• 3.2.1 调度问题P_mM_(1-m_1)TC,M((m_1+1)-m)PM||C(max)?特殊情况下的数学规划模型24-25
• 3.2.2 调度问题P_mM_(1-m_1)TC,M((m_1+1)-m)PM||C(max)?的数学规划模型25-26
• 3.3 下界26-27
• 3.4 启发式算法27-28
• 3.5 数学实验下的平均情况分析28-35
• 3.5.1 算法LPTP和算法LSP相对下界的平均误差与n的关系29-30
• 3.5.2 算法LPTP和算法LSP相对下界的平均误差与maxp的关系30-32
• 3.5.3 算法LPTP和算法LSP相对下界的最大误差与n的关系32-33
• 3.5.4 算法LPTP和算法LSP相对下界的最大误差与maxp的关系33-35
• 3.6 小结35-36
• 第4章 总结与展望36-38
• 4.1 总结36
• 4.2 问题与展望36-38
• 致谢38-40
• 参考文献40-42
• 附录A 程序42-51
• 附件B参加的项目和发表的论文51

【共引文献】

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

1 齐学梅;;无等待流水调度问题迭代启发式算法[J];安徽师范大学学报(自然科学版);2009年01期

2 卓奕君;成晔;;面向大型产品装配的两维势能调度算法研究[J];北京信息科技大学学报(自然科学版);2009年04期

3 崔建双,李铁克,张文新;混合流水车间调度模型及其遗传算法[J];北京科技大学学报;2005年05期

4 李裕梅;谷云东;李洪兴;;调度问题Pm|p_j=1,intree|∑C_j的两个启发式算法[J];北京师范大学学报(自然科学版);2006年02期

5 袁芬;谷云东;尘非;;关于模糊工期平行机调度问题的若干结果[J];北京师范大学学报(自然科学版);2006年03期

6 孙秀平;谷云东;李洪兴;;任务无准备时间最小化加权最大延误单机调度问题的若干结果[J];北京师范大学学报(自然科学版);2006年05期

7 程贞敏;李洪兴;;允许中断的同速机调度问题的一个最优算法[J];北京师范大学学报(自然科学版);2008年05期

8 程贞敏;李洪兴;谷敏强;;最小化时间表长的平行机调度近似算法研究[J];北京师范大学学报(自然科学版);2012年01期

9 李晓峰;赵海;杜洪军;刘小勇;;柔性流水作业排序问题的贪心算法求解[J];吉林大学学报(信息科学版);2009年06期

10 贾春玉;一类3×n流水型排序问题新近似最优解法的探讨[J];长春大学学报;2004年06期

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

1 闻振卫;;一类平行机上的任务指派问题及其动态规划算法[A];中国运筹学会第九届学术交流会论文集[C];2008年

2 刘广军;李瑞芹;;2×n排序模型在装备战场抢修决策中的应用[A];系统仿真技术及其应用（第16卷）[C];2015年

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

1 马英;考虑维护时间的机器调度问题研究[D];合肥工业大学;2010年

2 钟雪灵;带强制工期非正则目标函数的排序问题研究[D];暨南大学;2010年

3 柳春锋;工程项目中技能型员工调度问题研究[D];合肥工业大学;2011年

4 许瑞;基于蚁群优化算法的批调度问题研究[D];中国科学技术大学;2011年

5 王磊;面向订单生产的供应链排序问题研究[D];暨南大学;2011年

6 丁国生;多代理竞争排序问题的研究[D];上海大学;2009年

7 白芳;民航发动机机群调度优化与视情维修决策方法研究[D];南京航空航天大学;2009年

8 杨名;若干流水作业排序问题的算法研究[D];华东理工大学;2011年

9 宫华;钢铁企业一类考虑恶化和运输的新型生产调度问题的理论研究[D];东北大学;2009年

10 李士生;工件具有不相容性质的机器排序问题[D];郑州大学;2012年

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

1 张玮虹;生产管理中的若干排序问题[D];浙江理工大学;2010年

2 王悦;存在批处理设备的复杂产品调度研究[D];哈尔滨理工大学;2010年

3 苏胜龙;带一个服务器的两台平行机半在线排序问题[D];华东理工大学;2011年

4 牟启燕;带一个服务器的两台机器自由作业排序问题的近似算法[D];华东理工大学;2011年

5 史媛媛;两类双目标排序问题研究[D];武汉科技大学;2010年

6 何少龙;具有安装时间和变量加工时间的单机排序问题[D];沈阳师范大学;2011年

7 刘洋;具有学习效应和退化效应的单机排序问题[D];沈阳师范大学;2011年

8 曹文琴;带有运输时间的在线排序问题[D];兰州大学;2011年

9 冯娜;带有不可相容工件组的在线排序问题[D];兰州大学;2011年

10 王洁明;有关代理竞争排序问题的研究[D];华东理工大学;2011年

，

本文编号：703306