| 【中文题名】 | 机器带准备时间的分批排序问题研究 |
| 【英文题名】 | Batch Scheduling with Non-Simultaneous Machine Available Time |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-7-31 |
| 【中关键词】 | 分批排序,带准备时间,同型机,同类机,最差性能比, |
| 【英关键词】 | Scheduling,Batch scheduling,Identical machines,Uniform machines,Worst case performance ratio, |
| 【分类导航】 | 数理科学和化学>数学>运筹学>排队论（随机服务系统）>> |
| 【论文摘要】 |
排序论又称为时间表理论，其作为运筹学的一个分支，作为一门应用科学，有着深刻的实际背景和广阔的应用前景。分批排序、机器带准备时间的排序问题是近些年来新兴的排序模型，这两类模型更具有现实意义。本文将以上两种新的排序模型相结合，讨论机器有准备时间的分批排序问题，并在此基础下，考虑两个目标函数，极小化最大完工时间(C_(max))和加权总完工时间(∑w_jC_j)，论文的结构如下安排：
第一章，主要概述了排序问题的发展、研究现状，简单介绍了本文的主要研究成果。
第二章，主要研究了机器带准备时间的平行机上的分批排序问题，这里目标函数为工件的极大完工时间，这类问题是NP-难的，已有的结果比较少。在本章我们结合FBLPT算法，Multifit算法和LPT算法，利用复制的方法分别对机器是同型机和同类机的两种情形设计出近似算法，并证明它们的最差性能比分别不超过(2-1／B)[9／7+(1／2)~k]和5／3(2-1／B)。
第三章，排序问题P_m，α_i|B|∑w_jC_j是一个NP-难问题，本章主要考虑在工件的加工时间都相等的特殊情况下，即p_j=p时，给出一个最优的算法，并且给出了最优性的... |
| 【论文题纲】 |
|
摘要 |
3-4 |
|
ABSTRACT |
4-7 |
|
第一章 绪论 |
7-14 |
|
§1.1 排序问题的概念及其问题描述 |
7-10 |
|
§1.1.1 排序问题的概念 |
7 |
|
§1.1.2 排序问题的表示 |
7-10 |
|
§1.2 相关概念 |
10-13 |
|
§1.2.1 计算复杂性 |
10-11 |
|
§1.2.2 P类,NP类和NP完备 |
11-12 |
|
§1.2.3 近似算法 |
12-13 |
|
§1.3 本文主要结果及创新点 |
13-14 |
|
第二章 目标函数为最大完工时间的排序问题 |
14-21 |
|
§2.1 预备知识 |
14-15 |
|
§2.2 Multifit算法 |
15-17 |
|
§2.3 问题P_m,a_i|B|C_(max)的近似算法 |
17-19 |
|
§2.4 问题Q_m,a_i|B|C_(max)的近似算法 |
19-20 |
|
§2.5 结论 |
20-21 |
|
第三章 目标函数为加权总完工时间的排序模型 |
21-27 |
|
§3.1 问题的描述及研究现状 |
21 |
|
§3.2 加工时间相等的情形 |
21-25 |
|
§3.3 工件有常数个到达时间的情形 |
25-26 |
|
§3.4 结论 |
26-27 |
|
参考文献 |
27-30 |
|
附录一 攻读硕士学位期间撰写的论文 |
30-31 |
|
附录二 致谢 |
31 |
|
| 【DOI】 | LunWen.ID:2.2008.14805 |
