基于新型学习效应的调度模型及其优化算法研究

发布时间：2017-04-26 20:00

  本文关键词：基于新型学习效应的调度模型及其优化算法研究，，由笔耕文化传播整理发布。

【摘要】：调度问题是一类重要的离散优化问题,它是利用一些处理机、机器或资源,最优地完成一批给定的任务或工件。它在大多数的制造和生产系统以及大多数的信息处理环境中扮演着重要的角色。它同样存在于运输和配送设施以及其他类型的服务业中。然而经典调度问题往往在理论上假设任务或工件的加工时间是固定不变的,相应的现实情况是,生产、运输或配送等过程中,操作人员不同于机器设备、组织流程等,它是一个具有学习能力的个体,即工件处理时间会因学习效应而缩短(在原本操作人员所占的处理时间上相应地缩短)。另一方面,学习能力的提升不仅仅来源于员工自身,更来源于企业的外部刺激,即鼓励员工提高其自身学习能力,采取对其进行培训、资助其再学习等投资性管理手段,从而进一步提高其学习能力的同时,最大化企业的整体利益。 本文针对上述两方面现实生产过程中的学习特征,相应地选取了两类新型学习效应并分别与经典调度目标相结合进行调度新模型研究。相较于目前调度领域中被广泛研究的经典学习效应,这两类新型学习效应更加一般化且更加具有现实意义,但是目前鲜少被研究,因此,本文的研究工作主要围绕这两类新型学习效应展开,第一类为DeJong学习效应,在此基础上,我们分别研究了在单台机和多台机环境下的两个经典调度目标,即极小化制造期和完成时间和。我们证明了单台机下的这两个目标和多台机下的极小化完成时间和目标都是多项式可解的,而多台机下的极小化制造期被证明是一个一般NP-难问题。对这个NP-难问题,我们对其设计了一个FPTAS,即多项式时间内的近似方案。第二类学习效应为同时考虑自发和引导的学习效应,在此基础上,我们同样考虑了两种加工环境即单台机和多台机下的不同调度目标。在单台机下,我们研究了5个经典调度目标,分别为极小化制造期、完成时间和、完成时间差的绝对值之和、加权完成时间和,以及最大延迟；在多台机下,我们研究了极小化完成时间和这个目标。通过分析,我们证明了上述6种情况都是多项式时间内可解或者在一定条件下是多项式可解的,另外,我们对每一种情况都给出了相应的多项式求解算法,并通过算例对算法做了进一步说明。
【关键词】：生产调度 DeJong学习效应 FPTAS 同时考虑自发和引导的学习效应 投资 最优算法
【学位授予单位】：浙江工商大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：C931.1
【目录】：

• 摘要2-4
• ABSTRACT4-9
• 第1章 绪论9-19
• 1.1 研究背景及意义9-11
• 1.2 研究现状11-17
• 1.3 研究内容及框架17-19
• 第2章 基本理论介绍19-26
• 2.1 组合优化问题19-21
• 2.1.1 概述19
• 2.1.2 计算复杂性理论19-20
• 2.1.3 算法及算法应用20-21
• 2.2 调度问题21-26
• 2.2.1 概述21-23
• 2.2.2 调度问题建模23
• 2.2.3 调度问题求解23-26
• 第3章 基于DeJong学习效应的调度问题26-37
• 3.1 问题描述26
• 3.2 单台机环境下的问题研究26-28
• 3.2.1 极小化制造期27
• 3.2.2 极小化完成时间和27-28
• 3.3 多台机环境下的问题研究28-35
• 3.3.1 极小化制造期28-34
• 3.3.2 极小化完成时间和34-35
• 3.4 本章总结35-37
• 第4章 基于同时考虑自发和引导学习效应的调度问题37-57
• 4.1 问题描述37-38
• 4.2 问题研究38-51
• 4.2.1 单台机下极小化制造期38-39
• 4.2.2 单台机下极小化完成时间和39-40
• 4.2.3 单台机下极小化完成时间差的绝对值之和40-45
• 4.2.4 多台机下极小化完成时间和45-46
• 4.2.5 单台机下极小化加权完成时间和46-48
• 4.2.6 单台机下极小化最大延迟48-51
• 4.3 算例分析51-55
• 4.4 本章总结55-57
• 第5章 总结与展望57-60
• 5.1 研究工作总结57-58
• 5.2 研究工作展望58-60
• 参考文献60-64
• 致谢64-65
• 附录1 攻读硕士学位期间完成的论文65-66
• 附录2 攻读硕士学位期间参加的项目66-67
• 附录367-69

【共引文献】

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

1 王吉波;马力;王利岩;王丹;殷那;;具有学习效应的两个单机排序问题(英文)[J];大连理工大学学报;2008年06期

2 蒋志高;董明;;考虑维护且加工时间可变的单机调度问题研究[J];工业工程与管理;2011年03期

3 张新功;;时间相关的单机排序的最坏竞争比分析[J];重庆师范大学学报(自然科学版);2013年05期

4 王吉波;刘璐;;带准备时间的任务单机学习效应排序问题[J];大连理工大学学报;2013年06期

5 陈东;赵传立;;带有交货期窗口和工件可拒绝的单机排序问题[J];重庆师范大学学报(自然科学版);2013年06期

6 徐海燕;李小平;;基于学习和恶化效应模型的单机调度[J];东南大学学报(自然科学版);2013年06期

7 赵升华;罗成新;;带有学习及退化效应和资源分配的交货期指派的单机排序问题[J];重庆师范大学学报(自然科学版);2014年01期

8 于秀丽;张毕西;李逸帆;李弘;;考虑员工学习效应的MOS指派优化研究[J];工业工程;2014年01期

9 张新功;王慧;柏仕坤;;重加工具有退化与学习现象的单机批排序问题[J];重庆师范大学学报(自然科学版);2014年05期

10 程硕;张毕西;张明珠;;考虑组织学习率-倦怠的SMPEs小组作业模式生产加工周期优化研究[J];工业工程;2014年05期

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

1 ;Economic dispatching problem with Group and Resource Considerations[A];第24届中国控制与决策会议论文集[C];2012年

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

1 苗翠霞;分批排序及资源约束排序中若干问题[D];曲阜师范大学;2011年

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

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

4 王吉波;工件加工时间可变的现代排序问题[D];大连理工大学;2005年

5 季敏;当代工业中的若干排序问题研究[D];浙江大学;2006年

6 程明宝;工件加工时间非恒定的排序模型研究[D];上海大学;2006年

7 黄敏镁;具有柔性资源约束的优化调度问题研究[D];武汉理工大学;2007年

8 蒋淑s

本文编号：329101