学位论文 > 优秀研究生学位论文题录展示
两类加权幂和形式的分批排序问题
作 者: 李美华
导 师: 原晋江
学 校: 郑州大学
专 业: 运筹学与控制论
关键词: 单机 平行分批 在线 竞争比 加权完工时间平方和 加权完工时间常数次幂和 全多项式时间近似方案
分类号: O223
类 型: 硕士论文
年 份: 2008年
下 载: 3次
引 用: 0次
阅 读: 论文下载
内容摘要
平行分批排序和在线排序是两个发展迅速的排序模型。平行分批排序是指机器可以同时成批加工多个工件(有限或无限)。每批包含的工件同时开工同时完工。每批的加工时间是这批工件的最大加工时间。在线排序是指工件信息在其到达之前是一无所知的,并且一旦工件被安排后就不允许再改变。本文主要考虑了目标函数是和式的分批排序问题。首先研究了目标是最小化加权完工时间平方和的分批在线排序问题。在这个问题中,我们有一台批处理机,有n个按时在线到达的工件1,2,…,n.每个工件的加工时间为p_j,权重为w_j,到达时间为r_j.根据批容量b是无界还是有界,我们所考虑的模型可分别记为1|on-line,r_j,p-batch|∑w_jC_J~2与1|on-line,r_j,p-batch,b<n|∑w_jC_j~2.对这一问题本文得到如下结果。(1)给出了问题1|on-line,r_j,p-batch,b<n|∑w_jC_j~2的一个竞争比为16+O(ε)((?)_ε>0)的在线算法。(2)给出了问题1|on-line,r_j,p-batch|∑w_jC_j~2的一个竞争比为11.3429的在线算法。其次,本文对目标是加权完工时间常数次幂和的单机平行分批排序问题进行了研究。这里我们只考虑了批容量无界的情形。所研究问题可表示为1|p-batch,r_j|∑w_jC_j~h(h≥1为固定常数).文中通过利用划分时间轴和几何舍入的方法,把原始实例转化为较为简单的实例,并利用已有的拟多项式时间算法,最终给出了1|p-batch,r_j|∑w_jC_j~h(h≥1为固定常数)的一个全多项式时间近似方案。
|
全文目录
摘要 4-5 Abstract 5-8 第一章 引言 8-15 1.1 排序的介绍 8-9 1.2 在线排序和分批排序 9-11 1.3 算法和计算复杂性 11-13 1.4 相关结果及本文主要结果 13-15 第二章 最小化加权完工时间平方和的在线分批排序问题 15-24 2.1 准备工作 15-16 2.2 有界批模型的一个常数上界 16-18 2.3 无界批模型的一个在线算法 18-24 第三章 最小化加权完工时间常数次幂和的分批排序问题 24-30 3.1 准备工作 24 3.2 几个重要引理 24-27 3.3 一个全多项式时间近似方案 27-30 后记 30-31 参考文献 31-34 致谢 34
|
相似论文
- 多参数水质在线监测系统软件设计,TP3
- 面向动态文档集的大规模文本索引构建技术的研究,TP391.3
- 部队在线考试系统设计与实现,TP311.52
- 部队军事理论在线考试系统设计与实现,TP311.52
- 基于LPC2368的16位蓄电池在线监测仪的设计与实现,TP216
- 江西省商务学校在线考试系统,TP311.52
- 基于web的考试系统的设计与实现,TP311.52
- 基于Hadoop的在线购物原型系统的设计与实现,TP311.52
- 钢铁企业物料存取空间调度优化系统,F426.31
- 废纸造纸废水和生活污水处理技术方案的研究,X793
- 在线相册冲印系统的设计与实现,TP311.52
- 基于SaaS的高校就业综合管理平台设计与实现,TP311.52
- 数学公式在线考试系统的设计与实现,TP311.52
- 基于计算机视觉的带钢表面缺陷在线检测系统的设计与实现,TP391.41
- 在线招投标系统信息安全的设计与实现,TP393.08
- 基于高斯过程的在线建模问题研究,TP181
- 用于波像差检测的二元光栅掩模标记优化方法研究,TN305.7
- DURO:一种针对RAID-6单盘失效在线重构方法的研究,TP333
- 基于HMM的社交网络连接关系研究,F49
- 在线体育视频剪辑系统中元数据的应用研究,TP391.41
- 教师在线专业发展问题研究,G451.1
中图分类: > 数理科学和化学 > 数学 > 运筹学 > 统筹方法
© 2012 www.xueweilunwen.com
|