鏈組約束下的平行機(jī)在線排序.pdf

1、在經(jīng)典的排序問題中,總是假設(shè)工件信息在排序之初都已經(jīng)全部知道。在實際應(yīng)用中,工件的信息在一開始往往是不知道的,而是隨著時間的推移而逐個到達(dá)。這就是我們在此文中所要研究的按時在線(on-line-over-time)排序問題。
　　本文研究一類鏈組約束下的平行機(jī)在線排序問題,目標(biāo)是最小化最大完工時間。這里工件的加工時間相同,工件之間的序約束關(guān)系是平行鏈,工件鏈一旦到達(dá),該鏈上所有工件的信息才可知,已到達(dá)工件按照序約束關(guān)系在兩臺恒同機(jī)

2、上加工。該問題用三參數(shù)法表示為P2|pj=p,chainsi released at ri|Cmax。Huo和Leung在《SIAM J.Comput》(2005)上發(fā)表的文章中給出了此問題的一個(16)/(15)的下界,并由此得出結(jié)論:該問題不存在能達(dá)到離線最優(yōu)的在線算法。在本文中,我們首先利用對手法構(gòu)造一組實例證明了該問題有一個更好的下界1+α(α=((13)1/2-3)/2)≈1.3028。接著提供了一個最好可能的在線算法。該結(jié)論