论文摘要
作业调度问题是研究利用有限的计算资源来计算大量的计算任务时碰到的问题。本文的工作是针对作业调度中的两个具体问题展开的。本文首先研究的是带容量约束的多机调度问题,包括它的均一性版本,一般性版本和推广的2维、k维版本问题。容量限制是指每台机器并不能处理任意多的作业,不同的机器可能具有容量上的约束,这时需要在多台机器上调度作业使得最晚完成时间最小并且满足容量约束。均一性版本问题中,单个作业在不同机器上的运行时间是一致的,本文利用线性规划上的迭代取整法给出了一个3-近似算法。这是第一次将迭代取整法应用到调度问题中。对于一般性版本,每台机器在不同机器上运行时间可能不同,本文利用放松判定过程给出了一个2-近似算法。在2维、k维容量限制调度问题中,本文将容量限制和运行时间优化推广成同一个概念：容量限制。本文分别给出了一个（4,4）-放松判定过程和一个(O（k）,O（k）,...,O（k）-放松判定过程。本文接下来研究带作业依赖的单机调度中的最小的最大作业延迟时间问题。本文研究了单台机器上不同作业之间带有依赖关系的模型,利用迭代取整法给出了一个2-近似算法。此算法也可以应用于构造一个适用于经典的带作业依赖的单机调度的最小带权完成时间和问题的2-近似算法。这一工作的另一个意义是再次印证了迭代取整法在解决难解问题中具有一定的一般性。
论文目录
相关论文文献
- [1].一种作业调度和计算资源动态分配方法[J]. 电子技术与软件工程 2018(16)
- [2].用于高性能计算的作业调度能效性研究综述[J]. 计算机工程与科学 2019(09)
- [3].企业生产作业调度优化研究[J]. 魅力中国 2009(29)
- [4].拖船联合作业调度系统设计[J]. 船电技术 2014(03)
- [5].船舶曲面分段建造作业调度数字化仿真与优化[J]. 机械设计与制造 2020(02)
- [6].基于Plant Simulation的作业调度仿真研究[J]. 物流工程与管理 2019(09)
- [7].钢厂多行车作业调度方法研究[J]. 机械设计与制造 2016(11)
- [8].供应链协同生产作业调度优化研究[J]. 宁波大学学报(理工版) 2011(01)
- [9].集装箱码头岸吊作业调度建模及调度策略研究[J]. 工业工程与管理 2009(05)
- [10].面向多约束的船舶组立构件建造作业调度方法[J]. 船舶工程 2020(03)
- [11].银行信息系统作业调度自动化建设[J]. 中国金融电脑 2013(04)
- [12].物联网在混凝土施工作业调度管理中的应用[J]. 小水电 2016(06)
- [13].云计算环境下人工蜂群作业调度算法设计[J]. 数学的实践与认识 2012(10)
- [14].网格环境下可靠的可分割作业调度机制[J]. 小型微型计算机系统 2011(03)
- [15].北京市农机作业调度管理与精准作业系统[J]. 农业工程 2013(S2)
- [16].基于遗传算法的“人-多台单机”柔性作业调度[J]. 中国机械工程 2013(16)
- [17].特钢厂炼钢-浇铸流程作业调度优化仿真模型[J]. 计算机应用与软件 2019(08)
- [18].大规模异构集群地震作业调度与资源管理系统的设计与实现[J]. 石油地球物理勘探 2017(S2)
- [19].粒子群算法在车间作业调度问题中的仿真研究[J]. 计算机仿真 2011(11)
- [20].基于遗传算法的舰载装备多目标作业调度优化研究[J]. 系统仿真学报 2019(05)
- [21].面向云计算的期限约束的MapReduce作业调度方法[J]. 计算机与现代化 2018(11)
- [22].物流自动化仓库拣选作业调度粒子群优化研究[J]. 机械制造 2010(01)
- [23].基于高性能计算的联想智能超算平台LiCO的设计与实现[J]. 软件工程 2019(02)
- [24].基于生产资源的柔性作业调度任务优选方法[J]. 制造业自动化 2015(07)
- [25].基于改进遗传算法的单机成组作业调度[J]. 计算机仿真 2010(04)
- [26].混合遗传算法在多目标柔性作业调度中的应用[J]. 计算机仿真 2009(07)
- [27].Hadoop平台中作业调度算法分析与改进研究[J]. 微型机与应用 2016(11)
- [28].多目标军用飞机维修作业调度优化研究[J]. 计算机工程与应用 2016(14)
- [29].视频监控在高速路作业调度系统上的应用[J]. 微型机与应用 2015(01)
- [30].遥感数据集群处理作业调度管理系统研究[J]. 计算机工程与应用 2012(25)