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

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 调度问题概述

1.2 算法的设计与分析

1.3 带服务器的平行机调度问题

1.4 目前国内外的研究现状

1.5 论文结构及主要研究成果

2 带单个服务器的平行机调度问题的最优算法设计

2.1 引言

2.2 符号及最优解下界

2.3 最优算法OP A

2.4 小结

3 带两个服务器的平行机调度问题

3.1 引言

3.2 预备知识

3.3 LS算法

3.4 LP T算法

3.5 小结

4 LP T算法在配送中心的应用

4.1 引言

4.2 配送及配送中心概述

4.3 问题背景描述

4.4 三种关于包裹的调度

4.5 不同调度方法的比较

4.6 小结

5 总结与展望

参考文献

攻读学位期间的研究成果

致谢