一致平行機上工件有到達時間的在線算法性能分析.pdf

1、本文主要分為兩個部分，我們對一類一致平行機上工件有非遞減和任意到達時間兩種情況下的在線算法分別進行了性能比分析。
　　第一部分:Cho和Sahni(1980)首次提出了m臺一致平行機的在線算法問題，對于Qm/online/Cmax(m≥2)，他們證明出LS算法的最壞性能比不會大于1+√m-1/√2。當si=1(i=1，2，…，…，m-1)并且sm=s＞1時，他們證明了LS算法的最壞性能比1+m-1/m+s-1min{s，2}≤3-

2、4/m+1并且當s=2(m≥3)時，能夠取到3-4/m+1。
　　對于Qm/online/Cmax，Aspnes et al.(1997)第一個設(shè)計了一個比LS算法更好的算法，他們提出新算法在確定的情況下最壞性能比能達到8，在隨機情況下能達到5.436。隨后，Berman et al.(2000)將上述兩個性能比分別降低到了5.828和4.311。
　　本文在Berman的基礎(chǔ)上，加入了到達時間非遞減即r1≤r2≤…≤rn這

3、一約束，與Berman的模型中到達時間為零這一模型相比，本章的模型更為復(fù)雜，分析過程要考慮的因素也更多，從而得到該模型在LS算法下其最壞性能比為R(m，U)=sup L CUmax(L)/COPT/max(L)＜5.8284
　　第二部分:在第一部分的基礎(chǔ)上，進一步放松到達時間的條件，工件具有任意到達時間，與之前的模型相比，本模型更為復(fù)雜，分析的過程要素也更多，并證明了對于任意滿足條件的工件序列L，在U算法的最壞性能比為R(m，U