论文摘要
排序问题是运筹学与组合优化领域中的一类重要问题.对排序理论的研究具有重要的理论意义和广阔的实际应用前景.数十年来,人们对此专题进行了深入地研究,并提出了大量的模型和优秀的算法.在排序论的大部分文献中,排序问题分为离线和在线排序两种.所谓“离线”是指所有工件的信息都事先已知.而“在线”是指事先不知道工件的信息,工件的信息是逐个释放的.工件只有在到达后才知道它的信息.在决定当前工件的加工时,对其后面到达的工件的信息是一无所知的,并且工件一旦分给某台机器加工就不允许改变.随着排序理论和应用的发展,上面的分类已不足以包含所有的排序问题.大量问题的情况往往介于两者之间.从而“半在线”模型由于其在实践中的广泛应用引起了大家的重视.所谓“半在线”即所知道的工件信息介于离线和在线之间.或者说在半在线模型中人们知道未来工件的部分信息,但仍然要求工件一旦分给某台机器加工就不允许改变.人们试图利用某些部分信息设计出比已有最好在线算法更好的算法.本文研究的模型是带有机器准备时间的两台恒同平行机半在线排序问题.用三参数表示为,P2,ri|sum&decr|Cmax.也就是说,有两台恒同机且机器具有准备时间.已知所有工件的加工时间总和（sum）并且工件按加工时间递减顺序（decr）在线到达.目标为极小化最大完工时间（makespan）.在第一章中,我们主要向大家介绍了排序问题的一些基础知识和相关的文献.在第二章中,我们研究了P2,ri|sum&decr|Cmax（M）和P2,ri|sum&decr|Cmax（J）.对上述两个问题,我们给出了竞争比为7/6的半在线算法,并进行了严格的证明.
论文目录
相关论文文献
- [1].高宝创超快速印刷准备时间[J]. 广东印刷 2020(05)
- [2].装备全寿命阶段技术准备时间要求验证方法分析[J]. 军械工程学院学报 2015(01)
- [3].动中抓教“四步法”[J]. 政工导刊 2017(06)
- [4].预先信息的不确定性与准备时间对任务切换的影响[J]. 心理学报 2010(03)
- [5].军用飞机再次出动准备时间计算方法[J]. 北京航空航天大学学报 2008(12)
- [6].准备时间和预先信息对任务切换的影响[J]. 心理学报 2008(08)
- [7].任务前准备时间与语言复杂性对英语学习者复述故事的影响研究[J]. 佳木斯职业学院学报 2018(11)
- [8].全寿命过程装备准备时间验证费用优选模型[J]. 计算机与数字工程 2016(02)
- [9].从“预战场”里涅槃重生[J]. 解放军生活 2019(10)
- [10].低成本的现场改进方法[J]. 上海质量 2008(02)
- [11].构建急危重症手术护理配合救治流程对女性患者抢救效果的影响[J]. 临床研究 2020(09)
- [12].细节管理在院前急救中的应用[J]. 护理实践与研究 2015(05)
- [13].缩短你的印前准备时间[J]. 印刷经理人 2010(11)
- [14].军用飞机再次出动准备时间仿真预计方法研究[J]. 项目管理技术 2010(03)
- [15].两个带机器准备时间的半在线排序[J]. 广西科技师范学院学报 2017(06)
- [16].英语教学中任务前准备时间的定量分析[J]. 台州学院学报 2016(01)
- [17].品管圈活动对缩短日透析物品准备时间的效果研究[J]. 齐齐哈尔医学院学报 2016(10)
- [18].品管圈在缩短急诊患者紧急输血准备时间中的应用[J]. 现代实用医学 2015(10)
- [19].策略准备时间对二语对话型口语表现的影响（英文）[J]. Chinese Journal of Applied Linguistics 2015(03)
- [20].词汇准备时间对外语视听理解及焦虑的影响[J]. 外语教学 2012(06)
- [21].完美打造宝典[J]. 小学生必读(中年级版) 2011(12)
- [22].带有机器准备时间且允许重排的在线排序(英文)[J]. 运筹学学报 2010(03)
- [23].带准备时间的同类机半在线问题的近似算法[J]. 菏泽学院学报 2009(05)
- [24].悉心呵护孩子纯真的心[J]. 新课程(上) 2013(12)
- [25].考前三分钟镇静操[J]. 高中生 2008(12)
- [26].于德北 孩子的世界让我感动[J]. 东北之窗 2011(11)
- [27].带有准备时间和退化维护的单机排序问题[J]. 平顶山学院学报 2018(05)
- [28].带有准备时间和凸资源分配的单机排序问题[J]. 平顶山学院学报 2018(05)
- [29].别让TPP牵着鼻子走[J]. 光彩 2015(11)
- [30].劳动者莫入加班维权误区[J]. 劳动保障世界 2012(03)