可中斷平行機(jī)排序問題研究.pdf

1、本文主要研究可中斷平行機(jī)(半)在線排序問題的近似算法設(shè)計(jì)及其競爭比分析．對多個不同機(jī)器環(huán)境和目標(biāo)函數(shù)下的可中斷(半)在線問題以及兩個新排序模型，本文討論了這些問題的下界，設(shè)計(jì)了相應(yīng)的近似算法并給出了它們的競爭比． 全文共分為七章，第一章首先介紹了與排序問題相關(guān)的一些概念以及預(yù)備知識，并總結(jié)了近些年在半在線領(lǐng)域研究中取得的成果． 第二章研究可中斷的機(jī)器覆蓋問題(P(Q)|pmpt|C<,min>).對m臺同類機(jī)的離線情形，

2、文中證明了能在O(mn)時間內(nèi)找到最優(yōu)解．隨后研究了在線機(jī)器覆蓋問題的下界，給出了一個求解這類問題下界的一般公式并由此得出了問題Qm|pmpt|C<,min>)和Pm|pmpt|C<,min>)的下界分別為m和∑<'m><,i=1> 1/i．最后，文章還研究了兩臺同類機(jī)的在線算法并分別給出了在不允許機(jī)器空閑與允許機(jī)器空情況下的最優(yōu)在線算法． 第三章研究已知工件加工時間位于某一區(qū)間的可中斷半在線排序問題．文中分別給出了問題．P3|

3、pmpt，group|Cmax、Q2|prapt，group|C<,max>和Q2|pmpt，group|C<,min>的最優(yōu)可中斷參數(shù)界算法． 第四章研究了兩臺同類機(jī)上已知工件按非增序到達(dá)和已知最大工件長度這兩個可中斷半在線排序問題．文中分別給出了Q2|pmpt，decr|C<,min>、Q2|pmpt，max|C<,max<和Q2|pmpt，max|C<,min>．的最優(yōu)可中斷算法． 第五章研究帶不確定信息的可中斷半

4、在線排序問題．文章分別給出了Pm|pmpt，dist opt|C<,max>、Q2|pmpt，dist opt|C<,max>和Q2|pmpt，dist max|C<,max>的最優(yōu)可中斷算法． 第六章研究帶機(jī)器費(fèi)用的平行機(jī)可中斷(半)在線排序問題．在該問題中，一開始沒有任何機(jī)器可用，當(dāng)一個工件到達(dá)后，算法必須作出選擇是購買新機(jī)器加工該工件還是將其放在已購買的機(jī)器上加工．目標(biāo)函數(shù)是極小化makespan和所有機(jī)器的購買費(fèi)用之和．

5、文中首先給出了一個競爭比為(2<平方根6>+2)/5≈1.3798的在線可中斷算法，而該問題的下界為4/3．此外，還研究了已知工件按非增序到達(dá)的半在線情形，給出了競爭比為4/3的最優(yōu)算法，該算法無需工件被中斷，因此也是不可中斷問題的最優(yōu)算法． 第七章研究帶服務(wù)等級約束的平行機(jī)在線排序問題．該問題對每個工件和機(jī)器都賦予一個服務(wù)等級，工件只能在服務(wù)等級不高于自己的機(jī)器上加工．文中首先給出了兩臺機(jī)器上的最優(yōu)在線算法．對m臺機(jī)器帶有兩個