• 主题
高级搜索  >
历史搜索 清空历史
首页> 中文学位 >单机在线继列分批排序与离线混合分批排序
【6h】

单机在线继列分批排序与离线混合分批排序

代理获取
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

本文研究单机上的在线继列分批和离线混合分批排序.在线继列分批排序中,一个工件的信息只有当它到达后才被释放出来.一台批处理机可以同时将多个工件作为一个继列批进行加工,每个工件都有它自己的安装时间,批的加工时间为这一批里的所有工件的加工时间之和,批安装时间为这一批里工件的最大的安装时间,目标是最小化时间表长.利用排序问题的三参数表示法,该问题可表示为1｜s-batch,on-line,b=+∞,ri≤rj→si≥sj｜Cmax.
　　 混合分批排序中,我们有两组工件JA和JB,分别称为A工件和B工件.这两组工件要在同一台可以对工件进行分批的机器上进行排序.但是,A工件和B工件不能放在同一批内进行加工.此外,A工件批为平行批,容量为b(A)；B工件批为继列批,容量为6(B),安装时间为s(B).利用排序问题的三参数表示法,该问题可表示为1｜s—p-batch,s(B),(b(A),b(B))｜γ.其中,γ∈{Cmax,Lmax,∑Gj,∑wjCj,fmax).
　　 本文的主要内容如下:
　　 第一章介绍了排序问题的背景和本文所研究问题的相关发展,并给出了相关排序问题的术语和记号.
　　 第二章研究在线继列分批排序,给出排序问题1｜s-batch,on-line,b=+∞,ri≤rj→si≥sj｜Cmax的一个最好可能的在线算法,其竞争比为(√5+1)／2.
　　 第三章研究单机两组工件继列分批与平行分批混合排序.主要结果如下:
　　 ·排序问题1｜s-p-batch,s(B),(∞,∞)｜Lmax在O(nAnBn)时间可解.
　　 ·排序问题1｜s-p-batch,s(B),(∞,b(B))｜∑Cj在O(nAnBn)时间可解.
　　 ·排序问题1｜s-p-batch,pj=1,s(B),(b(A),b(B))｜∑wjCj在O(nAnBn)时间可解.
　　 ·排序问题1｜s-p-batch,s(B),(∞,b(B))｜fmax可以在时间界为O(log(maxj fj(M))×(nlog M+nAnBn))内可解.其中,M是工件完工时间的一个上界.
　　 文章最后总结了全文内容并提出了下一步需要做的问题.

著录项

相似文献

  • 中文文献
  • 外文文献
  • 专利
代理获取

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号