带装载和卸载的平行机调度问题

发布时间：2017-08-29 18:08

  本文关键词：带装载和卸载的平行机调度问题

  更多相关文章： 调度 算法 最坏情况界 最大完工时间 配送中心 包裹运输

【摘要】：本文主要研究带服务器的平行机调度问题，服务器负责装载和卸载的操作。对于带服务器的平行机调度问题一般研究的是服务器负责装载的操作，但随着自动化的全面发展，既然在工件加工之前有安装，相应的再将加工完成之后的工件从机器上卸载下来，这在实际的生产操作中也是一个很值得研究的问题。因此，本文的服务器既要负责装载的操作又要负责卸载的操作，即工件在加工之前先由服务器负责把工件装载到机器上，工件加工完成之后再由服务器把它从机器上卸载下来。由于增加了一个操作，在算法的设计上也增加了一定的难度，因此，本文首先研究带单个服务器的可中断的平行机调度问题；其次，再扩展到带两个服务器的不可中断的平行机调度问题；最后应用经典的LPT算法解决有关配送中心包裹的调度问题。通过比较随机算法R的结果、LPT算法的结果以及最优解值，得出LPT算法可以有效地解决包裹的调度问题。 本论文分为五章： 在第一章中，主要给出调度问题的相关知识以及有关调度问题算法的设计与分析，通过使用最坏情况界（或竞争比）来衡量一个算法的有效性。并介绍本文所要研究的带服务器的调度问题的相关背景、研究现状以及所要研究的问题。 在第二章中，研究只带一个服务器的可中断的平行机调度问题，每个工件在加工之前需要服务器先把它装载到两台机器中的一台上去，在加工完成之后再由该服务器把它从机器上卸载下来。该问题装卸载的时间都是单位时间，目标是极小化最大完工时间。本文设计了一个算法OPA来解决该问题，并且证明该算法是最优算法。 在第三章中，研究带两个服务器的平行机调度问题。这里的两个服务器，一个负责在工件加工开始之前把工件装载到机器上，另外一个负责在工件加工完成之后把工件从机器上卸载下来。这一章研究的是不可中断的情况，装卸载时间都是单位时间，目标是极小化最大完工时间。本文使用LS算法和LPT算法求解该问题，并证明它们的最坏情况界分别为8/5和6/5。 在第四章中，研究配送中心中有关包裹的调度问题。由于每天进入到配送中心的卡车数量比较多，而卸载点相对较少，如果不能对这些进入卡车进行合理的调度安排，就可能导致整个包裹转移网络的拥堵，从而导致更长的操作时间，所以如何对这些进来的卡车进行调度就显得至关重要。合理的调度能够降低操作费用，提高运输系统的可靠性，并且提升配送中心的竞争力。但往往最优的调度安排很难找到，如果找到一个调度，使得它接近最优调度，那么这个调度也是合理的。这节就使用LPT算法尝试解决该问题。通过几个具体的实例，分别使用随机算法R和LPT算法来对这些进入到配送中心的卡车进行调度安排，得到进入卡车的调度和相应的包裹流，再把用随机算法R得到的结果和用LPT算法得到的结果与最优解值进行比较，找到最坏情况界，，得出LPT算法可以有效地解决该问题。 第五章是对全文的总结以及对未来的展望。
【关键词】：调度 算法 最坏情况界 最大完工时间 配送中心 包裹运输
【学位授予单位】：浙江理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TH186
【目录】：

• 摘要4-6
• Abstract6-10
• 1 绪论10-16
• 1.1 调度问题概述10-11
• 1.2 算法的设计与分析11-12
• 1.3 带服务器的平行机调度问题12-13
• 1.4 目前国内外的研究现状13-15
• 1.5 论文结构及主要研究成果15-16
• 2 带单个服务器的平行机调度问题的最优算法设计16-26
• 2.1 引言16-18
• 2.2 符号及最优解下界18
• 2.3 最优算法OPA18-24
• 2.4 小结24-26
• 3 带两个服务器的平行机调度问题26-38
• 3.1 引言26-27
• 3.2 预备知识27
• 3.3 LS算法27-32
• 3.3.1 LS算法的结构28-30
• 3.3.2 LS算法的最坏情况界分析30-32
• 3.4 LPT算法32-37
• 3.5 小结37-38
• 4 LPT算法在配送中心的应用38-54
• 4.1 引言38
• 4.2 配送及配送中心概述38-40
• 4.3 问题背景描述40-44
• 4.3.1 包裹的转移操作40-41
• 4.3.2 包裹的工作流41-44
• 4.4 三种关于包裹的调度44-48
• 4.4.1 随机调度R45
• 4.4.2 最优调度OPT45-47
• 4.4.3 LPT算法调度47-48
• 4.5 不同调度方法的比较48-53
• 4.6 小结53-54
• 5 总结与展望54-56
• 参考文献56-60
• 攻读学位期间的研究成果60-62
• 致谢62

【参考文献】

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

1 徐俊刚,戴国忠,王宏安;生产调度理论和方法研究综述[J];计算机研究与发展;2004年02期

本文编号：754684