工件允許重啟的平行分批在線排序研究

工件允許重啟的平行分批在線排序研究排序論是運(yùn)籌學(xué)與組合最優(yōu)化的重要分支.分批排序是人們十分關(guān)注的現(xiàn)代排序模型;其特點(diǎn)是可將工件分批進(jìn)行加工,每一批工件具有相同的開工時(shí)間和相同的完工時(shí)間.在本文研究的平行分批排序模型中,每一批的加工時(shí)間等于該批中工件的最長加工時(shí)間.按照每一批可以加工的工件數(shù)目b的限制(稱為批容量),平行分批排序又可分為批容量有限(b<∞)和批容量無限(b=∞)兩種情形.在線排序問題是近年來排序論研究的熱點(diǎn)方向;其特點(diǎn)是工件的信息事先并不確定,決策者在沒有獲得所有工件信息之前就必須對(duì)已有工件進(jìn)行排序.本文所研究的在線排序是工件實(shí)時(shí)到達(dá)(overtime)的情形,即工件是隨著時(shí)間逐漸到達(dá)的.工件的所有信息在其到達(dá)時(shí)刻才能獲知.針對(duì)在線優(yōu)化問題設(shè)計(jì)的算法稱為在線算法.人們常用競(jìng)爭(zhēng)比來衡量在線算法性能的好壞.對(duì)于一個(gè)極小化目標(biāo)函數(shù)的優(yōu)化問題,我們稱一個(gè)在線算法是ρ-競(jìng)爭(zhēng)的,如果對(duì)于該問題的任意實(shí)例,算法所產(chǎn)生的目標(biāo)函數(shù)值不大于最優(yōu)離線算法所產(chǎn)生的目標(biāo)函數(shù)值的ρ倍.在線算法A的競(jìng)爭(zhēng)比定義為ρA=inf{ρ:A是ρ-競(jìng)爭(zhēng)的}.不難看出,ρA總是大于等于1的.由于信息的缺乏,ρA=1的情形只有在很特殊的問題上才會(huì)出現(xiàn).一般而言,ρA越是接近于1,在線算法A的性能越好.如果不存在競(jìng)爭(zhēng)比小于ρA的其他在線算法,就稱算法A是該問題的最好可能的的在線算法.為了得到性能更好的在線算法,人們常常允許工件重啟.這里的“重啟”指的是:我們可以中斷正在加工的工件或工件批,中斷加工的工件被重新釋放出來(以前的加工作廢)再重新安排加工.允許工件重啟給了我們糾正錯(cuò)誤的機(jī)會(huì),但重啟次數(shù)過多很容易造成資源的浪費(fèi)和工件的損壞.因此,在線算法的設(shè)計(jì)中,有限重啟也是人們采用的策略.本文中,有限重啟指的是:每個(gè)工件最多只能重啟一次,相應(yīng)地,如果一個(gè)正在加工的批里面包含有被中斷重啟過的工件,這個(gè)批就不能被中斷了.本學(xué)位論文研究工件允許重啟或有限重啟的在線平行分批排序問題.對(duì)所研究的四個(gè)在線排序問題,均給出了最好可能的在線算法.學(xué)位論文的結(jié)構(gòu)如下.第一章介紹了排序論中的基本概念,常用符號(hào)和相關(guān)的研究進(jìn)展.第二章研究了等長工件在m臺(tái)容量無限的平行批處理機(jī)上加工,工件允許有限重啟,目標(biāo)函數(shù)是最小化最大完工時(shí)間的在線排序問題.對(duì)于該問題我們?cè)O(shè)計(jì)出了一個(gè)競(jìng)爭(zhēng)比為1+αm的最好可能的在線算法.不同于已有文獻(xiàn)中的競(jìng)爭(zhēng)比的顯式表達(dá)式,這里的1+αm是由一個(gè)算法確定的.第三章研究了等長工件在一臺(tái)容量有限的平行批處理機(jī)上加工,工件允許有限重啟,目標(biāo)函數(shù)是最小化最大完工時(shí)間的在線排序問題.令α是方程(1+x)(2x~2+4x+1)=3的正根.β是方程x(1+x)~2=1的正根.當(dāng)批容量為2時(shí),我們給出了一個(gè)競(jìng)爭(zhēng)比為(1+α)的最好可能的在線算法.當(dāng)批容量大于等于3時(shí),我們給出了一個(gè)競(jìng)爭(zhēng)比為(1+β)的最好可能的在線算法.第四章研究了等長工件在一臺(tái)容量有限的平行批處理機(jī)上加工,工件允許重啟,目標(biāo)函數(shù)是最小化最大完工時(shí)間的在線排序問題.令γ是方程x(x+1)(2x+3)=2的正根.?是方程x(x+1)(2x+1)=1的正根.當(dāng)批容量為2時(shí),我們證明了第三章中允許有限重啟時(shí)批容量為2的情形的最好可能的在線算法也是允許重啟時(shí)的最好可能的在線算法.當(dāng)批容量為3時(shí),我們給出了一個(gè)競(jìng)爭(zhēng)比為(1+γ)的最好可能的在線算法.當(dāng)批容量大于等于4時(shí),我們給出了一個(gè)競(jìng)爭(zhēng)比為(1+?)的最好可能的在線算法.第五章研究了等長工件在一臺(tái)容量有限的平行批處理機(jī)上加工,工件允許有限重啟且目標(biāo)函數(shù)是最小化最大運(yùn)輸完工時(shí)間的在線排序問題.令α是方程2x(1+x)=1的正根.β是方程x(1+x)~