帶激活費(fèi)用的平行機(jī)排序問(wèn)題研究.pdf

1、本文比較系統(tǒng)深入地研究帶機(jī)器激活費(fèi)用的平行機(jī)(半)在線排序問(wèn)題的近似算法設(shè)計(jì)與競(jìng)爭(zhēng)比分析.對(duì)多個(gè)不同機(jī)器環(huán)境下的(半)在線問(wèn)題，討論了這些問(wèn)題的下界，設(shè)計(jì)了相應(yīng)的近似算法并給出了它們的競(jìng)爭(zhēng)比.所謂帶機(jī)器激活費(fèi)用的平行機(jī)(半)在線排序問(wèn)題是指有一些機(jī)器已經(jīng)提供，但使用這些機(jī)器需要激活，并需要激活費(fèi)用.當(dāng)一個(gè)工件到達(dá)后，算法必須作出選擇是激活一臺(tái)新的機(jī)器加工該工件還是將其放在已激活的機(jī)器上加工.目標(biāo)函數(shù)是極小化最大完工時(shí)間(makespan

2、)和所有機(jī)器的激活費(fèi)用之和.帶機(jī)器激活費(fèi)用的排序問(wèn)題和實(shí)際問(wèn)題的關(guān)系較為緊密，對(duì)實(shí)際問(wèn)題的刻畫(huà)也更深刻，同時(shí)這些問(wèn)題有著重要的理論意義. 全文共分為六章，前兩章主要介紹了與組合優(yōu)化、排序問(wèn)題相關(guān)的一些概念及預(yù)備知識(shí)，總結(jié)了近些年在(半)在線領(lǐng)域研究中取得的成果. 第三章研究了帶機(jī)器激活費(fèi)用的同型機(jī)在線排序問(wèn)題，給出了此問(wèn)題的下界，并分別設(shè)計(jì)了有2臺(tái)、3臺(tái)同型機(jī)可供激活時(shí)的最優(yōu)在線算法，其競(jìng)爭(zhēng)比分別為3/2和5/3.對(duì)于一

3、般情形(有4臺(tái)或以上同型機(jī)可供激活)，設(shè)計(jì)了一個(gè)競(jìng)爭(zhēng)比為2的在線算法，而相應(yīng)問(wèn)題的下界為1.88. 第四章研究了帶機(jī)器激活費(fèi)用的同類(lèi)機(jī)排序問(wèn)題，主要考慮了速度比為1∶s的兩臺(tái)同類(lèi)機(jī)的情形，證明問(wèn)題關(guān)于s的參數(shù)下界為2s+1/s+1，并設(shè)計(jì)了關(guān)于速度比的參數(shù)競(jìng)爭(zhēng)比為2s+1/s+1的最優(yōu)在線算法. 論文的最后部分研究了兩種帶機(jī)器激活費(fèi)用的同型機(jī)半在線排序問(wèn)題，一個(gè)問(wèn)題是待加工工件長(zhǎng)度總和已知的半在線問(wèn)題，另一個(gè)是待加工工件