集裝箱調(diào)度問題的平等機(jī)排序算法研究.pdf

1、本文以現(xiàn)代物流業(yè)中港口集裝箱的裝卸調(diào)度作業(yè)問題為背景,通過抽象和簡(jiǎn)化將其等價(jià)轉(zhuǎn)化為平行機(jī)排序理論中的最早完工時(shí)間問題,提出了三種近似算法并分析了各近似算法的時(shí)間復(fù)雜性以及各自的適用條件,對(duì)近似算法性能的分析主要采用了學(xué)術(shù)界常見的最差情形下的“競(jìng)爭(zhēng)比分析”來衡量各近似算法所求得的近似解和最優(yōu)解之間的關(guān)系,本文的主要研究成果及貢獻(xiàn)如下:
　　1,針對(duì)可組合型集裝箱裝卸調(diào)度問題提出了近似算法APA,并證明了近似算法APA的競(jìng)爭(zhēng)比為4/3

2、-1/3k(K≥2),其時(shí)間復(fù)雜性為O(n3+nlogn),該算法的局限性在于當(dāng)K≥t+1時(shí)顯然可以通過拆分的方法對(duì)近似解作進(jìn)一步的優(yōu)化。
　　2,在近似算法APA的基礎(chǔ)上,通過拆分優(yōu)化的方法提出了近似算法APB,其時(shí)間復(fù)雜性為O(n3+nlogn+K),并證明了在任一情況下近似算法APB的解均不差于近似算法APA的解,即CmaxAPB≤CmaxAPA;特別地當(dāng)K≥t+1時(shí),近似算法APB能夠?qū)⒔飧倪M(jìn)至CmaxAPB＜CmaxAP

3、A,且二者近似解的比值下界K/2k-1(K≥2)隨著車輛數(shù)K的增大而減小;然而由于對(duì)任意的K≥2在最差情形下近似算法APB無法作進(jìn)一步的優(yōu)化改進(jìn),因而對(duì)任意的K≥2近似算法APB的競(jìng)爭(zhēng)比為詈4/3-1/3K(K≥2)。
　　3,針對(duì)一類特殊情形分析了近似算法APB對(duì)競(jìng)爭(zhēng)比的具體改進(jìn),即τ≥1且K≥5時(shí),近似算法APB有效地將競(jìng)爭(zhēng)比改進(jìn)至{K/K-1(1≤λ≤3/2),4/3-1/3K(λ＞3/2)}。
　　4,針對(duì)可拆分型集

4、裝箱調(diào)度問題將其轉(zhuǎn)化為Pm|setup&splitting|Cmax,通過改進(jìn)近似算法LSU的拆分規(guī)則提出了近似算法Apc,其時(shí)間復(fù)雜性為O((n+K)log(n+K)),并證明了在任意情形下近似算法Apc的解均優(yōu)于近似算法LSU的近似解,具體的將競(jìng)爭(zhēng)比改進(jìn)至max{3/2-1/2K,5K-3/3K+2-4/K}。
　　本文所提出的各近似算法均能在多項(xiàng)式時(shí)間內(nèi)求得和最優(yōu)解較為接近的近似算,能夠有效響應(yīng)客戶的實(shí)時(shí)需求,因而具有較好的