论文部分内容阅读
带服务装置的平行机调度问题在现代柔性制造中有着重要的应用背景.本文主要研究带一个装载服务器和一个卸载服务器的平行机调度问题,都是以极小化最大完工时间作为我们的研究目标.分别在两台平行机和三台平行机情形下,分析了经典的LS算法和LPT算法的最坏情况界的情况. 全文共分五章: 在第一章中,简要地介绍了调度问题的基本知识和本文所要研究的带服务器的调度问题的相关背景、这些问题的研究现状和我们在文中所要研究的问题. 在第二、第三章中,研究带有装、卸服务器的两台平行机调度问题.每个工件在加工之前需要由一个装载服务器装载到两台机器中的一台机器上,在加工完成之后再由卸载服务器把工件从平行机上卸载下来,这里的装、卸载的时间均为单位时间,目标是极小化最大完工时间.第二章中主要研究两台平行机情形的LS算法(List Scheduling)的最坏情况界问题,证明了该算法下的紧界为11/7.第三章中主要研究两台平行机情形的LPT算法的最坏情况界,证明了该算法下最坏情况紧界为7/6.上述结果改进了已有文献中的结果. 在第四章中,研究带有装卸服务器的三台平行机情形,分析了LS算法的最坏情况界至多为17/9. 第五章对全文进行总结并提出相关问题以及进一步的研究方向.