兩類(lèi)半在線排序模型的算法性能分析.pdf

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

2、時(shí)長(zhǎng)pj∈[1，r](r≥1)的基礎(chǔ)上，加入了到達(dá)時(shí)間非遞減即r1≤r2≤…≤rn這一約束，與([12])的到達(dá)時(shí)間為零這一模型相比，本章的模型更為復(fù)雜，分析過(guò)程要考慮的因素也更多，從而得到該模型在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這是一個(gè)緊界，并且LS算法是解決此模型的最好的

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

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