| 【中文题名】 | 工件可拒绝的单机分批排序问题 |
| 【英文题名】 | Single Machine Batch Scheduling with Rejection |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-7-31 |
| 【中关键词】 | 分批排序,可拒绝,到达时间,最大完工时间,PTAS, |
| 【英关键词】 | Batch scheduling,Rejection,Release times,Makespan,PTAS, |
| 【分类导航】 | 数理科学和化学>数学>运筹学>排队论（随机服务系统）>> |
| 【论文摘要】 |
排序问题是一类重要的组合优化问题，它广泛应用于管理科学、计算机科学、工农业生产、交通运输等许多领域，一直受到国内外学术界的重视。而其中的分批排序问题以及工件可拒绝的排序问题，因其具有明显的实际应用背景，更是吸引了国内外许多学者。特别是对于工件可拒绝的排序问题，这一方面的研究结果还比较少，本文主要研究工件可拒绝的分批排序问题。
论文共分三章。
第一章主要介绍了排序的产生背景、发展及其一些符号等相关的基本知识。
第二章讨论的是工件可拒绝同时到达时的单机分批排序问题，目标函数是极小化最大完工时间加上被拒绝工件的拒绝费用之和。本文通过动态规划算法给出了多项式时间的精确算法，借助于数据结构中的堆排序，我们将算法复杂性降低为O(n~2 log B)。所研究的问题若用三参数法应表示为1|rej，B|C_(max)+∑_(j∈R)e_j。
第三章主要研究了工件可拒绝且不同时到达时的单机分批排序问题，即问题1|r_j，rej，B|C_(max)+∑_(j∈R)e_j，给出了PTAS算法。 |
| 【论文题纲】 |
|
摘要 |
3-4 |
|
ABSTRACT |
4-6 |
|
第一章 绪言 |
6-11 |
|
1.1 排序问题的概念及表示 |
6-7 |
|
1.2 分批排序及可拒绝排序 |
7-8 |
|
1.3 计算复杂性 |
8-9 |
|
1.4 P类,NP类和NP-完备类 |
9-10 |
|
1.5 本文主要成果及创新 |
10-11 |
|
第二章 工件可拒绝同时到达时的单机分批排序问题 |
11-16 |
|
2.1 引言 |
11-12 |
|
2.2 符号及预备知识 |
12-13 |
|
2.3 主要结果 |
13-15 |
|
2.4 结论 |
15-16 |
|
第三章 工件可拒绝且不同时到达时的单机分批排序问题 |
16-26 |
|
3.1 预备知识 |
16-17 |
|
3.2 一个特殊情形 |
17-21 |
|
3.3 一般情形 |
21-25 |
|
3.4 结论 |
25-26 |
|
参考文献 |
26-29 |
|
硕士生期间撰写的论文 |
29-30 |
|
致谢 |
30 |
|
| 【DOI】 | LunWen.ID:2.2008.14807 |
