论文部分内容阅读
本文主要研究了Ip范数下两台同类机的几种半在线排序问题。该类问题可以描述为:给定两台同类机(两台机器速度不同但恒定)和一个按列表到达的工件序列,每个到达的工件必须实时的分配给两台同类机中的一个,且只有在当前工件被分配后后续工件才会到达。目标是极小化机器负载的Ip范数。
在对排序理论进行了简短介绍后,我们在第二章研究了已知最大工件加工时长信息的半在线排序问题。我们给出了该问题的一个在线算法,证明了该算法的竞争比不超过CA≤max{α,β},其中α=p((√)1+s-p/2pγ);β=p((√)1/γ(s+1)p+1/(2s+1)p);γ=(s/1+s)p+(1/1+s)ps-p;s=s-p/p-1.
第三章主要研究了预知所有工件加工时长总和信息的两台同类机的半在线排序问题。本文给出了该模型的半在线算法并证明了该半在线算法的竞争比不超过CA≤max{α,β}其中α=1/s p((√)1/γ);β=1+s/2 p((√)1+1+sp/(ss)p+1)γ=(s/1+s)p+(1/1+s)ps-p;s=s-p/p-1.
第四章主要研究了已知最大工件加工时长和所有工件加工时长总和信息的复合半在线排序问题。我们给出了该问题的半在线算法并证明了该算法的竞争比不超过CA≤max{α,β}≤2其中α=1/2 p((√)1+(2+s)p-(1+s)p/(ss)p+1);β=1+s/2 p((√)1+1+sp/(ss)p+1);s=s-p/p-1
最后,对我们的工作进行了总结,分析了本文工作的不足和进一步研究的展望。