1、在傳統(tǒng)排序問題中,總是假設(shè)工件信息在排序之初都已經(jīng)全部知道.這些問題稱之為離線(off-line)排序問題.在實際應(yīng)用中,有些工件的信息在一開始往往是不知道的,而是隨著時間的推移而逐個釋放.這些問題稱之為在線(on-line)排序問題.本文研究帶有鏈約束chains1,chains2,…,chainsn工件的平行機(jī)排序問題.鏈的到達(dá)時間為rj,j=1,2,…,n.工件一旦開始加工,就不能被打斷,直到該工件被加工完畢。目標(biāo)函數(shù)是最小化機(jī)器

2、完工時間的平方和以及最小化最大延誤時間.本文的主要結(jié)果如下:
　　(1)研究了每一條鏈的長度都為1的離線排序問題.在0時刻,所有的工件已到達(dá).目標(biāo)函數(shù)是最小化兩臺機(jī)器的完工時間的平方和.用三參數(shù)法該問題可表示為P2||chaini|=1|.我們利用修改的LPT算法(Modified-LPTAlgorithm)求解該問題,并證明該算法的執(zhí)行比不大于1+1/81。
　　(2)研究了單位長度工件且鏈在整數(shù)時刻到達(dá)的2臺恒同機(jī)上的在

3、線排序問題.目標(biāo)函數(shù)是最小化兩臺機(jī)器的完工時間的平方和.用三參數(shù)表示為P2|pj=1,chainsi released at.證明了任一實例在任意算法下競爭比不小于5/4,而任意的稠密算法(Dense Algorithm)的競爭比都漸近地趨于2,并給出該問題的一個最好可能在線稠密算法。
　　(3)研究了等長工件在鏈約束下單機(jī)在線排序問題.每一個到達(dá)時刻ri到達(dá)的工件為一組鏈chainsi,其上面的工件Jj的加工時間pj和工期qj滿