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

工件带有优先约束的平行机在线排序问题

作　者: 吴丰金
导　师: 原晋江
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 平行机排序 在线排序 优先约束 竞争比
分类号: O223
类　型: 硕士论文
年　份: 2008年
下　载: 4次
引　用: 0次
阅　读: 论文下载
 

内容摘要


所谓排序,就是在一定的约束条件下分配时间资源去完成一些任务,使一个或多个目标达到最优.近年来,在线排序是发展比较迅速的排序模型。在线排序是指工件所有信息在其到达之前都是未知的,工件在到来之前不能安排作业,工件到达后也没必要立即安排,但是一旦工件被安排后就不允许再改变。本文中,我们研究了一种在线排序模型:带有优先约束的工件在平行机上的在线排序问题.有n个带有优先约束的工件J1,J2,…,Jn.每个工件都分别有一个到达时间rj,加工时间pj.这些工件需要在m（m≥1）台平行机上进行加工.工件一旦开始加工,中间不能被打断,直到该工件被加工完毕。我们的目标函数是最小化机器完工时间的平方和.用Graham等人[3]提出的三参数表示法,我们的问题可以表示为:（?）本文的主要结果如下:（1）对于排序模型（?）,任意在线算法的竞争比下界不小于5/4.（2）对于排序模型P3|pj=1,intreei released at （?）,任意在线算法的竞争比下界不小于302/281.（3）对于排序模型P2|pj=p,chainsi released at （?）,任意在线算法的竞争比下界不小于106/81.（4）对于排序模型P2|pj=1,preci released at （?）,任意在线算法的竞争比下界不小于65/49,并给出了一个竞争比不大于2的在线算法.（5）给出了排序模型Pm|pj=1,outtreei released at （?）一个竞争比不大于m的在线算法.

全文目录


摘要  3-4
Abstract  4-7
第一章 引言  7-13
  §1.1 排序的介绍  7-9
  §1.2 排序的记号  9-11
  §1.3 相关文献综述  11-12
  §1.4 本文主要结果  12-13
第二章 工件带有序约束的平行机在线排序问题  13-33
  §2.1 相关介绍  13-14
  §2.2 竞争比的下界  14-25
  §2.3 在线算法及证明  25-33
后记  33-34
参考文献  34-36
致谢  36

相似论文

  1. 带参数的平行机和流水作业排序问题的复杂性及算法研究,O223
  2. 工件可拒绝的在线排序问题的两个模型,O223
  3. 最大化按时完工工件个数的单位长度工件的单机在线分批排序问题,O223
  4. 部分机器分批的平行机在线排序,O223
  5. 数据仓库ETL分配与调度模型研究,TP311.13
  6. 链组约束下的平行机排序问题,O223
  7. 两类加权幂和形式的分批排序问题,O223
  8. 带有不可相容工件组的在线排序问题,O223
  9. 成组加工排序和供应链在线排序问题,O223
  10. 基于SOA的统一权限控制机制研究与应用,TP393.09
  11. 工件有优先约束的分批排序问题,O223
  12. 具有等长工件平行批排序模型的一些结果,O223
  13. 带有链优先约束的两类排序问题,O223
  14. 可重构系统中实时任务调度算法研究,TN791
  15. 实时系统任务调度若干关键技术的研究,TP316.2
  16. 具有非交叉维修时间的平行机在线排序,O223
  17. 关于同类机半在线排序问题的若干研究,O223
  18. （半）在线排序中若干问题的研究,O223
  19. 同类机半在线机器覆盖问题研究,O223
  20. 一定条件下平行机排序问题的研究,O223

中图分类: > 数理科学和化学 > 数学 > 运筹学 > 统筹方法
© 2012 www.xueweilunwen.com