時(shí)間可變的產(chǎn)品生產(chǎn)與配送調(diào)度研究.pdf

1、隨著信息技術(shù)的飛速發(fā)展，顧客對產(chǎn)品生產(chǎn)與配送的時(shí)效性要求也越來越高，未及時(shí)送達(dá)顧客的產(chǎn)品往往導(dǎo)致顧客索賠或商家信譽(yù)損失。為了應(yīng)對產(chǎn)品生產(chǎn)與配送時(shí)效的需求，廠商會根據(jù)較方便獲得的越來越豐富的生產(chǎn)與配送運(yùn)作信息，制定產(chǎn)品生產(chǎn)與配送的最優(yōu)調(diào)度順序。由于受工作人員及機(jī)器等的學(xué)習(xí)效應(yīng)/老化效應(yīng)影響，產(chǎn)品在實(shí)際生產(chǎn)或配送中的處理時(shí)間往往會隨其所在調(diào)度處理的序列位置變化而變化，這種變化顯然會影響廠商的產(chǎn)品運(yùn)作調(diào)度的效益與效率。考慮產(chǎn)品生產(chǎn)與配送任務(wù)處

2、理時(shí)間可變性的調(diào)度研究近年才剛剛興起，系統(tǒng)分析產(chǎn)品處理時(shí)間可變影響下考慮機(jī)器維護(hù)、兩個(gè)代理以及產(chǎn)品分組等具體調(diào)度的成果甚少。為此，本文在產(chǎn)品處理時(shí)間可變影響情形下，分別針對機(jī)器維護(hù)、兩個(gè)代理以及產(chǎn)品分組加工以及產(chǎn)品生產(chǎn)與配送集成下的調(diào)度問題進(jìn)行深入研究，建立相應(yīng)的調(diào)度模型，設(shè)計(jì)確定最優(yōu)調(diào)度方案的求解算法。
　　首先，研究任務(wù)處理時(shí)間可變的帶有機(jī)器維護(hù)情形下的生產(chǎn)調(diào)度。在最小化任務(wù)處理時(shí)間表長、最小化完工時(shí)間總和以及最小化調(diào)度總代價(jià)

3、等目標(biāo)要求下，分別建立考慮一般性函數(shù)形式的任務(wù)處理時(shí)間影響及機(jī)器計(jì)件維護(hù)的單機(jī)調(diào)度模型，研究給出確定相應(yīng)最優(yōu)調(diào)度方案的求解算法，并分析得到求解算法的計(jì)算復(fù)雜度均為O(N4）。在任務(wù)的實(shí)際處理時(shí)間可以表示為基本處理時(shí)間函數(shù)和排序位置函數(shù)乘積的特殊情形下，運(yùn)用改進(jìn)的LPT算法求得最優(yōu)的調(diào)度方案，證明了求解算法的計(jì)算復(fù)雜度為O(n2 logn)。
　　第二，研究任務(wù)處理時(shí)間可變的兩個(gè)協(xié)同代理情形下的生產(chǎn)調(diào)度。先在最小化處理時(shí)間表長的多項(xiàng)

4、式目標(biāo)函數(shù)的目標(biāo)要求下，建立不考慮計(jì)件維護(hù)的兩個(gè)協(xié)同代理的單機(jī)調(diào)度模型，給出了確定最優(yōu)調(diào)度方案的多項(xiàng)式時(shí)間算法，并分析得到算法的計(jì)算復(fù)雜度。接著在最小化處理時(shí)間表長的多項(xiàng)式目標(biāo)函數(shù)的要求下，建立考慮計(jì)件維護(hù)的兩個(gè)協(xié)同代理的單機(jī)調(diào)度模型，也給出了求得最優(yōu)調(diào)度方案的多項(xiàng)式時(shí)間算法及其計(jì)算復(fù)雜度。
　　第三，研究任務(wù)處理時(shí)間可變的考慮機(jī)器固定周期維護(hù)的生產(chǎn)調(diào)度。先在最小化處理時(shí)間表長的目標(biāo)要求下，建立機(jī)器周期維護(hù)的單機(jī)調(diào)度模型，并給出求

5、得近似最優(yōu)調(diào)度方案的多項(xiàng)式近似算法，分別得到算法的最壞情況比、計(jì)算復(fù)雜度、以及表現(xiàn)界。接著針對機(jī)器周期維護(hù)的單機(jī)調(diào)度模型，給出求得近似最優(yōu)調(diào)度方案的混合進(jìn)化算法，并通過算例驗(yàn)證給出的進(jìn)化算法能高效地求得近似最優(yōu)的調(diào)度方案。
　　第四，研究考慮任務(wù)處理時(shí)間可變影響和任務(wù)分組技術(shù)的生產(chǎn)調(diào)度。先在最小化處理時(shí)間表長要求下，分別建立考慮一般性處理時(shí)間可變影響的單機(jī)分組調(diào)度模型，給出了求得最優(yōu)單機(jī)器分組調(diào)度方案的求解算法，并證明了求解算法的

6、計(jì)算復(fù)雜度均為O（n3）。接著在最小化處理時(shí)間表長要求下，基于任務(wù)實(shí)際處理時(shí)間以及任務(wù)分組準(zhǔn)備時(shí)間都可以表示為基本處理時(shí)間函數(shù)和排序位置函數(shù)乘積的特殊處理時(shí)間可變影響，建立相應(yīng)的單機(jī)器分組調(diào)度模型，分析得到可運(yùn)用LPT算法得到最優(yōu)的單機(jī)分組調(diào)度方案，并證明了算法的計(jì)算復(fù)雜度為O(nlogn)。最后在最小化機(jī)器總負(fù)荷的要求下，建立考慮一般性處理時(shí)間可變影響的平行機(jī)分組調(diào)度模型，并給出了求得最優(yōu)平行機(jī)分組調(diào)度方案的求解算法，并證明了求解算法

7、的計(jì)算復(fù)雜度為O(n3)。
　　第五，研究老化影響的單個(gè)顧客的產(chǎn)品生產(chǎn)與配送集成調(diào)度。先在最小化處理時(shí)間表長要求下，建立了老化影響下生產(chǎn)調(diào)度模型，并運(yùn)用LPT算法求得最優(yōu)單機(jī)生產(chǎn)調(diào)度方案，分析得出算法的計(jì)算復(fù)雜度均為O(nlogn)。接著然后在最小化配送任務(wù)完成時(shí)間的要求下，建立老化影響的生產(chǎn)與配送集成調(diào)度和式模型以及乘式模型，分別依據(jù)求解最優(yōu)生產(chǎn)調(diào)度所得到的結(jié)論給出和式模型及乘式模型的多項(xiàng)式最優(yōu)求解算法，并分析得到算法的計(jì)算復(fù)雜

8、度也為O(nlogn)。
　　第六，研究任務(wù)處理時(shí)間可變的多個(gè)顧客的生產(chǎn)與配送集成調(diào)度。先在最小化配送任務(wù)完成時(shí)間的目標(biāo)要求下，建立任務(wù)處理時(shí)間可變的單臺生產(chǎn)機(jī)器多個(gè)顧客的生產(chǎn)與配送集成調(diào)度模型，并結(jié)合生產(chǎn)調(diào)度的求解算法結(jié)論和獨(dú)立即時(shí)配送模式的性質(zhì)，分析給出求得最優(yōu)調(diào)度方案的多項(xiàng)式時(shí)間算法。然后在最小化配送任務(wù)完成時(shí)間的目標(biāo)要求下，建立多臺生產(chǎn)機(jī)器多個(gè)顧客的生產(chǎn)與配送集成調(diào)度模型，并分析給出求得近似最優(yōu)的調(diào)度方案的多層代碼的遺傳進(jìn)