兩類半在線排序模型的算法性能分析.pdf

1、本文主要分為兩部分內(nèi)容，分別對兩類半在線模型的算法性能比進行了分析。
　　第一部分:He and Zhang在1999([12])年提出了一個半在線的排序模型:對任意的工件序列L={J1，J2,…，Jn}，工件具有相似的加工時長pj∈[1，r](r≥1）。將這些工件安排在兩臺平行機上。得到對任意滿足該模型的實例L在LS算法下的最壞性能比為R(2,LS,r)={1+r/21≤r≤23/2r≥2。
　　本文在其工件具有相似的加工

2、時長pj∈[1，r](r≥1)的基礎(chǔ)上，加入了到達時間非遞減即r1≤r2≤…≤rn這一約束，與([12])的到達時間為零這一模型相比，本章的模型更為復(fù)雜，分析過程要考慮的因素也更多，從而得到該模型在LS算法下其最壞性能比為R(2，LS，r)={k+3/k+2k+2/k+1≤r＜1+k+1/k(k+2),k∈Z+kr+1/k+11+k+1/k(k+2)≤ r＜k+1/k,k∈Z+3/2 r≥2這是一個緊界，并且LS算法是解決此模型的最好的

3、近似算法。這一部分內(nèi)容將在第二章展開詳細證明。
　　第二部分:Wei-Ping Liu，Jeffrey B.Sidney，Andre van Vliet在1996([24])年給出了一個模型:工件到達時間都為零，且加工時長非遞增。并給出了解決這一模型的算法Pm算法(在本文中暫稱為Pm算法，與([24])中的稱呼保持一致）且證明了對任意滿足該模型的實例L在Pm算法下的性能比為R(m，Pm)=sup L CPm max(L)/COPT

4、 max(L)≤1+m-1/m+[m/2]。
　　本文在其模型的基礎(chǔ)上，增加了一個約束條件，即當工件的到達時間不都為零且滿足非遞減（即r1≤r2≤…≤rn）。并證明了對于任意滿足條件的工件序列L，在Pm算法的最壞性能比為R(m，Pm)=sup L CPm max(L)/COPT max(L)≤2+m-1/m+[m/2]雖然單看性能比數(shù)值比之前要大，但是本章的模型是([24])的一個推廣，模型更為復(fù)雜，應(yīng)用的范圍也更加廣泛。這一部分