带拒绝和释放时间的单机批调度问题

发布时间：2017-05-05 20:11

  本文关键词：带拒绝和释放时间的单机批调度问题，由笔耕文化传播整理发布。

【摘要】：随着科技的日益革新与制造业的发展,调度问题的重要性得到了加强。有许多相关的研究者对于调度问题进行了大量的研究。大部分的研究都是在工件必须被加工这一前提条件下进行的,但是有些情况下可以选择拒绝加工一些工件,本文就是在这一前提条件下进行研究的。调度问题的研究方向有很多。比如车间调度问题,单机调度问题,并行机调度问题。本文主要研究单机调度问题。研究的问题具体如下：给定n个工件,其中每个工件的属性包括：处理时间Pj；到达时间rj(在这个时刻之前,该工件不能被调度)；惩罚值ej(工件是可以被拒绝的,但是当拒绝工件时,我们必须付出一定的代价,即为ej)。在加工期间,机器是不能暂停的,只能当一批工件都被处理完时,才会停止。我们只考虑一个机器的情况,即单机调度。机器最多一次同时加工b个工件,这b个工件称为一批,批里的工件的开始时间与结束时间一样,批的处理时间即为批中工件处理时间最大的那个。我们的目标是求最小的被接收工件的完成时间之和加被拒绝的工件的惩罚值之和。工件的完成时间即为工件的开始被处理的时间或者说工件所在批的开始时间加上批的处理时间。我们对于目标函数设计了一个动态规划算法,但是这个动态规划并不能求得最优解,而是最优解的一个近似解。因为,在算法中,我们要对给定的一部分初始条件做出改变,比如工件的到达时间与工件的处理时间,将其规整为某个数的指数倍。无规律初始条件改变为有一定规律的初始条件,使得我们后续的分析变得相对简单一些。我们将工件分成了长短两类工件,并将它们分开处理。对于短工件我们仍然采用了动态规划的方式,而对于长工件,则采取了枚举的方式。最后,我们分析了时间复杂度并证明了结果是一个多项式时间的近似方案。
【关键词】：到达时间 惩罚值 动态规划 完成时间之和加惩罚值之和 批调度
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TB497
【目录】：

• 摘要8-9
• ABSTRACT9-10
• 第一章 绪论10-14
• 1.1 研究的背景与意义10-11
• 1.2 问题介绍11-12
• 1.3 论文所做的工作12-13
• 1.4 论文结构13-14
• 第二章 研究现状与研究方法14-23
• 2.1 三元组的介绍14-15
• 2.2 不含拒绝的调度问题的研究15-16
• 2.2.1 FBLPT规则15
• 2.2.2 对于包含到达时间的调度问题15-16
• 2.2.3 对于包含工件尺寸的调度问题16
• 2.3 包含拒绝的调度问题的研究16-17
• 2.3.1 对于最小化最大完成时间问题的研究16-17
• 2.3.2 关于完成时间之和问题的研究17
• 2.4 解决调度问题的常用的一些研究方法17-22
• 2.4.1 优化算法18
• 2.4.2 启发式算法18-22
• 2.5 本章小结22-23
• 第三章 多项式时间近似方案23-43
• 3.1 预备知识与相关引理23-28
• 3.1.1 预备知识23-24
• 3.1.2 相关引理24-28
• 3.2 多项式时间算法28-42
• 3.2.1 算法的动态规划公式28-30
• 3.2.2 将长短工件分开30-31
• 3.2.3 对于短工件的分批处理31-35
• 3.2.4 对于长工件的处理方法35-37
• 3.2.5 在多项式时间内计算t,t',U,V的选择37-40
• 3.2.6 在多项式时间内计算W_(i+1)(t,t',a-a',U-V)40-42
• 3.3 本章小结42-43
• 第四章 总结与展望43-45
• 参考文献45-48
• 致谢48-49
• 附件49

【相似文献】

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

1 刘琳;谷寒雨;席裕庚;;工件到达时间未知的动态车间滚动重调度[J];机械工程学报;2008年05期

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

3 姜洋;孙伟;丁秋雷;张旭;;考虑行为主体的单机调度干扰管理模型[J];机械工程学报;2013年14期

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

5 徐群岭;;基于免疫优化的公交驾驶员调度问题[J];计算机工程;2010年24期

6 喻道远;史登松;刘盛强;张三强;;带模糊排序的移动瓶颈法求解不确定调度问题[J];机械制造;2011年02期

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

8 刘晓东;陈英武;龙运军;贺仁杰;李菊芳;;同型机在线调度问题研究进展[J];计算机集成制造系统;2012年03期

9 姚君遗，杨善林，左春荣;基于实例FMS的AGV调度数学模型与算法[J];合肥工业大学学报(自然科学版);1995年01期

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

中国重要会议论文全文数据库 前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];上海交通大学;2007年

4 王磊;OKP企业分散式项目计划与调度优化方法研究[D];哈尔滨工业大学;2013年

5 李小林;平行机环境下批处理机调度问题研究[D];中国科学技术大学;2012年

6 金毅;模糊集合论在生产计划和调度中的应用研究[D];东南大学;1994年

7 李玉庆;动态不确定环境下航天器观测调度问题研究[D];哈尔滨工业大学;2008年

8 刘志雄;调度问题中的粒子群优化方法及其应用研究[D];武汉理工大学;2005年

9 汤健超;基于混合进化算法的若干调度问题研究[D];华南理工大学;2012年

10 江维;任务关键实时系统的可信感知调度研究[D];电子科技大学;2009年

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

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

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

3 崔雪源;基于遗传模拟退火算法的航班着陆调度问题[D];华中师范大学;2015年

4 王翠;基于超图模型和相继干扰消除的链路调度问题的研究[D];曲阜师范大学;2015年

5 张勇;带拒绝和释放时间的单机批调度问题[D];山东大学;2015年

6 吴凡;基于粒子群优化算法的风电-火电机组组合调度研究[D];华北电力大学;2015年

7 赵虎;MTO模式下的制造企业稳健型调度问题研究[D];重庆理工大学;2015年

8 鲍和映;航空公司不正常航班调度研究[D];南京航空航天大学;2013年

9 羊晓飞;基于场景和模糊描述的不确定Job Shop鲁棒调度[D];山东大学;2009年

10 王建波;基于综合利益最优的集成调度优化模型应用研究[D];大连交通大学;2010年

  本文关键词：带拒绝和释放时间的单机批调度问题，由笔耕文化传播整理发布。

，

本文编号：347014