一致平行機(jī)上工件有到達(dá)時(shí)間的在線算法性能分析.pdf

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

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

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