论文摘要
调度问题是一类重要的组合优化问题.根据其内容特点,人们把调度问题分为经典调度问题和现代调度问题.作为运筹学的一个分支,调度问题及其理论在多个学科领域都是不可或缺的重要组成部分.同时,因其深刻的理论意义和广泛的应用前景长期以来受到了数学家、工程学家及计算机科学家的广泛关注和研究.过去很长一段时间,人们对调度问题的研究大都专注于经典调度问题中机器只有几台或机器没有周期维护要求等问题.然而,对于机器和工件成批且工件数严格大于机器台数的周期维护平行机调度问题的研究相对较少.在本文中,首先对周期维护调度问题的应用背景、基本概念及国内外研究现状等进行了详细的综述.接着,文章主要研究了三类与机器需要周期维护有关的调度问题.第一类是工件加工时长相等,工件在加工过程中可中断的周期维护平行机调度问题.第二类是工件加工时长相等,工件在加工过程中不可中断的周期维护平行机调度问题.第三类是工件加工时长不全相等,工件在加工过程中可中断的周期维护平行机调度问题.文中根据工件在加工过程中可否中断这一性质及工件加工时长间的关系,对这三类周期维护调度问题进行分类研究.文中通过“注水模型思想”及“横向切割法”设计出相应的算法以求其最优时间表长,最后由定理的形式证明了算法的合理性及由相应的算法获得的时间表长为最优时间表长.本文的研究从一定意义上推广了周期维护平行机调度理论.不仅如此,在该文中所运用的思想方法和所获得结果,为深入研究现代调度理论中出现的一些机器成批的周期维护调度问题奠定了一定的基础.
论文目录
文章来源
类型: 硕士论文
作者: 陈先康
导师: 程贞敏
关键词: 组合最优化,中断,周期维护,算法,最优化时间表长
来源: 贵州大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 贵州大学
分类号: O223
总页数: 61
文件大小: 1944K
下载量: 11