機器有準(zhǔn)備時間的平行機半在線排序.pdf

1、排序問題是運籌學(xué)與組合優(yōu)化領(lǐng)域中的一類重要問題.對排序理論的研究具有重要的理論意義和廣闊的實際應(yīng)用前景.數(shù)十年來,人們對此專題進行了深入地研究,并提出了大量的模型和優(yōu)秀的算法.在排序論的大部分文獻中,排序問題分為離線和在線排序兩種.所謂“離線”是指所有工件的信息都事先已知.而“在線”是指事先不知道工件的信息,工件的信息是逐個釋放的.工件只有在到達后才知道它的信息.在決定當(dāng)前工件的加工時,對其后面到達的工件的信息是一無所知的,并且工件一旦

2、分給某臺機器加工就不允許改變.隨著排序理論和應(yīng)用的發(fā)展,上面的分類已不足以包含所有的排序問題.大量問題的情況往往介于兩者之間.從而“半在線”模型由于其在實踐中的廣泛應(yīng)用引起了大家的重視.所謂“半在線”即所知道的工件信息介于離線和在線之間.或者說在半在線模型中人們知道未來工件的部分信息,但仍然要求工件一旦分給某臺機器加工就不允許改變.人們試圖利用某些部分信息設(shè)計出比已有最好在線算法更好的算法.
　　本文研究的模型是帶有機器準(zhǔn)備時間的

3、兩臺恒同平行機半在線排序問題.用三參數(shù)表示為,P2,ri|sum&decr|Cmax.也就是說,有兩臺恒同機且機器具有準(zhǔn)備時間.已知所有工件的加工時間總和(sum)并且工件按加工時間遞減順序(decr)在線到達.目標(biāo)為極小化最大完工時間(makespan).在第一章中,我們主要向大家介紹了排序問題的一些基礎(chǔ)知識和相關(guān)的文獻.在第二章中,我們研究了P2,ri|sum&decr|Cmax(M)和P2,ri|sum&decr|Cmax(J).