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

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

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

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

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

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

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

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

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