带服务器的平行机排序问题研究

发布时间：2021-11-14 05:04

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

【文章来源】：浙江理工大学浙江省

【文章页数】：39 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 排序调度问题概述
    1.2 算法设计与分析
    1.3 带服务器的平行机调度问题
    1.4 目前国内外的研究现状
    1.5 论文结构
2 两台机情形下的LS算法
    2.1 引言
    2.2 LS算法介绍
    2.3 预备知识
    2.4 LS算法紧界的证明
    2.5 本章小结
3 两台机情形下的LPT算法
    3.1 LPT算法介绍
    3.2 LPT算法的紧界证明
    3.3 本章小结
4 三台机情形下的LS算法
    4.1 预备知识
    4.2 LS算法界的证明
    4.3 本章小结
5 总结与展望
参考文献
附录
致谢


【参考文献】：
期刊论文
[1]带有单服务器的并行机调度问题[J]. 谢谢,李彦平.  沈阳大学学报(自然科学版). 2012(04)



本文编号：3494014