学位论文 > 优秀研究生学位论文题录展示
有资源限制的分批排序问题的算法研究
作 者: 张玲玲
导 师: 张玉忠
学 校: 曲阜师范大学
专 业: 运筹学与控制论
关键词: 资源限制 分批排序 NP-困难 最差性能比 最优算法 近似算法
分类号: O226
类 型: 硕士论文
年 份: 2007年
下 载: 52次
引 用: 0次
阅 读: 论文下载
内容摘要
排序问题是组合优化领域的一个重要分支,它有着重要的应用背景和深刻的理论意义.而分批排序是继经典排序之后的较新排序模型之一.本文就这一模型的有资源限制的问题做了一些工作.全文共分四章.第一章简单介绍了排序问题的相关定义、记号及相关预备知识.第二章考虑了单机分批排序问题中目标是极小化加权总完工时间的问题.将FBLW算法进行推广,就工件到达时间均为正整数、加工时间恒为1的情形,设计出了一个时间复杂性为O(n2 log n)的最优算法;对工件有常数m个到达时间、加工时间恒等的情形给出一个最优算法,并给出其算法复杂性为O(2m-1n log n).第三章研究了分批排序中机器有使用限制的两个问题.这是首次将机器有使用限制的条件在分批排序问题中进行考虑.对于目标是极小化最大完工时间、工件不可中断的单机分批排序问题,我们对批容量无限的情形找到了多项式时间的最优算法,对批容量有限的情形提出了一个最差性能比为4/3的近似算法,并且界是紧的.第四章总结了全文并指出了有待研究的排序问题.
|
全文目录
摘要 3-4 ABSTRACT 4-7 第一章 绪论 7-15 §1.1 排序的概念及其应用背景 7-8 §1.2 排序问题的表示 8-11 §1.3 计算复杂性 11-13 §1.4 分批排序 13-14 §1.5 本文主要成果及创新 14-15 第二章 一种极小化∑ω_jC_j的分批排序问题 15-20 §2.1 问题的研究现状 15-16 §2.2 工件有常数个到达时间、加工时间恒等的情形 16-18 §2.3 工件到达时间均为正整数、加工时间恒为1的情形 18-19 §2.4 结束语 19-20 第三章 机器有使用限制的分批排序问题的算法研究 20-26 §3.1 问题描述及研究现状 20-21 §3.2 一些用到的记号 21-22 §3.3 批容量有限的情形1|nr-α,B|C_(max) 22-25 §3.4 批容量无限的情形1|nr-α,B=∞|C_(max) 25 §3.5 结论 25-26 第四章 总结与展望 26-27 参考文献 27-30 硕士生期间撰写的论文 30-31 致谢 31
|
相似论文
- 干部管理信息系统的设计与实现,TP311.52
- 中国城市成年子女代际支持的阶层差异,C913.5
- 基于支持向量回归的电力采购评标方法研究,F224
- 有服务等级约束的平行机排序问题,O223
- 工件有到达时间的多代理排序问题,O223
- 具有学习与退化效应的排序问题,O223
- 无线传感器网络中的拓扑控制及能量有效利用问题研究,TN929.5
- 电磁场积分方程自适应交叉近似算法的研究,O175.5
- 与双目标分批排序相关的排序问题,O223
- 关于可靠性设施布局问题的近似算法,TB114
- LDPC码译码方法及性能分析研究,TN911.2
- 机器带学习效应的两类排序问题,O223
- 供应链管理中的分批调度问题,O223
- 无线传感器网络的自保护问题研究,TN929.5
- 最小化κ限制连通分支数的近似算法,O157.5
- 多类型客户k-种产品的工厂选址问题,F274
- 会话推理的元语用研究,H030
- 比特交织Turbo编码调制技术的研究,TN911.2
- 双空时传输分集技术研究,TN919.3
- 基于情景感知服务的旅游行程规划研究,F590
- 生产管理中的若干排序问题,O223
中图分类: > 数理科学和化学 > 数学 > 运筹学 > 排队论(随机服务系统)
© 2012 www.xueweilunwen.com
|