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

具有非交叉维修时间的平行机在线排序

作　者: 财玉华
导　师: 林诒勋
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 平行机排序 非交叉维修时间 可中断排序 在线算法 LS算法 竞争比
分类号: O223
类　型: 硕士论文
年　份: 2007年
下　载: 27次
引　用: 0次
阅　读: 论文下载
 

内容摘要


本文主要研究的是具有非交叉维修时间的平行机在线排序问题。在排序问题中，平行机排序是其中最活跃的分支之一。无论是对离线的还是在线的，数十年来人们进行了大量的研究。关于平行机排序问题的文献大都是假设所有机器自始至终都是可使用的，然而这种假设在实践中可能不现实。在生产过程中，由于对机器的预防性维修或机器突然出现故障都会导致机器在某一段时间内不能使用，有时候我们也把机器不能使用的这一段时间叫做这台机器的禁用区间，所以我们有必要把这些因素考虑到排序问题中去，再做出合理的决策非交叉维修时间指的是对于m台平行机（Parallel identical machines）的集合M={[Mi|i=1，2，…m}来说，每一台机器Mi上有一个维修时间段[ai，bi)，且0≤ai＜bi，i=1，2，…m，并且这m个维修时间段满足或者完全重合或者完全分离，也就是说；或者满足ai=a，bi=b，a，b是常数，i=1，2，…m；或者满足ai+1≥bi，i=1，2，…m-1．在本文的讨论中，对于前者我们还假定b-a≤Pmax，对于后者我们假定ai+1-bi≥Pmax，i=1，2，…m-1，其中Pmax是工件集中工件的最大加工时间。前者所述我们用D1={[ai，bi)|0≤ai＜bi，ai=a，bi=b，b-a≤Pmax，i=1，2，…m}来表示，后者所述用D2={[ai，bi)|0≤ai＜bi，ai+1-bi≥Pmax，i=1，2，…m-1)来表示。所谓在线指的是工件集是按照某个顺序到达的，是什么顺序我们事先不知道，工件的所有性质在它到来之前是未知的，工件在到来之前不能被安排加工。只有当工件Jj-1。已经被安排好之后工件Jj才到达，否则，工件Jj不出现，并且工件Jj一出现就要立即被安排到某台机器上加工，一旦被安排就不能再改变。在这种类型的排序问题中，又可分为两种情形来考虑：一种是中断后可继续加工的情形，比如说在某个时刻某台机器上有某个工件正在加工还没有完工，而这台机器在这个时刻需要进行维修，那么在这一时刻可以中断正在加工的这个工件，等到这台机器维修完之后，再接着加工被中断的工件剩余的部分。一种是中断后不可继续加工的情形，也就是说；对于上面的情形而言，被中断的工件在机器维修完之后必须被重新开始加工，相当于前面被加工的部分作废．这两种情形在排序模型中我们分别用符号r-a（Resumable availability）和nr-a（Nonresumable availability）来表示，这是借文献[1]的用法。在上述情况下，我们的任务是找一个把所有工件安排到机器集上之后使得我们所要的某个目标函数值达到尽可能优的方案，用排序论的语言来说也就是找一个尽可能好的算法。在这篇文章里，我们主要对m=2和3的情形进行了讨论，我们研究的问题的模型用三参数可表示为P2|on-line-list；r-a；D1|CmaxP2|on-line-list；nr-a；D1|CmaxP2|on-line-list；nr-a；D2|CmaxP3|on-line-list；nr-a；D1|Cmax本文的主要结果是对问题P2|on-line-list；r-a；D1|Cmax，找到了一个竞争比是2的最好的算法并给出了证明。对问题P2|on-line-list；nr-a；D1|Cmax，我们将证明此排序问题的任意在线算法的下界不小于2.79，并给出一个竞争比不大于2.8的在线算法。对问题P2|on-line-list；nr-a；D2|Cmax，我们将证明此排序问题的任意在线算法的下界不小于1.99，并证明了LS算法的竞争比不大于2．对于m=3的情形，即对问题P3|on-line-list；nr-a；D1|Cmax，我们将证明此排序问题的任意在线算法的下界不小于3-ε，并给了一个竞争比不大于10／3的在线算法。

全文目录


摘要  4-6
Abstract  6-9
第一章 引论  9-15
  1.1 排序论介绍  9-11
  1.2 排序的记号  11-13
  1.3 本文主要结果  13-15
第二章 具有重合维修时间的平行机在线排序问题  15-30
  2.1 模型介绍  15
  2.2 可中断的两台平行机在线排序  15-18
  2.3 不可中断的两台平行机在线排序  18-26
  2.4 不可中断的三台平行机在线排序  26-30
第三章 具有分离维修时间的平行机在线排序问题  30-32
  3.1 模型的描述  30
  3.2 不可中断的两台平行机在线排序  30-32
后记  32-33
参考文献  33-35
致谢  35

相似论文

  1. 机器带中断的若干延误问题研究,O223
  2. 带参数的平行机和流水作业排序问题的复杂性及算法研究,O223
  3. 工件可拒绝的在线排序问题的两个模型,O223
  4. 工件带有优先约束的平行机在线排序问题,O223
  5. 部分机器分批的平行机在线排序,O223
  6. 等长工件序约束下分批在线排序,O223
  7. 链组约束下的平行机排序问题,O223
  8. 链组约束下的平行机在线排序,O223
  9. 两类特殊的在线分批排序问题,O223
  10. 机器有准备时间的平行机半在线排序,O223
  11. 两类加权幂和形式的分批排序问题,O223
  12. 有服务等级约束的平行机排序问题,O223
  13. 带有运输时间的在线排序问题,O223
  14. 带有不可相容工件组的在线排序问题,O223
  15. 具有前瞻区间的分批在线排序问题,O223
  16. 批容量有界的单机分批列表在线排序,O223
  17. 可自由离线批处理机最小化加权完工时间和排序,O223
  18. 单机在线继列分批排序与离线混合分批排序,O223
  19. 单模光纤的光正交频分复用系统传输性能研究,TN929.11
  20. 成组加工排序和供应链在线排序问题,O223
  21. OFDM系统中信道估计的研究,TN919.3

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