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

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

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

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