| 【中文题名】 | 若干单机在线排序问题研究 |
| 【英文题名】 | Study on Some Single-Machine On-line Scheduling Problems |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2004-6-28 |
| 【中关键词】 | 运筹学,排序,单机动态排序问题,在线最优排序,中断, |
| 【英关键词】 | operational research,scheduling,single machine dynamic scheduling problems,on-line optimal schedule,preemption, |
| 【分类导航】 | 数理科学和化学>数学>运筹学>统筹方法>> |
| 【论文摘要】 |
排序问题是一类重要的组合优化问题，它是利用一些处理机、机器或资源最优的完成一批给定的任务或作业，经过近半个世纪的努力，排序理论已经发展成一门相当重要的学科，并且应用非常广泛。
在做决策之前，所有任务的信息都是已知的情况下做出的排序称为静态离线最优排序，在做决策的时间点上，只知道当前可排任务的信息而做出的最优排序称为在线最优排序。
本文选择单机排序问题为研究对象，并且研究单机排序问题的动态在线情况。首先建立了一般化中断模型，然后在此基础上研究了几类单机排序问题的动态在线最优排序问题，本文所做的工作如下：
首先，我们一般化了任务中断模型，讨论了定义在更一般意义下的可中断动态单机排序问题，即任务被中断后不能简单的恢复加工，而是需要有一定的时间延迟，延迟是由任务的安装时间和任务在中断后恢复加工时其一部分(或全部)需要返工的时间两部分共同造成的情况。通过刻化上述条件，给出了两种中断一安装重复模型一般化了任务可中断的概念，同时我们研究并给出了并行机排序问题P_2|prmp|C_(max)在中断—重复模型下的静态调度算法。
其次，我们研究了总加权最小完工时间的... |
| 【论文题纲】 |
|
摘要 |
4-6 |
|
Abstract |
6-10 |
|
第一章 绪论 |
10-17 |
|
1.1 引言 |
10-11 |
|
1.2 国内外排序问题研究概况 |
11-13 |
|
1.3 单机在线排序问题 |
13-15 |
|
1.4 本文主要工作概述 |
15-17 |
|
第二章 基础知识 |
17-30 |
|
2.1 排序问题的定义 |
17-23 |
|
2.2 排序问题的分类 |
23-27 |
|
2.3 排序问题的求解 |
27-28 |
|
2.4 排序问题的算法与复杂性 |
28-30 |
|
第三章 一般化可中断模型 |
30-39 |
|
3.1 引言 |
30 |
|
3.2 一般化可中断模型 |
30-32 |
|
3.3 排序问题P_2prmpC_(max)在中断-重复模型下的调度 |
32-39 |
|
第四章 总加权最小完工时间的在线调度 |
39-47 |
|
4.1 排序问题1sum (w_jc_j) |
39-40 |
|
4.2 1r_j,prmpsum (w_jc_j)，在中断-恢复模型下的在线调度 |
40-41 |
|
4.3 1r_j,prmpsum (w_jc_j)在中断-安装重复模型下的在线调度 |
41-47 |
|
第五章 排序问题1r_j,prmpsum (w_j(1-e~(-acj)))的动态在线调度 |
47-52 |
|
5.1 排序问题1r_j,prmpsum (w_j(1-e~(-acj))) |
47 |
|
5.2 在中断-恢复模型下的在线最优调度规则 |
47-48 |
|
5.3 在中断-安装重复模型下的在线最优调度规则 |
48-52 |
|
第六章 一般费用函数问题1r_j，prmpf_(max)的在线调度 |
52-58 |
|
6.1 排序问题1precf_(max) |
52-53 |
|
6.2 在中断-恢复模型下的在线调度 |
53-55 |
|
6.3 在中断-安装重复模型下的在线最优调度 |
55-58 |
|
第七章 排序问题1r_j,chains,prmpsum (w_j(1-e~(-acj)))在的线调度 |
58-65 |
|
7.1 排序问题1chainssum (w_j(1-e~(-acj))) |
58-60 |
|
7.2 链式约束在中断-恢复模型下的在线调度 |
60-62 |
|
7.3 链式约束在中断-安装重复模型下的在线调度 |
62-65 |
|
总结与展望 |
65-67 |
|
致谢 |
67-68 |
|
参考文献 |
68-72 |
|
攻读硕士期间参加的科研项目、获奖情况、发表和完成的论文 |
72-74 |
|
| 【DOI】 | LunWen.ID:2.2008.14414 |
