论文题目: 平行机半在线排序问题
论文类型: 博士论文
论文专业: 运筹学与控制论
作者: 罗润梓
导师: 孙世杰
关键词: 排序问题,半在线,竞争比
文献来源: 上海大学
发表年度: 2005
论文摘要: 本文主要考虑平行机半在线排序问题。本文首先简要介绍了排序问题、竞争比分析和近似算法等基本概念,总结了近年来出现的各个半在线模型及其有关结果。 第二章考虑已知工件最大加工时间的半在线模型,目标为极大化最小机器负载。主要讨论两个问题:1 三台同类机的情形,我们给出min3算法并且证明此算法的竞争比为max{r+1,（3s+r+1）/（1+r+s）}.rain3算法是紧的且当1≤s≤2、r=1时是最优的。2m台特殊同类机问题,我们给出Cmin算法及其竞争比max{m-1,（ms+m-1）/（m-1+s）},并证明Cmin算法是紧的且当1≤s≤（m-1）（m-2）（m≥3）时是最优的。 第三章考虑已知工件最大加工时间的半在线问题,目标为极小化机器最大负载。主要讨论四个问题:1 对于两台同类机的问题,我们给出竞争比分别为2（s+1）/（s+2）（1≤s≤2）和（s+1）/s（s>2）的Qmax2算法,并且证明此算法是紧的且相应某些s的特殊值是最优的。2 对于三台同类机半在线问题,我们给出Qmax3算法并证明此算法的竞争比不大于2（r+s+1）/（2r+s）（1<s≤2）和（r+2s+1）/（r+s）（s>2）且严格小于2.3对于三台特殊同类机问题,给出Qmax3t算法并证明其竞争比不大于（s+2）/2（1≤s≤2）和（s+2）/s（s>2）且恒小于2。4 最后我们考虑m台同型机问题,给出一个竞争比为（2m-3）/（m-1）的Cmax算法并证明此算法对任何m≥3是紧的。 第四章中,我们考虑已知工件总加工时间的两台同类机半在线问题,目标为极大化最小机器负载。我们给出Q2min算法并证明此算法的竞争比小于(2+21/2)/2,而此问题竞争比的下界为(1+51/2)/2。同时证明当s=(1+51/2)/2时Q2min算法最优的。 在第五章中,我们考虑带机器准备时间的已知工件总加工时间的半在线问题。第一节考虑P2,ri∣sum∣Cmin问题,给出Prsum算法并证明此算法的竞争比为3/2且是最优算法。在第二节则考虑Q2,ri∣sum∣Cmax问题,给出Qrmax算法并证明此算法的竞争比为21/2;同时给出此问题的一个下界。 第六章我们首先引进一个新的半在线术语:半在线模型的松弛,然后我们介绍一个新的半在线模型:已知工件最大加工时间在某一区域内,即known largest job interval模型。第一节考虑P2∣known largest job interval∣Cmax问题,我们给出Pinterval算法及其竞争比,并证明此竞争比是紧的且与最优竞争比的误差不超过4/（33）。第二节考虑P2∣known largest job interval∣Cmin问题,我们给出Pinterval算法的竞争比,并证明此竞争比是紧的且与最优竞争比的误差不超过1/4。
论文目录:
摘要
Abstract
第一章 绪论
§1．1 排序问题
§1．2 近似算法和竞争比分析
§1．3 半在线排序问题
§1．4 论文概述
第二章 已知工件最大加工时间的极大化目标问题
§2．1 引言
§2．2 三台同类机问题
§2．3 m台特殊同类机问题
第三章 已知工件最大加工时间的极小化目标问题
§3．1 引言
§3．2 两台同类机问题
§3．3 三台同类机问题
§3．4 三台同特殊同类机问题
§3．5 m台同型机问题
第四章 已知工件总加工时间的半在线模型
§4．1 1＜s＜(1+5~(1/2))/2时的情形
§4．2 s≥(1+5~(1/2))/2的情形
第五章 带机器准备时间的已知工件总加工时间的半在线模型
§5．1 P2，r_i|sum|C_(min)问题
§5．2 Q2，r_i|sum|C_(max)问题
第六章 半在线模型的松弛
§6．1 P2|Known largest job interval|C_(max)问题
§6．2 P2|Known largest job interval|C_(min)问题
第七章 小结
参考文献
作者在攻读博士学位期间公开发表及完成的论文
致谢
发布时间: 2005-09-16
参考文献
- [1].不确定情形下若干排序问题的研究[D]. 沈佳煜.南京理工大学2017
- [2].新型排序问题的计算复杂性研究[D]. 高园.郑州大学2018
- [3].依赖于资源分配的排序问题研究[D]. 殷娜.上海大学2015
- [4].若干排序问题研究[D]. 李好好.浙江大学2014
- [5].工件加工时间可变的现代排序问题[D]. 王吉波.大连理工大学2005
- [6].当代工业中的若干排序问题研究[D]. 季敏.浙江大学2006
- [7].通讯网络中排序问题的若干在线和高性能算法[D]. 叶德仕.浙江大学2005
- [8].关于分批排序问题的研究[D]. 李文华.郑州大学2006
- [9].窗时排序问题中的最优化算法研究[D]. 赵洪銮.山东大学2007
- [10].带尺寸、可拒绝的分批排序[D]. 张咸昭.曲阜师范大学2007
相关论文
- [1].在线平行机排序问题研究[D]. 丁际环.浙江大学2008
- [2].与Due Date相关的排序问题研究[D]. 沈灏.浙江大学2002
- [3].工件加工时间可变的现代排序问题[D]. 王吉波.大连理工大学2005
- [4].当代工业中的若干排序问题研究[D]. 季敏.浙江大学2006
- [5].若干批处理机排序与装箱问题的算法研究[D]. 石永强.浙江大学2005
- [6].关于分批排序问题的研究[D]. 李文华.郑州大学2006
- [7].一类平行机和批处理机组成的二阶段柔性流水作业问题[D]. 何龙敏.上海大学2006
- [8].工件加工时间非恒定的排序模型研究[D]. 程明宝.上海大学2006
- [9].带激活费用的平行机排序问题研究[D]. 韩曙光.浙江大学2007
- [10].可中断平行机排序问题研究[D]. 蒋义伟.浙江大学2007