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

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

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

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

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