帶激活費用的平行機排序問題研究.pdf

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

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

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