学位论文 > 优秀研究生学位论文题录展示

两类特殊的在线分批排序问题

作　者: 王申重
导　师: 李文华
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 单机排序平行机排序平行分批在线特殊工件竞争比
分类号: O223
类　型: 硕士论文
年　份: 2008年
下　载: 4次
引　用: 0次
阅　读: 论文下载

内容摘要

本文主要考虑了两类特殊的在线分批排序问题.所谓在线,本文指的是按时在线.工件信息在其到达之前是一无所知的,并且一旦工件被安排后就不允许再改变.所谓平行分批排序是指机器可以同时成批加工多个工件.每批包含的工件同时开工同时完工,批的加工时间是这批中加工时间的最大者.首先研究了批容量为3的单机平行分批排序.主要结果如下:（1）对排序问题1|p - batch,b = 3;p_j = 1; on - line;r_i;limited restarts|C_max,我们给出了竞争比为（?）的最好可能的在线算法.（2）对排序问题1|p - batch, b = 3; on - line, r_i; limited restarts|C_max,我们证明了竞争比下界为（?）,并给出了竞争比为（?）的在线算法.其次,对带有特殊工件的平行分批排序问题进行了研究.这里所有工件都是在线的,但是,其中有一些工件,它们要求单独成批,其它工件不能与其共批,并且一旦到达就要对其立即加工。我们称其为特殊工件,其它工件称为普通工件.假设特殊工件间不冲突.主要结果如下:（1）对排序问题1|special job（restart）;p_j = 1; on - line, r_i, D|Σf_j,我们给出了竞争比为（?）的最好可能的在线算法.（2）对排序问题P₂|special job（pmtn）;p - batch, b =∞; on - line, r_i|C_max,我们证明了竞争比下界为（?）,并给出了竞争比为（?）的在线算法.（3）对排序问题P₂|special job（restart）;p - batch, b =∞; on -line, r_i|C_max,我们给出了竞争比为2的最好可能的在线算法.

全文目录

摘要  4-5
Abstract  5-8
第一章绪言  8-14
  1.1 排序的介绍  8-9
  1.2 在线排序、平行机排序和特殊工件  9-11
  1.3 排序的记号  11-12
  1.4 已知结果及本文主要结果  12-14
第二章批容量为3的单机有限重启问题  14-29
  2.1 引言  14-15
  2.2 标准工件的情形  15-22
  2.3 任意工件的情形  22-29
第三章带有特殊工件的在线排序问题  29-41
  3.1 引言  29-31
  3.2 目标函数为利润最大的情形  31-35
  3.3 目标函数为最小化最大完工时间的情形  35-41
后记  41-42
参考文献  42-44
致谢  44

两类特殊的在线分批排序问题

内容摘要

全文目录

相似论文