若干调度问题的算法研究
本文关键词：若干调度问题的算法研究 出处：《大连理工大学》2016年博士论文 论文类型：学位论文
【摘要】：调度问题是组合最优化领域和理论计算机科学领域中的一个重要分支,主要研究将稀缺资源分配给在一定时间内不同任务的问题,分配过程也可以理解为一个决策过程。做决策目的是优化一个或者多个目标,有单机调度,也有多机调度。从输入信息的实时性来看,调度(排序)问题可以被分为离线、在线和半在线三类；从输出结果的精确角度来看,调度问题的算法可被分为精确算法,近似算法(包含启发式算法)。调度问题在实际生活中一直都有广泛应用,比如计算机领域的节能调度,负载平衡调度,作业调度,医院中护士排班调度,运输中的动态车辆调度,生产线上的流水调度,飞机的航班调度,钢铁生产过程中的批作业调度和流水调度等等,因此调度问题一直被人们所广泛关注,并且是很多学者的研究课题。本文分别研究了带缓冲在线平行机调度、单机在线调度、带运输时间的流水调度和离线平行机调度等问题。(1)带缓冲在线平行机调度：文中给出了三个在线算法,并给出算法的竞争比分析,改进了已有的研究成果。文中提出了一个在线算法并证明了在同型机的数量m51,缓冲区大小为[1.5m]的情况,该算法竞争比为1.5；此外还提出在同型机数量为3的情况只需要6个缓冲区的最优的在线算法,改进了之前需要9个缓冲区的最优在线算法；文中还证明了在同类机的数量和缓冲区的均为m时,将竞争比从2+ε提升到2-1/m+ε,其中m是常数即机器的数量,ε0且足够小(2)单机在线调度：文中研究了单机调度下带有截至期限的抢占-重启模型,在已知的WAL算法中基础上提出了一个传统启发式算法D-WAL算法,其思想就是同时关注任务和作业的收益大小,分析实验结果显示D-WAL算法在性能上比只关注收益大小的WAL算法要好。(3)带运输时间流水调度：文中考虑了一种特殊情况即所有的工件在机器B上加工时间都相同的时候,针对该种特殊情况可以发现：存在一个最优调度使得每个工件在机器A上的加工时间是非递减的,而且工件执行顺序在机器A上的顺序和在机器B和运输机V是一样的。利用这个性质,文中给出了多项式时间的最优调度算法以及相应的证明。(4)离线平行机调度：本文基于经典的粒子群算法,结合Levy飞行方法优化粒子群算法,提出了LPSO算法。分析实验结果发现Levy飞行方法可以使PSO算法本身容易陷入早熟的劣势得到很显著的缓解,并且同时充分发挥了PSO算法的简便快捷特性。
[Abstract]:......
【学位授予单位】：大连理工大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP301.6
【相似文献】
相关期刊论文 前10条
1 刘文涛,张群,孙肃清;关于炼钢厂重调度问题的研究[J];冶金自动化;2004年06期
2 张居阳 ,礼欣 ,孙吉贵;基于约束的调度研究和实现[J];计算机工程与应用;2004年33期
3 刘琳;谷寒雨;席裕庚;;工件到达时间未知的动态车间滚动重调度[J];机械工程学报;2008年05期
4 黄峰;丁亚武;;人机协同模式下的手工调度技术研究[J];黑龙江科技信息;2011年35期
5 郭艳东;黄敏;王庆;;锁定初始调度的紧急工作单机重调度问题[J];东北大学学报(自然科学版);2013年05期
6 姜洋;孙伟;丁秋雷;张旭;;考虑行为主体的单机调度干扰管理模型[J];机械工程学报;2013年14期
7 李向军,王书振;网络化集成制造模式下调度问题的混合遗传算法[J];西安联合大学学报;2002年04期
8 王中杰,吴启迪,有杰;基于多目标的半导体生产线满意调度[J];控制与决策;2002年06期
9 李云峰;凌晓冬;武小悦;;调度问题中的冲突研究[J];兵工自动化;2007年06期
10 徐群岭;;基于免疫优化的公交驾驶员调度问题[J];计算机工程;2010年24期
相关会议论文 前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];曲阜师范大学;2015年
5 张勇;带拒绝和释放时间的单机批调度问题[D];山东大学;2015年
6 吴凡;基于粒子群优化算法的风电-火电机组组合调度研究[D];华北电力大学;2015年
7 赵虎;MTO模式下的制造企业稳健型调度问题研究[D];重庆理工大学;2015年
8 吉佳红;基于细菌觅食算法的改进及应用研究[D];江苏科技大学;2015年
9 周超;柔性作业车间批量问题研究[D];宁波大学;2014年
10 赵兴野;工序顺序柔性作业车间描述与调度研究[D];大连理工大学;2015年
，本文编号：1352370
本文链接：https://www.wllwen.com/shoufeilunwen/xxkjbs/1352370.html
