一个特殊资源约束项目调度问题模型及其优化算法研究

发布时间：2017-08-30 14:24

  本文关键词：一个特殊资源约束项目调度问题模型及其优化算法研究

  更多相关文章： 资源约束项目调度问题 工位约束 串行进度生成机制 迭代局部搜索 最大最小蚂蚁系统

【摘要】：项目调度问题在企业生产中有着很重要的作用,与生产效率、成本密切相关。由于企业生产过程的多样性,经典资源约束项目调度问题(RCPSP)在实际生产中并不适用,所以,本文基于某企业的实际需求,在RCPSP基础上加入了工位、工件等新的概念,增加了工位对可更新资源、工件加工的约束,设定最小化总流程时间和最小化总偏差时间为求解目标,提出了一个新的项目调度问题模型——特殊资源约束项目调度问题(SRCPSP),用以解决实际调度问题。由于RCPSP是NP-hard问题,而SRCPSP约束更为复杂,所以,只能使用启发式算法进行求解。本文首先使用基于串行进度生成机制和优先规则的启发式算法对SRCPSP进行求解,提出了三大类规则分别用于选择工位、选择资源和选择工序,实验表明该算法可以快速生成一个初始可行解。然后,在此基础上,对初始解进行优化算法研究。首先,本文实验了使用迭代局部搜索的方法,研究了使用迭代局部搜索时解的表示方式、邻域结构、扰动策略等,然而研究表明,由于工件在工位间移动的巨大时间代价,迭代局部搜索并不适用于带工位约束的项目调度问题。之后,考虑到工序的调度主要是合适的工位和资源,所以本文实验了为工序随机选择工位和资源,结果表明,随机选择工位可以产生更好的结果。根据此结果,本文将蚁群优化算法——最大最小蚂蚁系统(MMAS)——应用到工位选择上,并用实验确定了蚁群算法中各项参数。实验表明,使用最大最小蚂蚁系统优化工位选择过程的方法是切实有效的,并且在生成相同数量解的情况下,相较于随机选择是稳定较优的。因此,对于本文提出的SRCPSP模型,设计的基于MMAS的优化算法具有很好的求解效果,将MMAS应用到工位选择上是合理有效的。
【关键词】：资源约束项目调度问题 工位约束 串行进度生成机制 迭代局部搜索 最大最小蚂蚁系统
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 致谢5-6
• 摘要6-7
• ABSTRACT7-11
• 1 引言11-19
• 1.1 研究背景及意义11-15
• 1.1.1 基本概念及约束11-13
• 1.1.2 RCPSP模型13
• 1.1.3 求解算法13-15
• 1.1.4 RCPSP局限性及本文研究意义15
• 1.2 国内外研究现状15-18
• 1.2.1 RCPSP模型扩展研究现状15-17
• 1.2.2 算法研究现状17-18
• 1.3 论文主要内容和组织结构18
• 1.4 本章小结18-19
• 2 特殊资源约束项目调度问题模型19-28
• 2.1 环境数据19-21
• 2.1.1 工件20
• 2.1.2 工位20
• 2.1.3 资源20-21
• 2.1.4 工序21
• 2.2 约束关系21-24
• 2.2.1 资源约束22-23
• 2.2.2 工序约束23-24
• 2.3 问题目标24
• 2.4 模型举例24-27
• 2.5 本章小结27-28
• 3 基于优先规则的SSGS启发式算法28-36
• 3.1 基本概念及定义28-29
• 3.2 算法总体流程29-30
• 3.3 优先规则30-33
• 3.3.1 工位选择规则30-31
• 3.3.2 资源选择规则31
• 3.3.3 工序选择规则31-32
• 3.3.4 解锁规则32-33
• 3.4 输入及输出数据格式33
• 3.4.1 输入数据33
• 3.4.2 输出数据33
• 3.5 本章小结33-36
• 4 基于迭代局部搜索的优化算法36-45
• 4.1 迭代局部搜索算法36-37
• 4.2 SRCPSP问题的迭代局部搜索优化算法设计37-42
• 4.2.1 解的表示37-38
• 4.2.2 邻域结构38-39
• 4.2.3 扰动策略39-40
• 4.2.4 算法总流程设计40-42
• 4.3 实验与结果分析42-44
• 4.4 本章小结44-45
• 5 基于蚁群算法的优化算法45-61
• 5.1 随机抽样算法45-49
• 5.1.1 工位随机选择算法47
• 5.1.2 资源随机选择算法47
• 5.1.3 实验验证及分析47-49
• 5.2 蚁群算法49-56
• 5.2.1 蚁群优化算法49-50
• 5.2.2 基于MMAS的优化算法设计与实现50-52
• 5.2.3 基于MMAS的优化算法参数选择52-56
• 5.3 实验结果与分析56-60
• 5.3.1 测试用例描述56-57
• 5.3.2 性能和可行性测试57-59
• 5.3.3 MMAS优化算法与随机算法对比59-60
• 5.4 本章小结60-61
• 6 总结与展望61-63
• 6.1 本文总结61-62
• 6.2 展望及今后的工作62-63
• 参考文献63-67
• 作者简历及攻读硕士学位期间取得的研究成果67-69
• 学位论文数据集69

【相似文献】

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

1 宋红星;曹文彬;;基于双种群蚁群算法的多目标资源受限项目调度问题研究[J];信息系统工程;2010年04期

2 程序;吴澄;;一种复杂项目调度问题的混合智能算法[J];计算机集成制造系统;2006年04期

3 徐进;费少梅;张树有;施岳定;;自适应粒子群求解资源动态分配项目调度问题[J];计算机集成制造系统;2011年08期

4 雒兴刚;汪定伟;唐加福;;任务可拆分项目调度问题[J];东北大学学报;2006年09期

5 宗砚;刘琼;张超勇;朱海平;;考虑资源传递时间的多项目调度问题[J];计算机集成制造系统;2011年09期

6 孙晓雅;林焰;;任务可定点拆分的资源受限项目调度问题研究[J];微电子学与计算机;2012年07期

7 张维存;康凯;;蚁群-粒子群算法求解多模式资源受限项目调度问题[J];计算机工程与应用;2007年34期

8 刘敏;代成琴;王宇航;;资源受限的项目调度问题的求解算法[J];自动化技术与应用;2008年06期

9 卢睿;李林瑛;;一种求解反应式项目调度问题的启发式方法[J];系统仿真学报;2011年02期

10 孙晓雅;林焰;;人工蜂群算法求解任务可拆分项目调度问题[J];微电子学与计算机;2011年11期

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

1 丁雪枫;尤建新;;多模式资源受限项目调度问题的混合优化算法研究[A];第十四届中国管理科学学术年会论文集(上册)[C];2012年

2 刘艳秋;张颖;汪定伟;王福利;;基于GA的RCPSP可靠性优化方法研究[A];2001年中国智能自动化会议论文集（下册）[C];2001年

3 周楷;何正文;;周期性支付的多模式Max-npv项目调度问题研究[A];中国企业运筹学学术交流大会论文集[C];2008年

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

1 王宏;求解资源受限项目调度问题算法的研究[D];天津大学;2005年

2 邓林义;资源受限的项目调度问题及其应用研究[D];大连理工大学;2008年

3 陈卫明;动态环境下产品开发项目调度问题及其求解研究[D];华中科技大学;2011年

4 吴兵;柔性资源受限的多模式项目调度问题研究[D];武汉理工大学;2008年

5 彭武良;面向产品开发的项目调度问题及项目管理系统研究[D];东北大学;2008年

6 李诗娴;基于净现值的资源受限型项目调度问题研究[D];天津大学;2012年

7 贾艳;资源受限项目调度问题的仿真优化方法及其应用研究[D];华中科技大学;2012年

8 应瑛;不确定资源约束下项目调度问题研究[D];浙江大学;2010年

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

1 李远见;几种改进的智能算法及其应用[D];安徽师范大学;2015年

2 段向阳;基于遗传算法的资源约束项目调度问题优化及应用研究[D];湖南工业大学;2015年

3 栗明威;一个特殊资源约束项目调度问题模型及其优化算法研究[D];北京交通大学;2016年

4 张冠群;基于蚁群算法的多模式资源受限项目调度问题研究[D];湖南大学;2009年

5 傅奥;多目标资源受限项目调度问题蚁群算法研究[D];浙江大学;2008年

6 蒲娟;多目标模糊资源受限项目调度问题研究[D];郑州大学;2012年

7 薄银利;基于模块化外包的项目调度问题研究[D];兰州大学;2011年

8 刘志霞;资源受限项目调度问题及其任务扰动的干扰管理研究[D];沈阳工业大学;2011年

9 陈俊波;考虑施工设备租赁的项目调度问题研究[D];华中科技大学;2009年

10 刘雅婷;人力资源受限项目调度问题研究[D];华中科技大学;2007年

，

本文编号：759811