導(dǎo)語：如何才能寫好一篇數(shù)學(xué)建模調(diào)度問題，這就需要搜集整理更多的資料和文獻(xiàn)，歡迎閱讀由公務(wù)員之家整理的十篇范文，供你借鑒。

篇1

【關(guān)鍵詞】鋁箔 加工 排產(chǎn) 優(yōu)化

鋁箔的生產(chǎn)，在工藝方面和材料的使用方面要求都比較高。需要的工藝流程復(fù)雜，要經(jīng)過焙鑄、熱軋鑄軋、冷軋、箔材軋制、分切等加工工藝和熱處理過程才能對鋁制品進(jìn)行加工，工序比較長、難度比較大。鋁箔的生產(chǎn)技術(shù)不斷的發(fā)展使我國在鋁箔方面的消費(fèi)比例不斷的提高但是鋁箔的生產(chǎn)水平還依然存在很多問題，對于加工方法還有待研究。本文對超薄鋁箔的加工動態(tài)集成排產(chǎn)方法進(jìn)行研究。

1熱軋問題的使用方法

1.1數(shù)學(xué)規(guī)劃方法

在熱軋的問題上，我們早期使用的方法是數(shù)學(xué)規(guī)劃的方法。數(shù)學(xué)規(guī)劃模型的使用是利用動態(tài)的規(guī)劃方法對離散鋼鐵企業(yè)的優(yōu)化生產(chǎn)問題進(jìn)行解決的。PVC板生產(chǎn)中的多開工時間調(diào)度問題開發(fā)出了一種TABU搜索啟發(fā)的算法，這種算法的應(yīng)用很大程度上減弱了開工時間的調(diào)度問題。分支界定算法的出現(xiàn)是對無縫鋼管的軋制進(jìn)行多階段的分批調(diào)度問題的解決。而在軋機(jī)、加熱爐、能力損耗和制造成本方面的調(diào)度目標(biāo)模塊所使用的是分支界定求解的方法。在國外，這幾種方法得到了廣泛的應(yīng)用但是應(yīng)用的時效性受到了限制。

1.2非數(shù)學(xué)規(guī)劃的方法

非數(shù)學(xué)的規(guī)劃方法可以分為兩大類，主要是啟發(fā)式方法和人工智能的方法。啟發(fā)式方法是通過對計算過程和評價指數(shù)的運(yùn)算在比較短的時間里，有意識的尋找最佳的解決方案。COWLING提出了一種決策系統(tǒng)，這種決策系統(tǒng)是以鋼鐵熱軋過程的多模型為依據(jù)，利用TSBU的算法對調(diào)度問題進(jìn)行有效的解決。熱軋調(diào)度問題的簡化是PCVRP的模型，同時提出了基于大規(guī)模鄰域定義的局部搜索方法。模擬退火算法有時候也被用于求解熱軋調(diào)度的相關(guān)問題。

1.3數(shù)學(xué)模型的建立

我國的研究者陳雄創(chuàng)造出了軋制批量計劃問題的數(shù)學(xué)模型，這種數(shù)學(xué)模型分為啟發(fā)式算法和模擬退火算法。我國在熱軋批量計算問題的約束滿意問題進(jìn)行了處理，對軋熱問題的PCTSP建模和該模蟻群的蒜放方面做出了研究。針對軋熱問題的CVRP建模還提出了混合免疫算法。

上述的這些方法都是軋制生產(chǎn)中的優(yōu)化排產(chǎn)的基本理論和方法。由于我國超薄鋁箔的生產(chǎn)不斷的發(fā)展，生產(chǎn)要求也隨之提高，在排產(chǎn)計劃和熱處理方面要使生產(chǎn)具有動態(tài)性就要根據(jù)具體實(shí)際進(jìn)行任務(wù)的不斷完善和添加，隨時對排產(chǎn)計劃進(jìn)行調(diào)整，排產(chǎn)的相關(guān)實(shí)時性要求和方法要快速的計算，增加可靠性和實(shí)用性特點(diǎn)。

2代數(shù)法建模

2.1符號函數(shù)的定義方法

I設(shè)置為鋁卷號，I=1，2...，P。J為設(shè)備的編號，J=1，2，...，M。工藝路線矩形陣R。R是n*m型矩陣，其中元素R表示鋁卷I在加工工藝路線中設(shè)備J所占的順序位。鋁卷號關(guān)系表E%表E中每行代表一個鋁卷號的屬性、各列分別表示物料編碼、爐架號、直徑、計劃開始時間、加工時間、設(shè)備編號、工藝順序號其中物料編碼、設(shè)備編號、工藝順序號、加工時間的數(shù)據(jù)來源于工藝路線矩陣和加工時間矩陣。圖1所示為爐架和鋁卷的幾何尺寸其中a、b、h分別代表爐架的長、寬、高。條件如下所示：

H=h1+h2+h3

r1>r2>....rk rk+1>rk+2>....>rk2k

上排

h1>r1 h2>r1 u1=r1 u2=r1+r2

下排

H3>rk+1 h2>rk+1

圖1.爐架和鋁卷的幾何參數(shù)

2.2第一次排序

第一次排序是對訂單池中的鋁卷進(jìn)行排序，排序按照重要的程度和緊急的程度進(jìn)行安排，優(yōu)化的準(zhǔn)則體現(xiàn)在評價指數(shù)當(dāng)中。對調(diào)度問題的NP難度性，要選擇計算量不大，計算時間不長的效果優(yōu)化好的啟發(fā)式目標(biāo)函數(shù)作為評判的標(biāo)準(zhǔn)。

兼顧能夠?qū)υO(shè)備的使用率提高、合同按照完工率和裝爐系數(shù)等進(jìn)行多樣性目標(biāo)的歸集，評價的指數(shù)可以參照鋁卷號和爐架號進(jìn)行歸類。第一次排序是對任務(wù)中的全部鋁卷進(jìn)行加工，按照從小到大的順序進(jìn)行排序。

2.3第二次排序

第二次排序是第一次排序的升級，把第一次排序截取的歸屬于統(tǒng)一最佳的鋁卷進(jìn)行內(nèi)部的排序，使呂佳能夠安裝更多的鋁卷，這樣能夠節(jié)省熱處理電費(fèi)。這種方法也被稱為爐次計劃，計劃的步驟主要體現(xiàn)在：

首先，在按照排好的序列中從前向后截取鋁卷直徑之和小于或等于2a最好接近2a的鋁卷子序列。

其次，從這種子序列中對鋁卷進(jìn)行選擇，每隔一個選取一個，按照鋁卷的直徑大小排列，排列順序是由小到大的排列順序。

最后，將該兩段鋁卷分別擺放在支架的上下兩排，對每個鋁卷的位置是否滿足約束條件進(jìn)行檢查，如果符合則排產(chǎn)成功，進(jìn)行下一步，如果沒有成功就要對兩端序列進(jìn)行保留。截取兩端子序列，在四段中選配評價指數(shù)最小的又能滿足條件的方案。然后輸出鋁卷的兩次排序方式和爐架上的擺放方式。

2.4狀態(tài)賦值

當(dāng)設(shè)備為退火爐時，設(shè)定編號為K，設(shè)備軋機(jī)時設(shè)定編號為J。這種情況下設(shè)備的變量的計算方式主要有三種，分別表示為：

首先，設(shè)備編號為軋制設(shè)備時每一個爐架的第一鋁卷開工時間為上一道熱處理時間與本輪最后一個任務(wù)完成時間的最大值。每一個爐架非第一個鋁卷軋制工序設(shè)備加工最近的鋁卷被上一道工序加工完畢是具有以下公式：

在設(shè)備J沒有加工鋁卷時，鋁卷被上一道程序加工時的公式是：

在這里i表示設(shè)備k加工的上一道鋁卷，熱處理工序的狀態(tài)時間是在當(dāng)前設(shè)備加工的前一個爐架的結(jié)束時間和當(dāng)前鋁卷時間的最大值。

3結(jié)語

綜上所述，本文從鋁卷的排產(chǎn)方法、爐架的布置以及生產(chǎn)的調(diào)度方面對超薄鋁箔的生產(chǎn)排產(chǎn)方法進(jìn)行了研究。按照訂單的需求進(jìn)行先后的排序，在同一個鋁卷在爐架上的合理排放方式進(jìn)行了分析。超薄鋁箔具有工藝流程復(fù)雜性的特點(diǎn)，我們要對對象進(jìn)行合并、分割、集中的特點(diǎn)運(yùn)用相應(yīng)的代數(shù)方法進(jìn)行模型的建立以此促進(jìn)按時完成訂單和節(jié)能減排的一員。

參考文獻(xiàn)：

篇2

【關(guān)鍵詞】車輛調(diào)度；物流配送；多車型

【中圖分類號】U492.2 【文獻(xiàn)標(biāo)識碼】A

配送車輛調(diào)度問題是運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的熱點(diǎn)問題.多車型配送車輛調(diào)度問題是配送車輛調(diào)度問題的一個分支，一般情況下，配送企業(yè)為了適應(yīng)配送商品種類繁多、性質(zhì)各異、客戶要求各不相同的情況，往往配置多種類型的配送車輛，以提高車輛的滿載率，降低配送成本.可見，研究多車型配送車輛調(diào)度問題具有重要的理論和現(xiàn)實(shí)意義.

本文在現(xiàn)有研究成果的基礎(chǔ)上，建立了多車型配送車輛調(diào)度問題的基于直觀描述的數(shù)學(xué)模型，考慮的目標(biāo)函數(shù)和約束條件比較接近實(shí)際，決策變量、目標(biāo)函數(shù)和約束條件的表示較為自然、直觀和易于理解.

1.對多車型配送車輛調(diào)度問題的描述

現(xiàn)實(shí)中的多車型配送車輛調(diào)度問題十分復(fù)雜，為了方便建模和求解，需要對現(xiàn)實(shí)問題進(jìn)行一些抽象和簡化.現(xiàn)對本文研究的多車型配送車輛調(diào)度問題作如下描述：

1）從一個配送中心向多個客戶送貨，配送中心供應(yīng)的貨物能夠滿足所有客戶的需求；

2）各個客戶需求的貨物均可以混裝，單一客戶的貨物需求量不超過配送車輛的最大載重量，每個客戶的送貨要求必須滿足，且僅能由一輛車完成，不允許分批配送；

3）配送車輛按載重量分類，每種車型的最大載重量一定且不允許超載，每種車型

的一次配送最大行駛距離一定，不允許超過.配送車輛均由配送中心出發(fā)，向一些客戶提供配送服務(wù)，最后返回配送中心；

4）配送中心與客戶之間及客戶相互之間的最短距離已知且固定.

在滿足上述條件下，我們要求運(yùn)輸成本最小.

2.構(gòu)建數(shù)學(xué)模型

現(xiàn)有一個有向圖G=（V，E），其中V={0，1，…，N}有N+1個頂點(diǎn)，E={（i，j）|i，j∈V，i≠j}表示弧集，頂點(diǎn)0表示配送中心，剩余的頂點(diǎn)集V′=V＼{0}表示N個配送點(diǎn)，為構(gòu)建多車型最小費(fèi)用車輛路徑問題數(shù)學(xué)模型，定義以下參數(shù)：

gi： 配送點(diǎn)i的需求量；

φ={1，2，…，L}為車輛類型的集合，類型總數(shù)為L；

Kl：l車型的數(shù)量；

φl：車型l的車輛數(shù)集，φl={1，2，…，Kl}；

dij： 兩個節(jié)點(diǎn)間的最短距離，i，j∈V；

Ql： 車型l的裝載能力，Q0l表示車型l的空重；

cl： l型車每公里每噸的載重費(fèi)用，單位：元/噸?公里；

clkij： l型車的第k輛從第i點(diǎn)到第j點(diǎn)的費(fèi)用，與距離和載重有關(guān)：

clkij=dijclrlkij（i，j）∈E；l∈φ；k∈φl；

rlkij： l型車的第k輛從第i點(diǎn)到第j點(diǎn)車輛的重量；

xlkij=1 l型車的第k輛從第i點(diǎn)行駛到第j點(diǎn)0 否則

式（1）表示目標(biāo)函數(shù)，即總配送成本最?。?/p>

式（2）保證車輛都是從配送中心出發(fā)，最后回到配送中心；

式（3）表示進(jìn)入每個貨物需求點(diǎn)的車輛卸載后會離開；

式（4）、（5）確保每個貨物需求點(diǎn)只能被一輛車服務(wù)一次；

式（6）表示車輛承載的貨物量之和不得大于車輛的容量；

式（7）是遞推車輛行駛路徑的總車質(zhì)量；

式（8）是車輛回到配送中心時車輛的重量；

式（9）是不超過車輛的裝載能力；

式（10）是經(jīng)過某一配送點(diǎn)時車輛重量不能小于空車重量；

式（11）是l型車的第k輛從第i點(diǎn)到第j點(diǎn)的費(fèi)用計算公式.

3.算法過程

在多車型低耗車輛路徑問題解決過程中，本文采用爬山算法作為求解的主要算法.爬山算法是一種局部擇優(yōu)的方法，它采用啟發(fā)式方法，是對深度優(yōu)先搜索的一種改進(jìn)，它利用反饋信息幫助生成解的決策.該算法每次從當(dāng)前解的臨近解空間中選擇一個最優(yōu)解作為當(dāng)前解，直到達(dá)到一個局部最優(yōu)解.屬于人工智能算法的一種.爬山算法結(jié)構(gòu)比較簡單，在某些情況下，整體效率還是很好的.但它的主要缺點(diǎn)是有時會陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解.但由于它求解時可以把復(fù)雜問題簡單化，且解的結(jié)果與最優(yōu)解比較接近，所以在很多領(lǐng)域中都有著廣泛的應(yīng)用.

爬山算法的基本步驟如下：

第一步：輸入多車型低耗車輛路徑問題，包括配送中心、顧客點(diǎn)之間的坐標(biāo)，配送

點(diǎn)需求，車型參數(shù)（載重能力、空重、不同車型固定成本）等.任意選定一個初始解x0，記錄當(dāng)前最優(yōu)解為xbest，且令xbest=x0，令U（xbest）代表xbest的鄰域.

第二步：從xbest的鄰域U（xbest）中按照某一規(guī)則選出一個解xnow，轉(zhuǎn)到第三步；

若當(dāng)U（xbest）=φ時，或滿足其他停止運(yùn)算的規(guī)則時，轉(zhuǎn)到第四步；

第三步：計算xnow的目標(biāo)函數(shù)值minZ1，若xnow的目標(biāo)函數(shù)值minZ1小于xbest的目標(biāo)函數(shù)值minZ，則xbest=xnow，minZ=minZ1，U=U（xbest），轉(zhuǎn)到第二步；否則 U=U-xnow，轉(zhuǎn)到第二步；

第四步：輸出計算結(jié)果，停止.

在爬山算法中，第一步的初始解可以采用隨機(jī)方法產(chǎn)生，也可以用一些經(jīng)驗(yàn)方法或者采用其他算法得到初始解.第二步中在U（xbest）中選取xnow的規(guī)則也可以采用隨機(jī)選取的規(guī)則.

4.實(shí)驗(yàn)計算和結(jié)果分析

實(shí)例：設(shè)配送中心（0，0）和16 個客戶配送點(diǎn)分布及需求情況，具體數(shù)據(jù)見表1，假設(shè)該配送中心有3種車型，見表2.根據(jù)以上的爬山算法，我們應(yīng)用Lingo語言來求解，獲得費(fèi)用最少的行駛路徑，見表3，此時費(fèi)用為3654.40元.

5.結(jié) 論

總的來說，對于復(fù)雜的VRP，如果僅憑決策者的經(jīng)驗(yàn)，是很難在較短時間內(nèi)作出一個合理的運(yùn)輸路徑規(guī)劃的，本文利用優(yōu)化模型，采用爬山算法，再通過Lingo自動搜索得到費(fèi)用最少的最優(yōu)路徑和車輛調(diào)度數(shù).最終結(jié)果是比較令人滿意的.

【參考文獻(xiàn)】

[1]楊浩雄，胡靜，何明珂.配送中多車場多任務(wù)多車型車輛調(diào)度研究[J].計算機(jī)工程與應(yīng)用，2013，49（10）.

篇3

【關(guān)鍵詞】可分負(fù)載 任務(wù)調(diào)度 可分負(fù)載理論（DLT）

調(diào)度問題是并行分布式系統(tǒng)研究領(lǐng)域中影響系統(tǒng)性能的最主要的因素之一。常用的對并行分布式系統(tǒng)中任務(wù)調(diào)度問題的建模主要有兩種，一種是基于DAG圖的相關(guān)任務(wù)調(diào)度，另外一直是基于可分負(fù)載理論（DLT）的獨(dú)立任務(wù)調(diào)度。

可分負(fù)載指的是任務(wù)可以劃分成任意數(shù)目，任意大小的獨(dú)立子任務(wù)，而這些子任務(wù)可以并行執(zhí)行且不會影響整個任務(wù)的最終結(jié)果。由于應(yīng)用上的需求，而可分負(fù)載理論在模型的精確性和問題的可解性之間取得很好的折中，近年來使其成為并行調(diào)度領(lǐng)域研究的一個新的熱點(diǎn)。對于如數(shù)據(jù)挖掘、圖像處理、大規(guī)模實(shí)驗(yàn)仿真、計算生物學(xué)等經(jīng)典的主從計算范例，可分負(fù)載調(diào)度可以取得很好的效果。

可分負(fù)載的任務(wù)調(diào)度采用線性模型對網(wǎng)絡(luò)和應(yīng)用進(jìn)行建模，并且充分利用了負(fù)載可任意劃分的特性，可以使用數(shù)學(xué)的方法進(jìn)行分析論證，使得很多重要類型的可分負(fù)載問題在特定情況下可以獲得近似最優(yōu)解或最優(yōu)解，這是可分負(fù)載的任務(wù)調(diào)度獲得成功的主要原因之一。

可分負(fù)載調(diào)度算法按對負(fù)載的分配方法可以分為：單輪可分負(fù)載調(diào)度算法和多輪可分負(fù)載調(diào)度算法兩種類型。

1 可分負(fù)載單輪調(diào)度

可分負(fù)載單輪調(diào)度算法就是指主處理機(jī)節(jié)點(diǎn)將負(fù)載劃分成塊數(shù)與從處理機(jī)節(jié)點(diǎn)數(shù)相等的子負(fù)載塊，然后一次性完成對子負(fù)載塊的分配處理。

可分負(fù)載單輪調(diào)度算法設(shè)計的主要難點(diǎn)是：

（1）確定主處理機(jī)節(jié)點(diǎn)給各個從處理機(jī)分發(fā)任務(wù)時的順序；

（2）確定給每一個從處理機(jī)節(jié)點(diǎn)分配多少負(fù)載量。但是由于后分配的從處理機(jī)都要較長的等待時間，所以單輪負(fù)載調(diào)度算法的效果不是很好。

可分負(fù)載單輪調(diào)度的研究成果有：

1.1 基本模型

這是研究在最理想情況下的調(diào)度問題，即不考慮通信鏈路的時間延遲，也不考慮機(jī)群系統(tǒng)的內(nèi)存不足的情況。在該情形下負(fù)載的通信時間為ai/zi，負(fù)載的計算時間為ai/wi（αi表示負(fù)載塊的大小，zi表示通信速度，wi表示處理機(jī)計算速度）。有關(guān)資料也證明了在同構(gòu)系統(tǒng)下，為了使調(diào)度的時間最短，所有的處理機(jī)都必須參與任務(wù)的計算，且任務(wù)調(diào)度時間不依賴于負(fù)載分發(fā)的順序。在異構(gòu)系統(tǒng)下，則應(yīng)該按照鏈路速度遞減的順序進(jìn)行負(fù)載的分發(fā)，并且所有處理機(jī)必須同時完成負(fù)載的計算，這樣的話負(fù)載就可以在多項(xiàng)式時間內(nèi)完成計算。

1.2 考慮時間延遲的模型

由于現(xiàn)實(shí)的網(wǎng)絡(luò)中存在通信的啟動時間，且每個進(jìn)程在開始處理數(shù)據(jù)之前也可能需要先進(jìn)行一些系統(tǒng)的初始化的工作，為此，在此模型下將負(fù)載的通信時間和計算時間分別定義為ci+αi/zi和oi+αi/wi （ci和oi分別表示通信和計算時間的延遲），所以在該情形下，選擇所有的處理機(jī)產(chǎn)生的效果可能比選擇一部分處理機(jī)的效果來得低。資料顯示單輪可分負(fù)載的任務(wù)調(diào)度異構(gòu)環(huán)境下遵循的原則有：

（1）如負(fù)載足夠大，則所有的處理機(jī)都參與計算。

（2）所有參與計算的處理機(jī)都必須同時完成計算任務(wù)。

（3）當(dāng)所有的鏈路是相同的時候則各處理機(jī)須按照c/w的升序進(jìn)行負(fù)載的接收，如果鏈路速度不同、時間延遲不同則目前還找不到最優(yōu)的分發(fā)順序。經(jīng)過分析得出，單輪調(diào)度下的新的結(jié)論：當(dāng)鏈路速度不同，通信延遲時間不同，各處理機(jī)計算速度不同時，當(dāng)則應(yīng)該按鏈路速度從大到小的順序進(jìn)行負(fù)載的分發(fā)可得到在給定的比較大的時間內(nèi)的最優(yōu)調(diào)度。

1.3 考慮系統(tǒng)內(nèi)存容量有限的模型

以上關(guān)于單輪可分負(fù)載的任務(wù)調(diào)度的研究都是在假設(shè)系統(tǒng)的內(nèi)存容量足夠大的情形下進(jìn)行的，而在實(shí)際情況中每個處理機(jī)系統(tǒng)的內(nèi)存都是有限的，所以當(dāng)分發(fā)到的負(fù)載量大于其內(nèi)存容量時，則算法是不能有效運(yùn)行的，且處理機(jī)進(jìn)行任務(wù)計算的速度也會受到很大影響，因此內(nèi)存受限問題是調(diào)度算法中不可忽略的問題。有關(guān)文獻(xiàn)也討論了內(nèi)存受限的單層樹型網(wǎng)絡(luò)的異構(gòu)機(jī)群系統(tǒng)下單輪可分負(fù)載的任務(wù)調(diào)度，提出了IBS算法，該算法在每進(jìn)行一次迭代，都將以一個處理機(jī)節(jié)點(diǎn)的內(nèi)存大小為標(biāo)準(zhǔn)分發(fā)負(fù)載，然后該處理機(jī)節(jié)點(diǎn)不再參與后面負(fù)載的調(diào)度。但是該算法沒有考慮時間的延遲，為此，后來后者對其進(jìn)行了改進(jìn)，提出了既考慮內(nèi)存不足也考慮時間延遲問題的算法。分析分層存儲系統(tǒng)、單層受限存儲系統(tǒng)中內(nèi)存對可分負(fù)載的調(diào)度性能的影響，給出了在分發(fā)順序已知、考慮內(nèi)存、考慮時間延遲情況下的周期性可分負(fù)載多輪調(diào)度的模型，通過設(shè)定一個布爾變量表示處理機(jī)j是否是分發(fā)序列中的第i個處理機(jī)的方法，來研究涉及處理機(jī)順序選擇問題，并給出了數(shù)學(xué)模型。

1.4 考慮結(jié)果信息返回的模型

在實(shí)際應(yīng)用中存在一些應(yīng)用在處理完任務(wù)后需要將處理結(jié)果返回給中心處理節(jié)點(diǎn)，如果返回的信息量比較大的話，則返回結(jié)果信息的通信時間是不能忽略的。帶返回結(jié)果信息的可分負(fù)載調(diào)度中常見的兩種通信策略是FIFO策略和LIFO策略。FIFO策略是指從處理機(jī)在處理完負(fù)載后返回結(jié)果信息給主處理機(jī)節(jié)點(diǎn)的處理機(jī)順序與其在接收主處理機(jī)給它分發(fā)負(fù)載時的處理機(jī)順序是一樣的，如果順序正好相反則是LIFO策略。

專業(yè)資料首次研究了這種類型的問題，它解決了兩類特殊應(yīng)用的最優(yōu)調(diào)度問題：一類是通信時間與消息大小無關(guān)的常量，這種情況下按LIFO方式是最優(yōu)的方法；另一類是在總線網(wǎng)上且數(shù)據(jù)的傳輸過程中忽略啟動開銷的情況，在這種情況下按FIFO方式是最優(yōu)的。而在雙工通信模式下，即主處理機(jī)節(jié)點(diǎn)分發(fā)任務(wù)的同時可以接收從處理機(jī)節(jié)點(diǎn)返回的信息的星型拓?fù)浣Y(jié)構(gòu)下的可分負(fù)載調(diào)度問題，分別討論了FIFO和LIFO這兩種策略對調(diào)度性能的影響，并證明了最佳的結(jié)果信息的返回方案既不是FIFO策略也不是LIFO策略。星型網(wǎng)絡(luò)環(huán)境下，采用單工通信模式的考慮結(jié)果信息返回的可分負(fù)載調(diào)度問題，得到了在分發(fā)順序已知、所有參加計算的處理機(jī)沒有空閑時間情況下的最優(yōu)調(diào)度。

2 可分負(fù)載多輪調(diào)度

可分負(fù)載多輪調(diào)度算法是指主處理機(jī)節(jié)點(diǎn)將應(yīng)用劃分成塊數(shù)大于從處理機(jī)數(shù)目的子任務(wù)，采用并行多次分配的方法多次將子任務(wù)分給各個從處理機(jī)節(jié)點(diǎn)。其算法設(shè)計存在的難題是：

（1）如何確定負(fù)載劃分的塊數(shù)；

（2）每塊負(fù)載的大小如何確定；

（3）從處理機(jī)接收負(fù)載的順序如何。

可分負(fù)載多輪調(diào)度的研究成果有：

2.1 基本模型

有關(guān)文獻(xiàn)研究了在給定趟數(shù)時同構(gòu)平臺下多輪可分負(fù)載調(diào)度，提出了MI算法，該算法用數(shù)學(xué)方法得到函數(shù)來解決負(fù)載塊大小的問題，且該文獻(xiàn)中給出為了得到好的調(diào)度，在分配負(fù)載的時候該遵循：

（1）各處理機(jī)在接收下一負(fù)載塊之前要完成當(dāng)前負(fù)載塊的計算；

（2）各從處理機(jī)完成當(dāng)前輪負(fù)載計算的時候主處理機(jī)也完成了下一輪負(fù)載的分發(fā)。

2.2 考慮時間延遲的模型

關(guān)于考慮時間延遲的XMI算法，但是該算法仍然沒有提出求解最優(yōu)輪數(shù)的方法。為了使多輪調(diào)度更有效，學(xué)者們又提出了機(jī)群系統(tǒng)下考慮時間延遲的均勻多輪調(diào)度算法UMR，該算法通過在同構(gòu)系統(tǒng)下采用每輪分配給各處理機(jī)節(jié)點(diǎn)負(fù)載量相同、異構(gòu)系統(tǒng)下使每輪各處理機(jī)處理時間相同的策略，給出了求解最優(yōu)調(diào)度輪數(shù)的方法，使整體的調(diào)度性能得到大幅度提高。在UMR算法的基礎(chǔ)上做了擴(kuò)展，提出了一種可以得到更好調(diào)度效果的多輪調(diào)度算法RUMR，該算法考慮性能預(yù)測中可能存在的錯誤，通過先從小到大遞增負(fù)載塊，然后再遞減負(fù)載塊的方法進(jìn)行負(fù)載的分配，使得算法更加實(shí)用。星型拓?fù)浣Y(jié)構(gòu)下可分負(fù)載的多輪調(diào)度問題以及在周期性調(diào)度中對相應(yīng)參數(shù)進(jìn)行優(yōu)化的問題，并進(jìn)一步證明了當(dāng)負(fù)載量比較大時，若要得到近似最優(yōu)的調(diào)度算法，應(yīng)該要保證在通信過程中鏈路不出現(xiàn)空閑。

以上所提出的多輪調(diào)度算法，都假設(shè)各處理機(jī)都是周期性的參與計算，且計算和通信之間沒有空閑時間，所以后來的文獻(xiàn)資料只研究了一般的情形，即不要求參與計算的處理機(jī)周期性的接收負(fù)載，在子負(fù)載塊數(shù)已知的情況下的多輪可分負(fù)載任務(wù)調(diào)度，并分別用B&B方法和啟發(fā)式的算法得到各負(fù)載塊的大小及分發(fā)的目的處理機(jī)號。通過總結(jié)分析已有的研究成果，通過設(shè)定布爾值的方法，設(shè)計了可分負(fù)載單輪調(diào)度中帶處理機(jī)的選擇問題的算法，并給出了星型網(wǎng)絡(luò)下參加計算的處理機(jī)給定情況下的可分負(fù)載多輪調(diào)度，不過該算法的目標(biāo)不是為了最小化負(fù)載的處理時間，而是以在給定一個時間內(nèi)負(fù)載塊的處理數(shù)量的最大化為目標(biāo)的算法，并給出了詳細(xì)的證明。

2.3 考慮系統(tǒng)內(nèi)存容量有限的模型

考慮內(nèi)存的可分負(fù)載多輪調(diào)度算法，該算法是在子負(fù)載塊的塊數(shù)已知的情況下考慮的。而文獻(xiàn)考慮了各處理機(jī)的內(nèi)存問題，提出了UMRLM算法，采用當(dāng)某輪負(fù)載總量超過從處理機(jī)的內(nèi)存容量的時候，使該輪及后面每輪輪負(fù)載總量和前一次的負(fù)載總量相等的策略避免了由于內(nèi)存容量不足時UMR不能繼續(xù)執(zhí)行的問題，提高了算法的實(shí)用性。

2.4 考慮結(jié)果信息返回的模型

有關(guān)文獻(xiàn)考慮了同構(gòu)系統(tǒng)下帶返回信息的多輪調(diào)度算法，該文獻(xiàn)分別研究了不考慮時間延遲和考慮時間延遲兩種情況，但該算法針對的是調(diào)度輪數(shù)給定的情形。在采用FIFO策略提出了異構(gòu)機(jī)群系統(tǒng)上帶返回結(jié)果信息的可分負(fù)載多輪調(diào)度算法。

除了上面的基本模型及其擴(kuò)展的模型外，近年還有其他一些研究成果，比如：提出了具有兩個主處理節(jié)點(diǎn)（即由兩個處理機(jī)來進(jìn)行任務(wù)的分配）的情形，且主處理機(jī)能同時和兩個從處理機(jī)進(jìn)行通信，得到一個漸進(jìn)最優(yōu)的調(diào)度。同時還提出了在系統(tǒng)參數(shù)未知情況下的可分負(fù)載的調(diào)度算法，在文獻(xiàn)中把負(fù)載分發(fā)分兩個階段：第一階段將很小部分的負(fù)載分發(fā)到各處理機(jī)節(jié)點(diǎn)，且從處理機(jī)節(jié)點(diǎn)處理完后向主處理機(jī)節(jié)點(diǎn)返回信息，然后根據(jù)返回的信息估計各個參數(shù)，從而根據(jù)估計的參數(shù)來確定余下的負(fù)載的分發(fā)，但是該文獻(xiàn)研究的是單輪調(diào)度。據(jù)文獻(xiàn)研究了單層樹模型下，針對未知網(wǎng)絡(luò)參數(shù)的異構(gòu)網(wǎng)絡(luò)系統(tǒng)，提出了一個基于探測技術(shù)的多階段的針對多可分負(fù)載任務(wù)的調(diào)度策略，文中考慮了不知道網(wǎng)絡(luò)性能參數(shù)以及網(wǎng)絡(luò)性能隨時間動態(tài)變化兩種情形。機(jī)群環(huán)境下有多個可分負(fù)載任務(wù)的調(diào)度問題，其中文在星型環(huán)境下證明了多個可分負(fù)載的調(diào)度問題是計算難的，只有在一些假設(shè)情況下才存在著多項(xiàng)式時間解，在總線型結(jié)構(gòu)下的多個可分負(fù)載的調(diào)度問題。

上面所有文獻(xiàn)資料中所提到的算法都是在從處理機(jī)接收完負(fù)載以后才開始計算（blocking通信模式），而在大型的應(yīng)用以及實(shí)時系統(tǒng)中，這種模式是不適用的，所以在后面的文獻(xiàn)資料中提出了noblocking的通信模式，即從處理機(jī)在接收任務(wù)的同時就可以開始計算工作。并且得出近似的關(guān)于處理時間的表達(dá)式及最優(yōu)的調(diào)度順序?？煞重?fù)載調(diào)度在實(shí)際應(yīng)用當(dāng)中取得的效果，證明了可分負(fù)載調(diào)度的實(shí)用性。另外，隨著多核機(jī)器的出現(xiàn)，異構(gòu)多核機(jī)群系統(tǒng)上的可分負(fù)載多輪調(diào)度算法，系統(tǒng)參數(shù)未知的多核異構(gòu)機(jī)群上考慮結(jié)果信息返回模型的可分負(fù)載多輪調(diào)度算法。

3 結(jié)語

綜上所述，可分負(fù)載單輪的任務(wù)調(diào)度研究的比較透徹，而可分負(fù)載多輪的任務(wù)調(diào)度的研究成果就比較少，且已有的研究成果大多都是假設(shè)內(nèi)存足夠大、結(jié)果的返回時間忽略的情形，且系統(tǒng)的所有參數(shù)都是事先確定好的靜態(tài)的調(diào)度，同時，大多數(shù)的研究都是在單核的機(jī)群系統(tǒng)上進(jìn)行的，而在多核機(jī)器占主導(dǎo)地位的今天，今后研究在由多核機(jī)器組成的機(jī)群系統(tǒng)上的可分負(fù)載的任務(wù)調(diào)度就顯得尤為重要。

參考文獻(xiàn)

[1]李顯寧，鐘誠，楊鋒.異構(gòu)集群系統(tǒng)的可分負(fù)載多輪調(diào)度算法[J].計算機(jī)應(yīng)用研究，2008，25（4）：1028-1032.

[2]鐘誠，李顯寧.異構(gòu)機(jī)群系統(tǒng)上帶返回信息的可分負(fù)載多輪調(diào)度算法[J].計算機(jī)研究與發(fā)展，2008，45（Suppl）：99-104.

[3]黎鶴，孫廣中，許胤龍.未知網(wǎng)絡(luò)中可分負(fù)載的分布式調(diào)度[J].中國科學(xué)技術(shù)大學(xué)學(xué)報，2009，39（8）：864-870.

[4]Cheng Zhong，Xia Li，F(xiàn)eng Yang，Jun Liu，Meng-Xiao Yin，Yi-Ran Huang. Scheduling Divisible Loads with Return Messages on Multi-core Heterogeneous Clusters with Unknown System Parameters[J].EN.2012（7）.

作者簡介

李霞（1980-），女，研究生學(xué)歷。碩士學(xué)位?，F(xiàn)為廣西財經(jīng)學(xué)院防城港學(xué)院教師。研究方向?yàn)榫W(wǎng)絡(luò)與并行計算 。

篇4

[關(guān)鍵詞] 仿真 物流系統(tǒng) 供應(yīng)鏈

隨著物流系統(tǒng)變得越來越復(fù)雜并且內(nèi)部關(guān)聯(lián)性越來越強(qiáng)，建模與仿真的方法在物流系統(tǒng)的完善和決策中變得日益重要。仿真是利用計算機(jī)來運(yùn)行仿真模型，模擬時間系統(tǒng)的運(yùn)行狀態(tài)及其隨時間變化的過程，并通過對仿真運(yùn)行過程的觀察和統(tǒng)計，得到被仿真系統(tǒng)的仿真輸出參數(shù)和基本特性，以此來估計和推斷實(shí)際系統(tǒng)的真實(shí)參數(shù)和真實(shí)性能。計算機(jī)仿真的類型有離散事件(系統(tǒng))仿真、連續(xù)系統(tǒng)仿真、混合系統(tǒng)仿真，還有蒙特卡羅仿真(Monte Carlo Simulation)等。

物流系統(tǒng)是復(fù)雜的離散事件系統(tǒng)，在系統(tǒng)設(shè)計與控制過程中存在許多優(yōu)化問題，用系統(tǒng)仿真為解決復(fù)雜物流系統(tǒng)的問題提供了有效的手段，它不僅可提供用于決策的定量信息而且可以提高決策者對物流系統(tǒng)工作原理的理解水平，仿真技術(shù)為復(fù)雜物流系統(tǒng)設(shè)計提供了技術(shù)性和經(jīng)濟(jì)性的最佳結(jié)合點(diǎn)和直觀有效的分析方法。

因此,物流系統(tǒng)仿真成為近年來國內(nèi)外學(xué)術(shù)界研究的一個熱點(diǎn)問題。本文對物流系統(tǒng)中的供應(yīng)鏈仿真、生產(chǎn)物流系統(tǒng)仿真和物流配送系統(tǒng)仿真進(jìn)行綜述。

一、供應(yīng)鏈仿真

供應(yīng)鏈管理是一種為適應(yīng)市場全球化和客戶需求多樣化而產(chǎn)生的一種管理技術(shù)，它能夠有效地協(xié)調(diào)和控制供應(yīng)鏈上物料流、信息流、價值流，保持靈活和穩(wěn)定的供需關(guān)系，使整個供應(yīng)鏈上企業(yè)效益最大化。由于供應(yīng)鏈這類復(fù)雜系統(tǒng)中存在著很多不確定性和隨機(jī)性因素，而數(shù)學(xué)方法由于求解條件的限制，建立的數(shù)學(xué)模型有時存在著求解困難甚至不可解的結(jié)果。在此情況下，以數(shù)學(xué)模型為基礎(chǔ)、以求數(shù)值解或特解為特征的仿真建模方法顯示出了極強(qiáng)的技術(shù)優(yōu)勢。近年來，伴隨著許多成熟的仿真軟件的引入和使用，各種仿真建模方法解決供應(yīng)鏈問題的適用性也得到了大幅度提高。

近年來，很多學(xué)者進(jìn)行了物流與供應(yīng)鏈管理的仿真與建模方面的研究。高翔，林杰，張煒等仿真的供應(yīng)鏈強(qiáng)調(diào)上游及下游企業(yè)問的信息共享與相互協(xié)作，并根據(jù)供應(yīng)鏈中不同的信息做出相應(yīng)的決策。它將整個供應(yīng)鏈分為三層結(jié)構(gòu)，即供應(yīng)商、制造商和銷售商，此外還有運(yùn)輸商負(fù)責(zé)不同層面之間的聯(lián)系，并通過建模仿真對系統(tǒng)進(jìn)行優(yōu)化，提高系統(tǒng)的整體適應(yīng)能力。

朱衛(wèi)峰，費(fèi)奇針對復(fù)雜物流系統(tǒng)仿真及其現(xiàn)狀進(jìn)行了研究，給出了復(fù)雜物流系統(tǒng)的網(wǎng)絡(luò)圖結(jié)構(gòu)，提出了復(fù)雜物流系統(tǒng)仿真CLSim的總體結(jié)構(gòu)，同時指出了復(fù)雜物流系統(tǒng)仿真研究的三個問題：復(fù)雜物流系統(tǒng)中的不確定性建模、復(fù)雜物流系統(tǒng)仿真模型設(shè)計與實(shí)現(xiàn)及復(fù)雜物流系統(tǒng)控制；并將復(fù)雜物流系統(tǒng)仿真設(shè)計的思想應(yīng)用于敏捷后勤仿真系統(tǒng)，提出了基于時間步進(jìn)的事件調(diào)度仿真策略，用實(shí)體流程圖法設(shè)計了敏捷后勤系統(tǒng)的仿真模型。

隨著電子商務(wù)的逐步普及，面向制造企業(yè)的傳統(tǒng)供應(yīng)鏈的結(jié)構(gòu)發(fā)生了變化，程曙等運(yùn)用優(yōu)化方法理論從供應(yīng)鏈的系統(tǒng)性和整體性視角出發(fā)，對此種供應(yīng)鏈的結(jié)構(gòu)進(jìn)行詳細(xì)的建模和仿真研究，尋找具體的決策優(yōu)化方法，并探討了其中的目標(biāo)函數(shù)、約束條件等關(guān)鍵性問題。

彭建剛在分析供應(yīng)鏈管理的基礎(chǔ)上，提出“一流二網(wǎng)三關(guān)系”的供應(yīng)鏈建模思想：“一流” 指訂單信息流；“二網(wǎng)” 指物流網(wǎng)和資源網(wǎng)；“三關(guān)系”指客戶關(guān)系、動態(tài)關(guān)系和集成關(guān)系。同時對供應(yīng)鏈建模的混合整數(shù)規(guī)劃和統(tǒng)一優(yōu)化方法論作了闡述，為供應(yīng)鏈的建模提供了較為實(shí)用的方法。

彭晨等應(yīng)用供應(yīng)鏈思想對煤炭供應(yīng)鏈進(jìn)行研究，應(yīng)用Petri網(wǎng)對供應(yīng)鏈物流及供應(yīng)流運(yùn)行過程進(jìn)行建模，然后運(yùn)用子過程分析煤炭供應(yīng)鏈存在的問題，最后結(jié)合煤炭供應(yīng)鏈過程模型運(yùn)用VB方法完成供應(yīng)鏈決策過程的可視化仿真，找出煤炭供應(yīng)鏈運(yùn)營瓶頸。

在二級供應(yīng)鏈研究方面，郭士正研究了服務(wù)銷售系統(tǒng)的二級供應(yīng)鏈模型，是關(guān)于設(shè)施選址和市場顧客配置的混合整數(shù)規(guī)劃問題。在實(shí)例應(yīng)用中，對奶制品零售分銷的供應(yīng)鏈問題進(jìn)行了計算機(jī)仿真計算。

二、生產(chǎn)物流系統(tǒng)仿真

生產(chǎn)物流是指從企業(yè)的原材料采購，車間生產(chǎn)，半成品與成品的周轉(zhuǎn)直至成品發(fā)送的全過程中的物流活動。生產(chǎn)物流系統(tǒng)是一個復(fù)雜的綜合性系統(tǒng)，如何提高其效率和效益是至關(guān)重要的，系統(tǒng)仿真作為一項(xiàng)用于系統(tǒng)分析和研究的十分有效的技術(shù)，已經(jīng)被廣泛用來對生產(chǎn)物流系統(tǒng)進(jìn)行規(guī)劃設(shè)計，運(yùn)輸調(diào)度和物料控制等。

A．Sawhney(1999)將Petri網(wǎng)技術(shù)用于郵件處理中心，對整個處理中心的工作流程進(jìn)行了分析與優(yōu)化，提高了郵件處理的效率。

張穎利等對某微型汽車廠總裝車間的生產(chǎn)物流系統(tǒng)進(jìn)行分析研究，在此基礎(chǔ)上對其建模和仿真，在仿真過程中可以看到主要部件在裝配線中所處的位置，能夠判斷裝配各種零件所需要的時間，方便車間管理人員根據(jù)生產(chǎn)需求對生產(chǎn)線進(jìn)行及時的調(diào)整。

詹躍東基于Petri網(wǎng)建模理論，對煙草行業(yè)的卷接包車間的AGVS進(jìn)行了分析，并對該系統(tǒng)構(gòu)造了Petri網(wǎng)模型。

何臘梅等則以某煉鋼廠全連鑄改造后的生產(chǎn)調(diào)度問題為應(yīng)用背景，研究了此煉鋼生產(chǎn)物流系統(tǒng)的仿真建模與仿真運(yùn)行問題。在此系統(tǒng)現(xiàn)有流程生產(chǎn)物流的輸入條件下。分別對設(shè)備在正常生產(chǎn)以及正常檢修兩種不同條件下進(jìn)行了仿真試驗(yàn)，得出系統(tǒng)正常運(yùn)行所需的臨界條件。

嵇振平等使用分層有色Petri網(wǎng)(HCPN)和事件操作表(EOL)的方法來減少復(fù)雜制造系統(tǒng)建模的復(fù)雜性，為物流仿真軟件體系結(jié)構(gòu)的模塊化及層次化設(shè)計建立了良好的基礎(chǔ)，并將HCPN應(yīng)用于寶鋼煉鋼連鑄生產(chǎn)物流仿真系統(tǒng)的建模中。

三、物流配送系統(tǒng)仿真

在現(xiàn)代物流系統(tǒng)中，配送中心是集物流、信息流和資金流為一體的流通型節(jié)點(diǎn)，是現(xiàn)代物流系統(tǒng)中的重要組成部分。對物流配送中心，特別是配送中心各個子系統(tǒng)的研究也越來越多。

在配送中心的多個子系統(tǒng)中，分揀系統(tǒng)是較為復(fù)雜的，同時又是其核心部分。邵明習(xí)等對物流分揀系統(tǒng)進(jìn)行建模。主要對系統(tǒng)中的設(shè)備的選擇進(jìn)行研究討論．著重描述了分揀設(shè)備的動態(tài)運(yùn)行過程，以及速度的選擇對分揀效率的影響。

沙洪洲等則是以配送中心的倉儲系統(tǒng)為研究對象，建立了其數(shù)學(xué)模型并研制了計算機(jī)仿真軟件。在軟件平臺上，只要給出庫存初始參數(shù)和出庫隨機(jī)分布就可以清楚地看到庫存量的動態(tài)變化過程，并預(yù)測達(dá)到庫滿或庫空所需的時間。

在輸送系統(tǒng)研究方面，孫娟等對物流輸送系統(tǒng)進(jìn)行三維動畫仿真，在仿真程序中通過對設(shè)備參數(shù)設(shè)定，可以模擬出在這組參數(shù)下整個運(yùn)輸系統(tǒng)的繁忙狀況及各設(shè)備的工作效率，從而對系統(tǒng)的輸送能力做出評估。

在物流活動中，科學(xué)合理的貨物配送路徑選擇是物流中心在最佳時間選擇最佳路徑為客戶提供最佳服務(wù)的有效保證。王英凱等[17]對貨物配送最佳路徑進(jìn)行研究，為其建立了一個基于遺傳算法的數(shù)學(xué)模型。并對該模型進(jìn)行了較為深入的數(shù)學(xué)處理，給出了智能化配送的路徑量化方法。

張漢江等對配送中心的自動化立體倉庫可視化問題進(jìn)行了探討，采用基于虛擬現(xiàn)實(shí)的仿真輔助設(shè)計方法，建立了輔助自動化立體倉庫設(shè)計的可視化仿真的模型。重點(diǎn)論述了輔助自動化立體倉庫設(shè)計的可視化仿真的設(shè)計過程，并以某公司自動化立體倉庫設(shè)計方案為例，使用該仿真輔助設(shè)計軟件對方案進(jìn)行優(yōu)化調(diào)整。

四、結(jié)束語

系統(tǒng)仿真作為解決復(fù)雜物流系統(tǒng)問題的有效手段，已經(jīng)廣泛應(yīng)用于生產(chǎn)物流系統(tǒng)、供應(yīng)鏈及物流配送系統(tǒng)等研究領(lǐng)域。但是由于實(shí)際供應(yīng)鏈的復(fù)雜性，目前的供應(yīng)鏈仿真只停留在理論研究階段，未能有效地應(yīng)用于實(shí)際的供應(yīng)鏈管理中。對真實(shí)的復(fù)雜物流系統(tǒng)的仿真和總體優(yōu)化是未來研究的方向和重點(diǎn)。

參考文獻(xiàn)：

[1] Kochel P. Solving Logistics Problems through Simulation and Evolution [C]//in the 7th international symposium on operational research in Slovenia Podetrtek，Slovenia．2003

[2]金淳劉昕露:供應(yīng)鏈協(xié)調(diào)的仿真建模方法研究綜述[J]．計算機(jī)應(yīng)用研究，2006，23(4)：1～3

[3]朱衛(wèi)峰費(fèi)奇:復(fù)雜物流系統(tǒng)仿真及其研究現(xiàn)狀[J].系統(tǒng)仿真學(xué)報，2002，l5(3)：353～356

[4]朱衛(wèi)峰費(fèi)奇:敏捷后勤仿真系統(tǒng)設(shè)計與實(shí)現(xiàn)[J]．計算機(jī)仿真，2003，2O(6):4～7

[5]程曙張浩陸劍峰:制造企業(yè)雙渠道市場的供應(yīng)鏈建模和仿真[J].計算機(jī)集成制造系統(tǒng)，2004，10(5)：519～522

[6]彭建剛:供應(yīng)鏈建模分析[J]．現(xiàn)代管理科學(xué)，2004，10：75～76

[7]彭晨岳 東:基于Petri網(wǎng)的流程供應(yīng)鏈過程建模分析[J]． 計算機(jī)工程與應(yīng)用，2003，38(3)：199～201

[8]郭士正盧震:二級供應(yīng)鏈建模及仿真研究[J].集美大學(xué)學(xué)報:自然科學(xué)版，2004，90)：346～349

[9]Sawhney A，Abudayyeh O．Modeling and Analysis of a Mail Processing Plant Using Petri Nets [J]．Advances in Engineering Software(S0965―9978)，1999，3O(8)：543～549

[10]張穎利邵明習(xí):企業(yè)生產(chǎn)物流系統(tǒng)的建模與仿真[J]．物流技術(shù).2005(12)：62～65

[11]詹躍東駱瑛:基于Petri網(wǎng)的物流自動化系統(tǒng)建模與仿真研究[J].系統(tǒng)仿真學(xué)報，2001，13(4)：501～504

[12]何臘梅鄭忠高小強(qiáng)等:攀銅煉鋼生產(chǎn)物流仿真分析[J].重慶大學(xué)學(xué)報，2004，27(5)：57～61

[13]嵇振平陳文明于戈:分層有色Petri Net(HCPN)及其在寶鋼煉鋼連鑄生產(chǎn)物流系統(tǒng)仿真建模中的應(yīng)用[J].冶金自動化，2002，27(2)：6～9

[14]邵明習(xí)王春峰張沂泉:基于AutoMod的物流分揀系統(tǒng)的建模與仿真[J].物流科技，2006，29(2)：50～53

[15]沙洪洲郭果敢:馬爾可夫鏈用于倉儲建模與仿真[J]．計算機(jī)仿真，2005，22(4):61～63

[16]孫娟尹軍琪寧建國:動畫技術(shù)在物流仿真系統(tǒng)中的應(yīng)用[J].起重運(yùn)輸機(jī)械，2003(9)：48～50

篇5

針對連續(xù)泊位與橋吊集成調(diào)度大規(guī)模求解困難的問題，提出一種基于滾動策略的優(yōu)化方法。首先，建立了最小化船舶偏離偏好泊位的成本以及延遲靠泊、延遲離港的懲罰成本的基本的多目標(biāo)優(yōu)化模型；然后，采用滾動調(diào)度方法根據(jù)動態(tài)抵泊的船舶抵達(dá)順序?qū)⒄{(diào)度過程分成連續(xù)的調(diào)度窗口，并設(shè)計窗口的平移策略、當(dāng)前窗口對下一窗口的參數(shù)更新方式；對每個窗口內(nèi)船舶進(jìn)行調(diào)度優(yōu)化，根據(jù)每個窗口內(nèi)的優(yōu)化結(jié)果，更新下一個窗口中數(shù)學(xué)模型的輸入?yún)?shù)；通過選取以船舶數(shù)量表示的滾動計劃窗口和凍結(jié)船舶的數(shù)量，持續(xù)滾動獲得每個窗口的最優(yōu)解，疊加后獲得對所有船舶的靠泊計劃。通過算例分析表明，滾動調(diào)度能夠解決較大規(guī)模的調(diào)度問題，其效率受滾動窗口大小、凍結(jié)船舶數(shù)量及滾動次數(shù)影響。

關(guān)鍵詞：連續(xù)泊位分派問題；橋吊分配問題；滾動策略；混合整數(shù)規(guī)劃；集成調(diào)度

0 引言

泊位和橋吊都是集裝箱碼頭的稀缺資源，泊位分派問題（Berth Allocation Problem， BAP）和橋吊分配問題（Quay Crane Assignment Problem， QCAP）是提高集裝箱港口作業(yè)效率的關(guān)鍵。用于符合實(shí)際情況的動態(tài)連續(xù)靠泊計劃問題（Dynamic Continuous Berth Allocation Problem， DCBAP）是BAP和QCAP的集成優(yōu)化，然而集成優(yōu)化在計算上的困難使得相關(guān)研究成果難以得到推廣。而滾動策略是碼頭實(shí)際運(yùn)作計劃過程中廣泛采用的方法，本文的主要工作是設(shè)計DCBAP的滾動優(yōu)化策略并進(jìn)行實(shí)現(xiàn)。

BAP和QCAP是集裝箱港口運(yùn)作優(yōu)化領(lǐng)域的熱點(diǎn)問題。根據(jù)岸線是否連續(xù)，可分為離散泊位分派問題（Discrete BAP）[1]與連續(xù)泊位分派問題（Continuous BAP）[2]。在離散BAP中，岸線被分為多個泊位，船?？繒r一般不能跨越多個泊位，只能處于某個泊位所限定的位置空間；連續(xù)BAP則把岸線看作一個整體，船舶通?？梢栽谌我饪梢匀菁{它的空閑位置作業(yè)。根據(jù)船舶抵港時間，可分為靜態(tài)泊位分派問題（Static BAP）與動態(tài)泊位分派（Dynamic BAP）問題。靜態(tài)BAP指在進(jìn)行泊位分配時，所有需要安排作業(yè)的船舶都已經(jīng)抵達(dá)港口[3]；而動態(tài)BAP是指泊位分配開始仍有船舶未到港，未到港的船舶會在分配時間段中的某時刻到達(dá)[4]。根據(jù)船舶抵達(dá)的動態(tài)性，依抵達(dá)順序形成序列，為滾動調(diào)度提供基礎(chǔ)。

BAP和QCAP相互耦合，橋吊對船舶的分配數(shù)量直接影響船舶作業(yè)時間。將BAP與QCAP獨(dú)立地分別研究，往往存在一個問題：當(dāng)港口繁忙時，船舶按照最優(yōu)靠泊方式靠泊以后，有限的橋吊不能滿足其正常作業(yè)需求，按時離港；而港口相對空閑時，又可能造成橋吊資源的浪費(fèi)[3，5]。因此在研究BAP時，需要考慮橋吊數(shù)量的限制。Imai等[5]建立了同時優(yōu)化泊位分配與岸橋調(diào)度的模型，考慮了岸橋移動路徑優(yōu)化問題并采用離散泊位分配方法。Legato等[6]以船舶操作時間和岸橋使用數(shù)量最少為目標(biāo)，并考慮船偏好泊位和時間。雖然已有大量文獻(xiàn)對BAP建模和設(shè)計算法，但是通常都對橋吊分派數(shù)量決定船舶作業(yè)時間這一條件進(jìn)行簡化，或者簡化總橋吊數(shù)量有限這一現(xiàn)實(shí)條件。例如，Zhen等[7]針對泊位分配問題的不確定性進(jìn)行了場景分析，并采用啟發(fā)式算法，解決了40條船舶的較大規(guī)模的問題，但忽略了橋吊數(shù)量對船舶作業(yè)時間的影響。Sammarra等[8]采用禁忌搜索算法（Tabu Search，TS）解決了橋吊分派調(diào)度問題，同樣未考慮橋吊分派數(shù)量對船舶作業(yè)時間的影響。目前在靠泊計劃中，同時考慮橋吊數(shù)量對船舶作業(yè)時間影響和橋吊總數(shù)量限制的大規(guī)模問題（例如80條船舶以上），在文獻(xiàn)中尚未見研究。

連續(xù)泊位與橋吊的集成調(diào)度問題在求解上存在困難，以往研究主要采用的是TS和模擬退火算法等啟發(fā)式算法或智能算法對簡化模型進(jìn)行求解[8-10]，而基于數(shù)學(xué)規(guī)劃的精確算法或啟發(fā)式算法往往只能獲得中小規(guī)模問題的最優(yōu)解或近似解[7， 10-11]。滾動調(diào)度法最初主要運(yùn)用于生產(chǎn)制造領(lǐng)域，它通過反復(fù)求解小規(guī)模優(yōu)化問題來取代求解大規(guī)模的調(diào)度問題[8-10]。Raa等[12]利用滾動策略解決離散泊位下的泊位橋吊集成調(diào)度問題，并采用混合啟發(fā)式算法對窗口船舶進(jìn)行調(diào)度優(yōu)化。何軍良等[13]從能耗角度考慮連續(xù)泊位下的泊位調(diào)度模型，并提出了滾動式優(yōu)化決策策略，但并未考慮泊位與橋吊的集成調(diào)度問題。

DCBAP同時考慮了船舶的動態(tài)靠泊、連續(xù)泊位分配、岸橋調(diào)度問題，較符合集裝箱港口動態(tài)優(yōu)化的實(shí)際情形，已有文獻(xiàn)對其進(jìn)行研究。Park等[14]采用兩階段方法，在第一個階段確定靠泊的位置和分配的橋吊數(shù)量，而在第二個階段確定橋吊對船舶的分派，但是在所研究的算例中，只能獲得9個橋吊、40條船舶和1200m岸線的中小規(guī)模算例的近似解。韓曉龍等[15]將泊位問題抽象為二維裝箱問題，建立了同時考慮泊位和橋吊資源的整數(shù)規(guī)劃模型，并采用啟發(fā)式回溯算法求解，但求解規(guī)模也僅僅為5個橋吊、5條船舶的小規(guī)模算例。

相對于已有文獻(xiàn)，本文的工作主要是以下兩點(diǎn)。首先，本文研究DCBAP，同時考慮橋吊數(shù)量對船舶作業(yè)時間影響和橋吊總數(shù)量限制，建立混合整數(shù)線性規(guī)劃模型，目標(biāo)函數(shù)考慮最小化船舶偏離最優(yōu)泊位的偏好成本，以及因延遲靠泊和延遲離港引起的懲罰成本三個目標(biāo)。然后，根據(jù)模型的特征，通過船舶動態(tài)靠泊順序分割滾動調(diào)度窗口，設(shè)計了窗口調(diào)度模型與窗口之間參數(shù)的更新方法，設(shè)計了DCBAP的滾動調(diào)度算法。通過大規(guī)模算例的驗(yàn)證，得到本文建立的模型和滾動調(diào)度算法能夠求解大規(guī)模BAP，求解性能與船舶數(shù)量呈近似線性關(guān)系，能夠推廣用于大型集裝箱港口的靠泊計劃決策支持系統(tǒng)。

1 基本模型

Kim等[14]在解決DCBAP時，將連續(xù)岸線和時間離散化，建立了以時間為橫坐標(biāo)、泊區(qū)為縱坐標(biāo)的二維坐標(biāo)圖表示泊位分配情況。每個矩形表示一個船舶的靠泊計劃。每一個矩形的高度取決于作業(yè)時間，與分配給它的橋吊數(shù)量的函數(shù)關(guān)系成反比關(guān)系。參照Park等[3]建立的模型，本文構(gòu)建的DCBAP模型考慮以下條件：每一條船舶都有預(yù)先設(shè)置的偏好泊位；船舶作業(yè)時間與作業(yè)的橋吊數(shù)量成反比，即作業(yè)時間不受其他環(huán)境因素影響；每艘船舶都有一個最小橋吊數(shù)和最大橋吊數(shù)的限制，最小橋吊數(shù)目一般由船公司決定，只有橋吊達(dá)到最小數(shù)目，作業(yè)才能開始，而最大橋吊數(shù)受船長限制；船舶在停泊過程中，作業(yè)一旦開始，則必須作業(yè)直至必須完全作業(yè)完畢，才能停止作業(yè)，不得中途停止作業(yè)。

下面定義相關(guān)集合、參數(shù)與決策變量。集合sl={1，2，…，sls}表示船舶集合，k∈sl表示其中一條船舶；sm={1，2，…，sms}表示泊位離散化的分段集合，i，i-，i+∈sm表示其中的分段；而 sn={1，2，…，sns}為計劃時間離散化的時段集合，j， j-， j+∈sn表示其中的時段。參數(shù)ek表示船k的預(yù)期到達(dá)時間；ak表示船k的總的橋吊作業(yè)時間，以單位橋時計算；bk表示船k的長度；sk表示船k的偏好泊位；c1k、c2k、c3k分別為船k偏離偏好泊位、推遲靠泊、延遲離港的單位懲罰成本；lk、uk分別表示可以分配給船k的最小橋吊數(shù)和最大橋吊數(shù)；c表示可用橋吊數(shù)的總數(shù)量；Ai， j表示時空點(diǎn)（i， j）是否被占用；Dj表示j時刻已被占用的橋吊數(shù)；M為充分大的正整數(shù)。在以上集合的基礎(chǔ)上，定義以下決策變量。xi， j，k表示（i， j）是否位于船舶k的靠泊計劃矩形區(qū)域內(nèi)，若是則為1，否則為0；zi， j，k表示如果（i， j）點(diǎn)為船舶k的靠泊計劃矩形的左下角；vkj表示船k在j時刻是否作業(yè)，若是則為1，否則為0；uki表示船k是否在i位置靠泊，若是則值為1，否則為0；Ykj表示j時刻分配給船k的橋吊數(shù)量；Ck表示集裝箱作業(yè)的完成時間，即當(dāng)Ykj>0時，取j的最大值+1；BLk、BRk分別表示船k停泊位置相對于偏好泊位左偏和右偏的長度；TEk、TLk分別表示船舶k遲于預(yù)期離港時間離港和遲于到港時間靠泊的時間差；DLk表示船舶k晚于預(yù)期離港時間的時間差。為建模和分析方便，引入以下變量，它們都可以直接通過以上變量和參數(shù)表示：

2.1 符號定義

（1）集合

1）為船舶集合，表示其中一條船舶。

2）為泊位離散化的分段集合，表示其中的分段。

3）為計劃時間離散化的時段集合，表示其中的時段。

（2）參數(shù)

1）：船的預(yù)期到達(dá)時間。

2）：船的總的橋吊作業(yè)時間，以單位橋時計算。

3）：船的長度。

4）：船預(yù)期離港時間。

5）：船的偏好泊位。

6）：船偏離偏好泊位的單位懲罰成本。

7）：船推遲靠泊的單位懲罰成本。

8）：船延遲離港的單位懲罰成本。

9）：可以分配給船的最少橋吊數(shù)量。

10）：能分配給船的最大橋吊數(shù)量，受船長限制。

11）：可用橋吊數(shù)的總數(shù)量。

12）：表示時空點(diǎn)是否被占用。

13）：表示時刻已被占用的橋吊數(shù)，可用橋吊數(shù)為。

14）：充分大的正整數(shù)。

（3）決策變量

1）：表示是否位于船舶的靠泊計劃矩形區(qū)域內(nèi)，若是則為1，否則為0。

2）：表示如果點(diǎn)為船舶的靠泊計劃矩形的左下角。

3）：表示船在時刻是否作業(yè)，若是則為1；否則，為0。

4）：表示船是否在位置靠泊，若是則值為1；否則，為0。

5）：表示時刻分配給船的橋吊數(shù)量。

6）：表示集裝箱作業(yè)的完成時間，即當(dāng)時，取的最大值+1。

7）：表示船停泊位置向左偏離偏好泊位的長度。

8）：表示船停泊位置向右偏離偏好泊位的長度。

9）：船舶遲于預(yù)期離港時間離港的時間差。

10）：船舶遲于到港時間進(jìn)行靠泊的時間差。

11）：表示船舶晚于預(yù)期離港時間的的時間差。

為建模和分析方便，引入以下變量，它們都可以直接通過以上變量和參數(shù)表示 。

1）：表示船的靠泊位置。

2）：表示船的靠泊時間。

3）：表示占用時空點(diǎn)的船。

1.1 模型構(gòu)建

DCBAP的優(yōu)化目標(biāo)包含兩方面：一是泊位的優(yōu)化，即?？坎次粦?yīng)該盡可能地靠近偏好泊位，以減少集裝箱從橋吊到后方堆場的移動時間，提高橋吊作業(yè)效率，降低作業(yè)成本；二是服務(wù)時間的優(yōu)化，即船舶入港后應(yīng)盡快靠泊作業(yè)，靠泊后盡可能在船公司規(guī)定的時間內(nèi)作業(yè)完畢并按時離港。針對這兩個目標(biāo)建立了最小化總懲罰成本的多目標(biāo)模型，旨在減少靠泊懲罰成本、靠泊等待時間和離港延遲時間。目標(biāo)函數(shù)通過式（1）～（4）定義；而約束函數(shù)通過式（5）～（29）定義。

其中：目標(biāo)函數(shù)式（1）為最小化懲罰成本函數(shù)，包括船舶?？坎次凰狡破貌次坏目偝杀?、船舶推遲靠泊的懲罰成本、延遲離港的懲罰成本，分別通過 （2）～（4）定義；式（5）和（6）約束了船的停泊位置偏離偏好泊位的水平距離；式（7）～（8）界定了船舶推遲靠停泊的時間差和計算延遲離泊的時間差；式（9）表示船舶必須在到港后才能靠泊；式（10）表示計算船舶離開時刻必須大于等于集裝箱作業(yè)完成時間；式（11）表示每一個時空點(diǎn)只能被一條船占用；式（12）表示可供分配的橋吊數(shù)受總橋吊數(shù)限制；式（13）約束了船的作業(yè)時間必須要大于等于總橋時；式（14）～（15）反映了作業(yè)的持續(xù)性，要求作業(yè)期間至少有一個橋吊為之服務(wù)，即不能中途停止作業(yè)；式（16）～（17）限制了可以給每條船分配的橋吊數(shù)受最大值和最小值限制；式（18）～（19）建立了Vk， j與Xk，i， j之間的關(guān)系；式（20）～（21）建立了Uk，i與Xk，i， j之間的關(guān)系；式（22）～（24）保證了船舶靠泊后占用時間和泊位上的連續(xù)性；式（25）保證了一條船只有一個參考點(diǎn)；式（26）～（29）保證了船舶靠泊計劃矩形內(nèi)的網(wǎng)格取值為1，矩形外的網(wǎng)格取值為0。

2 滾動調(diào)度方法

滾動調(diào)度方法是對大規(guī)模問題的分解策略，將原問題分解為規(guī)模較小的子問題來進(jìn)行求解，是解決大規(guī)模復(fù)雜問題的有效手段。劉越洋等[11]針對單機(jī)調(diào)度問題提出了一種滾動調(diào)度策略，有效解決了動態(tài)到達(dá)的工件在機(jī)器上有序加工的調(diào)度問題?？坎从媱澥且活惗嗵幚頇C(jī)任務(wù)調(diào)度[10]，能夠借鑒這一單機(jī)調(diào)度問題的滾動調(diào)度策略。在集裝箱碼頭作業(yè)過程中，船舶按照預(yù)定靠泊時間陸續(xù)到港，船舶按照抵達(dá)碼頭的先后順序，依次保存在待調(diào)度船舶集中等候調(diào)度。在滾動調(diào)度的操作過程中，將所有船舶分為己靠泊船舶集、待靠泊船舶集、未調(diào)度船舶集。其中，已靠泊船舶集指已完成裝卸作業(yè)或正在進(jìn)行裝卸作業(yè)的船舶；待靠泊船舶集指在調(diào)度中的船舶，尚未開始作業(yè)；未調(diào)度船舶集指已經(jīng)到港但調(diào)度計劃還未下達(dá)的船舶。每次滾動調(diào)度優(yōu)化時，按照一定規(guī)則將完成裝卸作業(yè)的船舶從窗口中移除，并將未調(diào)度船舶集補(bǔ)充進(jìn)船舶窗口中，運(yùn)用優(yōu)化算法對當(dāng)前窗口船舶進(jìn)行優(yōu)化，得到該靜態(tài)調(diào)度區(qū)間的調(diào)度方案[10]。

為了在滾動調(diào)度過程中，更新已靠泊船舶的調(diào)度信息使之成為待靠泊船舶調(diào)度的參數(shù)，在式（1）～（29）確定的DCBAP模型的基礎(chǔ)上，建立如式（30）～（32）所示的新模型。其中，式（31）拓展式（11）中對于時空點(diǎn)的占位約束，參數(shù)A用于表示以靠泊船舶的占位情況，如果已經(jīng)占位則為1，否則為0。參數(shù)A用于設(shè)置前期滾動調(diào)度中已被占用（“凍結(jié)”）的時空點(diǎn)式（32）拓展式（12）的定義，引入D計算每個時段已經(jīng)被已靠泊船舶占用的橋吊數(shù)量，從而更新每個時段的可用橋吊數(shù)量配置。參數(shù)D用于設(shè)置前期滾動調(diào)度結(jié)果中每個時刻已被占用的橋吊數(shù)目。

約束函數(shù)式（2）～（10）和約束函數(shù)式（13）～（29）。

滾動調(diào)度方法將動態(tài)調(diào)度過程分解為一系列的靜態(tài)調(diào)度窗口，對于各個窗口進(jìn)行優(yōu)化獲得最優(yōu)解，然后平移窗口并更新新窗口中優(yōu)化問題的參數(shù)。平移間距和滾動窗口寬度是滾動調(diào)度的兩個基本因素。平移間距就是當(dāng)前窗口與下一窗口之間的間隔，一般來說，平移間距越短，滾動優(yōu)化結(jié)果越接近于全局優(yōu)化，但是滾動優(yōu)化的迭代次數(shù)越大、計算時間越長。滾動優(yōu)化窗口是第t次滾動時未調(diào)度部分內(nèi)前k個船舶的集合，定義為k（t），k是此滾動調(diào)度策略的滾動優(yōu)化窗口的寬度參數(shù)，決定滾動窗口大小。當(dāng)k（t）是常數(shù)時，只有最后一個滾動窗口的船舶個數(shù)可能會小于k，其余滾動窗口的船舶個數(shù)均等于k。滾動窗口越小，每次調(diào)度的船數(shù)目越少，調(diào)度模型的計算性能越高，但是滾動迭代次數(shù)越大，同時全局優(yōu)化程度也會越低。

在t步的滾動結(jié)果中，根據(jù)調(diào)度結(jié)果中船舶的開始作業(yè)時間排序，取前λ個船舶凍結(jié)。λ為滾動調(diào)度策略的凍結(jié)窗口的長度，即窗口的平移間距。這λ個船舶的調(diào)度并入前（t-1）步的已調(diào)度部分S（t）構(gòu)成下一滾動步驟（t+1）的已調(diào)度部分V（t），k（t）內(nèi)未被凍結(jié)的剩余船舶包含在V（t）的補(bǔ)集中。然后從該補(bǔ)集中根據(jù)靠泊時間排序選擇前k個船舶組成新的滾動窗口k（t+1），如果剩余船舶數(shù)量少于k，則取全部剩余船舶。當(dāng)V（t）包含所有船舶，即所有船舶都已經(jīng)被調(diào)度，則滾動結(jié)束，最后一個滾動窗口內(nèi)的優(yōu)化調(diào)度結(jié)果全部執(zhí)行。

綜合以上滾動調(diào)度策略的研究，建立連續(xù)泊位與橋吊的滾動調(diào)度算法流程如下。

步驟1 將所有需要調(diào)度的船舶按照到港時間先后排序。并初始化總船舶集合sl，令t=1。

步驟2 初始化已調(diào)度船舶集V（t）=，未調(diào)度船舶集V（t）=sl；根據(jù)集合V（t）中按預(yù)期靠泊時間排序的船舶序列，選擇前k條船舶，構(gòu)成滾動船舶集k（t），并更新V（t）=V（t）＼k（t）；根據(jù)V（t）中已靠泊船舶對時空點(diǎn)的占位情況更新參數(shù)A；根據(jù)V（t）中已靠泊船舶在每個時段已經(jīng)占用的橋吊數(shù)量更新參數(shù)D。

步驟3 根據(jù)式（30）～（32）確定的模型，設(shè)置slk（t），求解模型，確定k（t）中船舶的靠泊計劃；根據(jù)開始時間排序，得到前λ條船舶作為新的凍結(jié)船舶，合并已靠泊船舶集合V（t）得到V（t+1）；而剩余的（k-λ）條船舶則與未調(diào)度船舶V（t）合并得到V（t+1）。

步驟4 如果V=sls，即所有船舶都已經(jīng)調(diào)度，則停止執(zhí)行并返回；否則，更新t=t+1，轉(zhuǎn)到步驟2。

3 算例仿真

考慮一個周期48h，泊位碼頭長1200m的泊位橋吊集成調(diào)度計劃，以50m為單位對岸線空間離散化，以1h時間單位對計劃時間離散化。為48h內(nèi)到港的20條船舶安排靠泊計劃，在初始狀態(tài)沒有任何已靠泊船只。每條船的懲罰成本系數(shù)均設(shè)置為c1*=100、c2*=200和c3*=300，總橋吊數(shù)c=9，取滾動窗口大小為k=5，平移間距為λ=2，其他參數(shù)的配置見表1。船舶到達(dá)時間ek取自區(qū)間[1，36]的均勻分布，船舶偏好位置sk取自區(qū)間[1，20]的均勻分布，船舶離開時間dk取自區(qū)間[8，14]+ek的均勻分布，船舶作業(yè)時間ak取自區(qū)間[10，30]的均勻分布。

根據(jù)表1中數(shù)據(jù)（表中下劃線表示當(dāng)前實(shí)驗(yàn)下的最優(yōu)解），采用Cplex作為混合整數(shù)規(guī)劃模型求解引擎，采用C#編寫滾動調(diào)度算法進(jìn)行求解，得到48h內(nèi)20條船的靠泊計劃如圖1所示。圖1中給出每條船舶的靠泊時間、離泊時間、靠泊位置，以及給出了所分配的橋吊數(shù)量。每個矩形代表船舶靠泊所占據(jù)的時空區(qū)間，數(shù)字代表該時刻分配給該船的橋吊數(shù)量。

滾動策略的主要設(shè)計參數(shù)是滾動窗口寬度k和平移間距λ。表1是調(diào)整k與λ得到的一系列實(shí)驗(yàn)的結(jié)果。當(dāng)λ=4時，隨著k從5遞增到8，總的懲罰成本先遞增后遞減，在窗口船舶數(shù)為7時，目標(biāo)函數(shù)值最小，達(dá)到λ=15600。k從5增加到7時，隨著滾動窗口的增大，總的懲罰成本減小。因?yàn)闈L動窗口越大，每次調(diào)度的船舶數(shù)量越多，局部調(diào)度越接近于全局優(yōu)化的結(jié)果。總的懲罰成本減少主要是船舶延遲靠泊成本與延遲離港成本的減少。由于延遲靠泊與延遲離港帶來的懲罰遠(yuǎn)大于偏離偏好泊位的懲罰成本，所以當(dāng)窗口數(shù)增大以后，優(yōu)化結(jié)果更多地偏向于以偏離泊位或者分配更多的橋吊數(shù)替代延遲，使總的懲罰成本更小。同時，隨著k值增大，橋吊數(shù)的利用率更高，橋吊的波動率（即每時刻使用的橋吊個數(shù)方差值）更小，橋吊數(shù)目更加均衡，橋吊的運(yùn)營成本相對更低，但總的在港時間略有增加。這說明，港口滾動計劃需要港口運(yùn)營人員與船公司協(xié)作共贏，平衡多方利益，以達(dá)最優(yōu)成本。

在滾動調(diào)度中，平移間距越小，雖然滾動次數(shù)增多，但調(diào)度結(jié)果也相對更為優(yōu)化。在表1中，當(dāng)船舶數(shù)量分別為5、7和8時，從四個目標(biāo)函數(shù)和總在港時間看，λ越小，綜合結(jié)果越優(yōu)。例如，對k=7的計劃，λ從5到4，f、f 1、f 2、f 3和總在港時間的優(yōu)化比率分別為13.8%、25%、13.7%、0%和5%。其他實(shí)驗(yàn)組合也都有明顯的優(yōu)化效果。

滾動窗口從7增加到8時，滾動次數(shù)也同時增加，此時，滾動次數(shù)增加帶來的影響大于滾動窗口增加的影響，總的懲罰成本增加。滾動次數(shù)與滾動窗口的大小負(fù)相關(guān)，與凍結(jié)船舶數(shù)量正相關(guān)。因此，碼頭在做滾動計劃時，需要通過合理匹配滾動窗口和凍結(jié)船舶的窗口大小，以使得滾動計劃性能最優(yōu)。

通過控制凍結(jié)船舶的數(shù)量進(jìn)行研究，從表1可以看出，隨著凍結(jié)船舶的增加，懲罰成本增加，滾動性能降低。這是由于系統(tǒng)靜態(tài)部分的影響。凍結(jié)船舶數(shù)量增加，每次調(diào)度前系統(tǒng)的靜態(tài)部分增加。即由前一次決策產(chǎn)生的調(diào)度，已經(jīng)調(diào)度但尚未完成部分，也會降低系統(tǒng)的性能，影響優(yōu)化結(jié)果。因?yàn)殪o態(tài)的部分并未參與后一次的局部優(yōu)化，導(dǎo)致局部優(yōu)化并非局部最優(yōu)。凍結(jié)船舶數(shù)量設(shè)置得過小，又會導(dǎo)致滾動次數(shù)過多，計算時間過長。在具體調(diào)度中，可通過合理設(shè)置凍結(jié)船舶的數(shù)量，減少靜態(tài)部分的影響，控制計算時間，提高滾動調(diào)度的整體性能。

船舶的到達(dá)耦合度對于滾動效率也有較大影響。由圖2所示，在不同滾動窗口下，進(jìn)行第三次和第五次滾動調(diào)度時，滾動窗口內(nèi)船舶懲罰成本都急劇增加，滾動調(diào)度效率急劇下降。因?yàn)榍耙粫r期船舶到達(dá)耦合度較高，船舶到達(dá)較為密集，集裝箱操作量大，使得橋吊操作時間延長，長時間占用大量橋吊和泊位資源，以至于后一滾動期進(jìn)行滾動調(diào)度時，橋吊資源和橋吊資源缺乏，后續(xù)船舶不得不延遲靠泊和離港延遲，滾動調(diào)度效率受到影響，懲罰成本增加。

影響滾動調(diào)度的內(nèi)因主要在于滾動窗口大小、凍結(jié)船舶數(shù)量以及滾動次數(shù)，因此需要選擇合適的滾動窗口大小以及凍結(jié)船舶數(shù)量來提高總體性能。在選擇窗口長度時：一方面要使窗口要足夠大，使得滾動窗口內(nèi)的船舶數(shù)量足夠多，盡量讓所有船舶窗口的局部最優(yōu)調(diào)度方案接近于全局調(diào)度方案，從而降低碼頭的運(yùn)營成本，提高碼頭的服務(wù)水平；另一方面，窗口大小的選擇也需要考慮到優(yōu)化時間，若船舶過多，局部優(yōu)化時間過長，可能會延誤船舶的靠泊，影響到碼頭的正常運(yùn)營，反而增加了時間成本。所以，必須對滾動窗口的大小進(jìn)行合理控制，提高碼頭生產(chǎn)系統(tǒng)的作業(yè)效率。在此基礎(chǔ)上，需要選擇合理的凍結(jié)船舶數(shù)量，使?jié)L動調(diào)度性能最優(yōu)。

表2中的6個實(shí)例中，采用滾動調(diào)度時，都求得了最優(yōu)值，而一次調(diào)度在船舶規(guī)模增長到14條時，就已經(jīng)內(nèi)存溢出，無法計算出結(jié)果。表明較之于一次調(diào)度，滾動調(diào)度能夠大大降低計算難度，解決大規(guī)模問題。

船舶總量從10增長到15時，僅從優(yōu)化結(jié)果上看，滾動調(diào)度與一次調(diào)度優(yōu)化結(jié)果相近，說明滾動調(diào)度的效果較好。由圖3可以看出一次調(diào)度與滾動調(diào)度的運(yùn)行時間增長趨勢，隨著船舶規(guī)模的增大，一次調(diào)度的計算時間急劇增長，船舶總量為10時，一次調(diào)度的時間為滾動調(diào)度的近兩倍，而當(dāng)規(guī)模達(dá)到13時，一次調(diào)度的時間是滾動調(diào)度時間的25倍，一次調(diào)度的時間消耗幾乎呈指數(shù)增長，而當(dāng)船舶規(guī)模增長到14條時，在當(dāng)前機(jī)器上就已經(jīng)無法計算出結(jié)果。相對而言，滾動策略的計算時間增長緩慢上升，與數(shù)量幾乎呈正比關(guān)系。這是因?yàn)橐淮握{(diào)度需要一次性搜索大量節(jié)點(diǎn)，消耗的CPU和內(nèi)存資源較大。滾動調(diào)度計算效率較高，能在有限的時間內(nèi)完成大規(guī)模的優(yōu)化。

雖然在上文算例中，規(guī)模僅為20條船，但是由于滾動策略的計算時間與數(shù)量幾乎成正比關(guān)系，因此采用本文提出的滾動調(diào)度方法，能夠適應(yīng)規(guī)模無限大的算例，滿足實(shí)際應(yīng)用的需要。在根據(jù)上文模型和算法進(jìn)行的實(shí)驗(yàn)中，本文已經(jīng)演算了規(guī)模從40～200條船，計劃周期從48h到400h的算法，均發(fā)現(xiàn)計算性能與船舶數(shù)量呈近似線性關(guān)系。

4 結(jié)語

為解決大規(guī)模的集裝箱碼頭泊位與橋吊集成調(diào)度問題，本文提出了基于滾動調(diào)度策略的優(yōu)化方法，建立了連續(xù)泊位下以船總在港懲罰成本最小的混合整數(shù)規(guī)劃模型。算例分析結(jié)果表明該方法可以解決大規(guī)模的船舶調(diào)度問題，計算性能與船舶數(shù)量呈近似線性關(guān)系。在滾動調(diào)度過程中，滾動窗口寬度和平移間距等滾動策略設(shè)計參數(shù)對于滾動調(diào)度的優(yōu)化能力和整體性能有著較大影響。隨著滾動窗口的增大，調(diào)度結(jié)果更加優(yōu)化，運(yùn)算時間也指數(shù)增長。隨著平移間距減小，滾動次數(shù)增多，調(diào)度結(jié)果也會更優(yōu)。在本文的算例中，當(dāng)k=7，λ=4時，獲得的解最優(yōu)。同時，船舶預(yù)期靠泊時間集中情況下，滾動調(diào)度的效率會降低。實(shí)際調(diào)度中，需考量實(shí)際情況，對滾動窗口寬度和平移間距進(jìn)行組合實(shí)驗(yàn)和選擇，平衡滾動調(diào)度策略的優(yōu)化能力和計算性能，提高碼頭靠泊計劃的效率，降低碼頭的運(yùn)營成本和提高碼頭的服務(wù)水平。本文滾動調(diào)度策略的設(shè)計，利用了DCBAP中船舶預(yù)期靠泊時間的動態(tài)特征，相對于文獻(xiàn)[14]建立的模型而言，雖然計算規(guī)?？梢源蟠笸卣?，但是沒有考慮船舶提前抵達(dá)并進(jìn)行作業(yè)安排的可能性。另外，采用混合整數(shù)規(guī)劃模型的計算引擎雖然便于研究滾動調(diào)度策路的有效性，但是其已然成為制約計算性能的關(guān)鍵，下一步的研究是設(shè)計有效的子問題啟發(fā)式算法融入滾動算法，進(jìn)一步提高優(yōu)化能力和計算性能，以滿足實(shí)際應(yīng)用的需要。

參考文獻(xiàn)：

[1] VIS I F A， DE KOSTER R， Transshipment of containers at a container terminal：An overview[J]. European Journal of Operational Research， 2003，147（1）： 1-16.

[2] KIM K H， MOON K C. Berth scheduling by simulated annealing[J]. Transportation Research Part B： Methodological， 2003， 37（6）： 541-560.

[3] PARK Y M， KIM K H. Berth scheduling for container terminal by using a subgradient optimization technique[J]. Journal of Operation Research， 2002， 53（9）： 1054-1062.

[4] IMAI A， NISHIMURAA E， PAPADIMITRIOU S. The dynamic berth allocation problem for a container port[J]. Transportation Research Part B： Methodological， 2001， 35（4）： 401-417.

[5] IMAI A， CHEN H C， NISHIMUR E， et al. The simultaneous berth and quay crane allocation problem[J]. Transportation Research Part E： Logistics and Transportation Review， 2008， 44（5）： 900-920.

[6] LEGATO P， GULLI D， TRUNFIO R. The quay crane deployment problem at a maritime container terminal[EB/OL].[20130120]. http：///conf/ecms2008/ecms2008%20CD/ecms2008%20pdf/ibsECMS2008_0106.pdf.

[7] ZHEN L， LEE L H， CHEW E P. A decision model for berth allocation under uncertainty[J]. European Journal of Operational Research， 2012， 212（1）： 54-68.

[8] SAMMARRA M， CORDEAU J F， LAPORTE G， et al. A tabu search heuristic for the quay crane scheduling problem[J]. Journal of Scheduling， 2007， 10（4/5）： 327-336.

[9] TAVAKKOLIMOGHADDAM R， MAKUI A， BAZZAZI M， et al. An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports[J]. Computers and Industrial Engineering， 2009， 56（1）： 241-248.

[10] 楊春霞， 王諾.基于多目標(biāo)遺傳算法的集裝箱碼頭泊位岸橋分配問題研究[J]. 計算機(jī)應(yīng)用研究， 2010，27（5）： 1720-1725.

[11] 劉越洋，席裕.基于兩步滾動的單機(jī)調(diào)度算法研究[J]. 計算機(jī)工程， 2004，30（24）： 144-147.

[12] RAA B， DULLAERT B R W， van SCHAEREN R. An enriched model for the integrated berth allocation and quay crane assignment problem[J]. Expert Systems with Applications， 2011， 38（11）： 14136-14147.

[13] 何軍良， 宓為建，謝塵，等.基于分布式混合遺傳算法的動態(tài)泊位分配策略與仿真[J].上海海事大學(xué)學(xué)報， 2008，29（2）： 52-57.

篇6

關(guān)鍵詞:遺傳算法;GA;進(jìn)化;最優(yōu)化

中圖分類號:TP18 文獻(xiàn)標(biāo)識碼:A文章編號:1007-9599 (2010) 04-0000-01

Summary on Genetic Algorithm

Gao Ying

(Shandong Industry Vocational College,Zibo256414,China)

Abstract:This article has summarized the genetic algorithm basic principle and the characteristic, as well as in each domain application situation.

Keyword:Genetic algorithm;Evolution;Optimization

一、引言

在人工智能領(lǐng)域中,有不少問題需要在復(fù)雜而龐大的搜索空間中尋找最優(yōu)解或準(zhǔn)最優(yōu)解。在計算此類問題時,若不能利用問題的固有知識來縮小搜索空間則會產(chǎn)生搜索的組合爆炸。因此,研究能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識并自適應(yīng)地控制搜索過程從而得到最優(yōu)解的通用搜索算法一直是令人矚目的課題[1]。遺傳算法簡稱就是這類特別有效的算法之一。

二、遺傳算法基本原理

遺傳算法是建立在自然選擇和群眾遺傳學(xué)機(jī)理基礎(chǔ)上的,具有廣泛適應(yīng)性的搜索方法。遺傳算法搜索結(jié)合了達(dá)爾文適者生存和隨機(jī)信息交換的思想,適者生存消除了解中不適應(yīng)因素,隨機(jī)信息交換利用了原有解中已知的知識,從而有力地加快了搜索過程。

遺傳算法的基本思想[2]:遺傳算法是從代表問題可能潛在解集的一個種群開始的,一個種群由經(jīng)過基因編碼的一定數(shù)目的個體組成,初始種群產(chǎn)生之后,按照適者生存和優(yōu)勝劣汰的原理,逐步演化產(chǎn)生出越來越好的近似解。在每一代,根據(jù)問題域中個體的適應(yīng)度大小挑選個體,并借助自然遺傳學(xué)的遺傳算子進(jìn)行交叉和變異,產(chǎn)生出代表新的解集的種群。這個過程將導(dǎo)致種群向自然進(jìn)化一樣的后代種群比前代更加適應(yīng)環(huán)境,末代種群中的最優(yōu)個體經(jīng)過解碼,可以作為問題近似最優(yōu)解。

三、遺傳算法的主要特點(diǎn)及改進(jìn)

隨著問題種類的不同以及問題規(guī)模的擴(kuò)大,要尋求一種能以有限的代價來解決搜索和優(yōu)化的通用方法,遺傳算法正是為我們提供的一個有效的途徑,它不同于傳統(tǒng)的搜索和優(yōu)化方法。主要區(qū)別在于:

(1)自組織、自適應(yīng)和自學(xué)習(xí)性。

(2)遺傳算法的本質(zhì)并行性。

(3)遺傳算法不要求導(dǎo)或其他輔助知識,而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)。

(4)遺傳算法強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則,而不是確定的轉(zhuǎn)換規(guī)則。

(5)遺傳算法可以更加直接地應(yīng)用。

(6)遺傳算法對給定問題,可以產(chǎn)生許多的潛在解,最終選擇可以由使用者確定。

其中對全局信息有效利用和隱含并行性是遺傳算法的兩大特點(diǎn),同時遺傳算法對問題本身的限制較少,因而具有很強(qiáng)的通用優(yōu)化能力。但遺傳算法容易過早收斂,這樣就會使其他個體中的有效基因不能得到有效復(fù)制,最終丟失;而且在進(jìn)化后期染色體之間的差別極小,整個種群進(jìn)化停滯不前,搜索效率較低,這樣就會導(dǎo)致搜索到的結(jié)果不是全局最優(yōu)解。

自從1975年J.H.Holland系統(tǒng)地提出遺傳算法的完整結(jié)構(gòu)和理論以來,眾多學(xué)者一直致力于推動遺傳算法的發(fā)展,對編碼方式、控制參數(shù)的確定、選擇方式和交叉機(jī)理等進(jìn)行了深入的探究,其基本途徑概括起來有以下幾個方面[3]:

(1)改變遺傳算法的組成部分或使用技術(shù);

(2)采用混合遺傳算法;

(3)采用動態(tài)自適應(yīng)技術(shù),在進(jìn)化過程中調(diào)整算法控制參數(shù)和編碼粒度;

(4)采用非標(biāo)準(zhǔn)的遺傳操作算子;

(5)采用并行遺傳算法等。

四、遺傳算法的應(yīng)用領(lǐng)域

遺傳算法經(jīng)過幾十年的發(fā)展,逐漸被人們接受和運(yùn)用,遺傳算法的應(yīng)用研究比理論研究更為豐富,下面是遺傳算法的一些主要應(yīng)用領(lǐng)域[4]:

(1)優(yōu)化問題:優(yōu)化問題包括函數(shù)優(yōu)化和組合優(yōu)化兩種。函數(shù)優(yōu)化是遺傳算法的經(jīng)典領(lǐng)域,也是對遺傳算法進(jìn)行性能評價的常用算例。對于組合優(yōu)化,隨著問題規(guī)模的擴(kuò)大,搜索空間急劇擴(kuò)大,這類復(fù)雜問題,人們已經(jīng)意識到把精力放在尋找其滿意解上。實(shí)踐證明,遺傳算法對于組合優(yōu)化中的NP完全問題非常有效。

(2)生產(chǎn)調(diào)度問題:生產(chǎn)調(diào)度問題在許多情況下所建立起來的數(shù)學(xué)模型難以精確求解,即使經(jīng)過一些簡化之后可以進(jìn)行求解,也會因簡化太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。遺傳算法已成為解決復(fù)雜調(diào)度問題的有效工具,在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。

(3)自動控制:在自動控制領(lǐng)域中許多與優(yōu)化相關(guān)的問題需要求解,遺傳算法的應(yīng)用日益增加,并顯示了良好的效果。例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、基于遺傳算法的參數(shù)辨識、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學(xué)習(xí),都顯示了遺傳算法在這些領(lǐng)域中應(yīng)用的可能性。

(4)機(jī)器人智能控制:機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng),而遺傳算法的起源就來自于對人工自適應(yīng)系統(tǒng)的研究。例如遺傳算法已經(jīng)在移動機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動軌跡規(guī)劃、機(jī)器人逆運(yùn)動學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行動協(xié)調(diào)等方面得到研究和應(yīng)用。

(5)圖像處理和模式識別:圖像處理和模式識別是計算機(jī)視覺中的一個重要研究領(lǐng)域。在圖像處理過程中,如掃描、特征提取、圖像分割等不可避免地產(chǎn)生一些誤差,這些誤差會影響到圖像處理和識別的效果。如何使這些誤差最小是使計算機(jī)視覺達(dá)到實(shí)用化的重要要求。遺傳算法在圖像處理中的優(yōu)化計算方面是完全勝任的。目前已在圖像恢復(fù)、圖像邊緣特征提取、幾何形狀識別等方面得到了應(yīng)用。

五、總結(jié)

遺傳算法作為一種非確定性的模擬自然演化的學(xué)習(xí)過程的求解問題方法,在很多領(lǐng)域具有廣泛的應(yīng)用價值,但其在很多方面有待于進(jìn)一步研究、探討和完善?？梢灶A(yù)期,隨著計算機(jī)技術(shù)的進(jìn)步和生物學(xué)研究的深入,遺傳算法在操作技術(shù)和方法上將更通用、更有效。

參考文獻(xiàn):

[1]王煦法.遺傳算法及其應(yīng)用.小型微型計算機(jī)系統(tǒng),1995,2

篇7

關(guān)鍵詞 網(wǎng)絡(luò)控制系統(tǒng)；信息調(diào)度；靜/動態(tài)調(diào)度；混合調(diào)度；調(diào)度與控制協(xié)同設(shè)計

1　引言

網(wǎng)絡(luò)控制系統(tǒng)（Network Control System，NCS）是指傳感器、控制器和執(zhí)行器通過網(wǎng)絡(luò)形成的閉環(huán)反饋控制系統(tǒng)。目前，大部分關(guān)于NCS的研究針對NCS存在的問題和特性建立系統(tǒng)模型、分析系統(tǒng)穩(wěn)定性、給出控制方法和控制規(guī)律，以保證系統(tǒng)具有良好的穩(wěn)定性和高質(zhì)量的控制性能。然而NCS的性能不僅依賴于控制策略及控制規(guī)律的設(shè)計，而且還受到網(wǎng)絡(luò)通信和網(wǎng)絡(luò)資源的限制。信息調(diào)度盡量避免網(wǎng)絡(luò)中信息的沖突和擁塞現(xiàn)象的發(fā)生，從而大大提高了網(wǎng)絡(luò)控制系統(tǒng)的服務(wù)性能。

2 　NCS中的信息特征與信息調(diào)度概念

在NCS中網(wǎng)絡(luò)傳輸?shù)男畔⒅饕譃閮深悾簩?shí)時性信息和非實(shí)時性信息[3]。實(shí)時性信息對時間要求非?？量蹋绻谝?guī)定時間的上限內(nèi)某一信息未能起作用，則該信息將被丟棄，啟用最新的信息。而在NCS信息調(diào)度策略中主要調(diào)度兩類數(shù)據(jù)信息：周期性信息和非周期性信息。周期性信息是一種實(shí)時性信息，一般要求在傳輸周期時間內(nèi)必須傳送給目標(biāo)節(jié)點(diǎn)，周期性信息也被稱為時間觸發(fā)信息或者同步信息。非周期性信息是指節(jié)點(diǎn)間的請求服務(wù)等信息，它們的發(fā)生時刻是隨機(jī)的，非周期性信息也被稱為事件觸發(fā)信息、異步信息或者隨機(jī)性信息。

此外，在NCS信息調(diào)度中不能忽視突發(fā)性信息，突發(fā)性信息指一些事先無法預(yù)知的突發(fā)性的或者隨機(jī)的事件（例如報警信號、異常處理等），這類信息必須在一定時間內(nèi)給予處理，否則系統(tǒng)可能出現(xiàn)異常甚至癱瘓。

在網(wǎng)絡(luò)控制系統(tǒng)中，信息調(diào)度發(fā)生在應(yīng)用層，即傳感器、控制器與執(zhí)行器之間信息傳遞的過程中。當(dāng)系統(tǒng)網(wǎng)絡(luò)中某節(jié)點(diǎn)發(fā)生數(shù)據(jù)傳輸碰撞時，信息調(diào)度規(guī)定節(jié)點(diǎn)的優(yōu)先發(fā)送次序、發(fā)送時刻和時間間隔，以避免網(wǎng)絡(luò)沖突。

在NCS中，如果網(wǎng)絡(luò)控制系統(tǒng)的所有數(shù)據(jù)傳輸都能在任務(wù)時限內(nèi)完成，則稱網(wǎng)絡(luò)控制系統(tǒng)的傳輸是可調(diào)度的。

3　典型的NCS信息調(diào)度算法

目前對網(wǎng)絡(luò)控制系統(tǒng)中信息調(diào)度的研究主要分為調(diào)度與控制的分開設(shè)計和調(diào)度與控制的協(xié)同設(shè)計。

3.1　調(diào)度與控制的分開設(shè)計

在NCS的研究中，一類研究是針對通信網(wǎng)絡(luò)，研究提高網(wǎng)絡(luò)服務(wù)質(zhì)量的信息調(diào)度方法；另一類研究是在一定的網(wǎng)絡(luò)信息調(diào)度方法基礎(chǔ)上，研究提高NCS性能的控制方法。因此，信息調(diào)度方法對改善NCS性能起著很大的作用。

根據(jù)信息對實(shí)時性的要求，信息調(diào)度分為靜態(tài)調(diào)度（又稱離線調(diào)度）、動態(tài)調(diào)度（又稱在線調(diào)度）和混合調(diào)度。

3.1.1　靜態(tài)優(yōu)先級調(diào)度

目前靜態(tài)調(diào)度算法很多，本文著重介紹以下幾種典型的算法以及算法的改進(jìn)。

速率單調(diào)靜態(tài)優(yōu)先級調(diào)度 (Rate Monotonic Scheduling Model) 算法的調(diào)度優(yōu)先級由任務(wù)周期確定，在任務(wù)周期等于時限的同步實(shí)時任務(wù)系統(tǒng)中是最佳靜態(tài)調(diào)度算法。但是該算法具有調(diào)度判定具有指數(shù)時間復(fù)雜度、對任務(wù)的執(zhí)行周期限制的過于嚴(yán)格、只能處理具有固定周期的任務(wù)等缺點(diǎn)。鑒于上述缺點(diǎn)Lehoczky等[23]提出了擴(kuò)大調(diào)度可行性條件的RM算法。Sha等[22]考慮到任務(wù)的阻塞，給出了非搶占服務(wù)方式下RM算法的可調(diào)度條件。葉明等[5]基于RM算法提出了一種新的實(shí)時調(diào)度算法(Hard Real-time Communication Scheduler，HRTCS)。文遠(yuǎn)保等[4]針對任務(wù)的周期和調(diào)度優(yōu)先級關(guān)系不固定的流媒體提出了改進(jìn)的RM算法。

截至?xí)r間單調(diào)調(diào)度模型(Deadline Monotonic Scheduling Model )策略的任務(wù)優(yōu)先級由任務(wù)時限來決定。該調(diào)度算法要防止任務(wù)越過其時限而得不到調(diào)度，從而影響系統(tǒng)的實(shí)時性。當(dāng)任務(wù)周期和時限相同或者所有同步周期性任務(wù)時，DM算法都是最佳靜態(tài)調(diào)度算法。

由Hong等提出的基于時間窗的靜態(tài)帶寬調(diào)度算法避免了數(shù)據(jù)在網(wǎng)絡(luò)傳輸過程中產(chǎn)生干擾和數(shù)據(jù)沖突。Hong等還將該調(diào)度方法應(yīng)用于循環(huán)服務(wù)型NCS和CAN 網(wǎng)下的NCS中。

劉魯源[6]等鑒于該調(diào)度方法只限于調(diào)度網(wǎng)絡(luò)中的周期數(shù)據(jù)，提出基于同步相和異步相的時間窗調(diào)度算法，使非周期數(shù)據(jù)也可以采用該基于時間窗的靜態(tài)調(diào)度算法。

3.1.2　動態(tài)優(yōu)先級調(diào)度

在動態(tài)優(yōu)先級調(diào)度算法中，任務(wù)的時間約束關(guān)系并沒有完全確定，新任務(wù)的到達(dá)時間是未知的。下面介紹幾種經(jīng)典的動態(tài)優(yōu)先級調(diào)度算法。

Liu和Layland提出的時限最早的任務(wù)優(yōu)先調(diào)度（Earliest deadline first scheduling），任務(wù)優(yōu)先級是任務(wù)時限與任務(wù)執(zhí)行時刻的差，該算法對同步周期任務(wù)組是最佳的動態(tài)調(diào)度算法。鑒于EDF是搶占式調(diào)度算法，任務(wù)間的切換時需要大量開銷。Baker[12]給出了非搶占士服務(wù)方式下EDF算法的可調(diào)度性條件。張惠娟等[11]提出了一種基于EDF算法的優(yōu)先級驅(qū)動實(shí)時調(diào)度算法，較大程度地克服了EDF算法在多處理器系統(tǒng)中的調(diào)度缺點(diǎn)。劉懷等[10]提出了基于EDF算法的容錯調(diào)度算法。張奇智等[7]采用非中斷的EDF調(diào)度方法來改善周期性數(shù)據(jù)幀的端到端延遲。洪艷偉等[1]提出了分別在簡單模型上和復(fù)雜模型上如何判定實(shí)時任務(wù)的可行性。

最小松弛優(yōu)先調(diào)度(Least laxity first)和EDF算法可看作同類型的調(diào)度算法，任務(wù)優(yōu)先級是完成時限和任務(wù)執(zhí)行時刻的差再減去周期任務(wù)的執(zhí)行時間。LLF算法盡量避免了長周期任務(wù)的頻繁等待、執(zhí)行，具有較小的抖動性。

最大誤差優(yōu)先—嘗試一次丟棄(most error first-try once discard)是Walsh 等[8]人提出的基于在線獲取的網(wǎng)絡(luò)誘導(dǎo)傳輸誤差和動態(tài)分配網(wǎng)絡(luò)帶寬的調(diào)度算法。

Otanez 等[9]人提出的基于死區(qū)的動態(tài)調(diào)度在確保系統(tǒng)性能的基礎(chǔ)上動態(tài)地丟棄一定比率的數(shù)據(jù)，以減輕網(wǎng)絡(luò)的負(fù)荷。但是當(dāng)多個獲準(zhǔn)訪問網(wǎng)絡(luò)的數(shù)據(jù)包同時競爭網(wǎng)絡(luò)資源時，該策略不能確定數(shù)據(jù)包發(fā)送的優(yōu)先級。

基于業(yè)務(wù)平滑的動態(tài)調(diào)度是Kewon等利用業(yè)務(wù)平滑的技術(shù)控制Ethernet網(wǎng)的通信量，通過在Ethernet 網(wǎng)的UDP( TCP/ IP) 層和MAC 層插入定速率業(yè)務(wù)平滑器和自適應(yīng)業(yè)務(wù)平滑器以限定MAC 層數(shù)據(jù)包的到達(dá)速率，并且保證網(wǎng)絡(luò)誘導(dǎo)時延的有界性，從而提高網(wǎng)絡(luò)的服務(wù)質(zhì)量.

Cena等提出的優(yōu)先級提升—分布式優(yōu)先級排隊(duì)調(diào)度( PP-DPQ)可以保證實(shí)時數(shù)據(jù)傳輸最大間隔具有確定上界，非實(shí)時數(shù)據(jù)在傳輸中公平地競爭網(wǎng)絡(luò)資源。

基于時間窗的動態(tài)調(diào)度（Dynamic Time Window）是Raja對基于時間窗的靜態(tài)調(diào)度算法進(jìn)行改進(jìn)，提出優(yōu)先級循環(huán)服務(wù)和動態(tài)時間窗的帶寬分配策略。

模糊動態(tài)調(diào)度是白濤[13]等將模糊控制理論引入到NCS 信息調(diào)度中，利用基于IF2THEN 規(guī)則的模糊邏輯確定數(shù)據(jù)傳輸?shù)膬?yōu)先級。

3.1.3　混合調(diào)度

Zuberi等針對CAN 下網(wǎng)絡(luò)控制系統(tǒng)，提出混合通信調(diào)度(MTS)策略。在設(shè)計調(diào)度策略時，考慮到數(shù)據(jù)實(shí)時性要求不同，可以分別采用不同的調(diào)度策略，以提高網(wǎng)絡(luò)資源的可調(diào)度性。Tabuada等[27]給出的退火控制任務(wù)的事件觸發(fā)實(shí)時調(diào)度是基于有反饋事例的事件觸發(fā)調(diào)度器，并且給出了它如何保證系統(tǒng)性能的條件。

3.2　調(diào)度與控制的協(xié)同設(shè)計

目前關(guān)于控制與調(diào)度共同設(shè)計成為研究熱點(diǎn)受到越來越多的重視，大體可分為開環(huán)調(diào)度和反饋控制實(shí)時調(diào)度兩方面。

3.2.1　開環(huán)調(diào)度

1）對NCS 中各個控制環(huán)中數(shù)據(jù)傳輸節(jié)點(diǎn)采樣周期和采樣時刻的調(diào)度

Hong基于“窗口”的概念，給出了一種通過調(diào)度采樣時間來減少時延的影響并提高網(wǎng)絡(luò)利用率的調(diào)度算法，建立了NCS 控制系統(tǒng)性能與網(wǎng)絡(luò)性能間的約束關(guān)系。但該算法是基于令牌環(huán)系統(tǒng)(token passing system) 和輪詢系統(tǒng)(polling system) 的一維對象的調(diào)度，系統(tǒng)中信息類型僅限于周期性信息。Kim等[16 ]基于相同思想提出了適用于多維對象的采樣時間調(diào)度算法。劉魯源等[17 ]提出了利用剩余的時間窗口調(diào)度非實(shí)時數(shù)據(jù)提高了網(wǎng)絡(luò)資源利用率的調(diào)度算法。

2）調(diào)度優(yōu)化

Seto[19] 針對性能指標(biāo)是單調(diào)遞減并且是每一任務(wù)頻率的凸函數(shù)的這樣一類控制系統(tǒng)，提出了一種通過改變采樣頻率使得任務(wù)能被EDF和RM調(diào)度的新算法，而且系統(tǒng)的性能在有限計算資源的約束下可達(dá)到最優(yōu)。但該算法沒有考慮執(zhí)行時間的變化與擾動問題。Cervin[20]考慮了具有時延變化的控制系統(tǒng)采樣周期的選擇問題，對低于一個采樣周期的時延系統(tǒng)的采樣周期進(jìn)行了分析。Ryu 等[21] 以穩(wěn)定狀態(tài)誤差、過沖、上升時間、沉降速度等作為控制性能參數(shù)，并將它們表示為采樣周期和輸入輸出延時的函數(shù)，在可調(diào)度約束條件下用迭代算法對這些性能參數(shù)進(jìn)行優(yōu)化。何堅(jiān)強(qiáng)等[24 ] 在上述研究的基礎(chǔ)上給出了NCS 的優(yōu)化模型并采用遺傳算法來求取采樣頻率。Branicky 和Zhang 等[25 ]提出將非搶占RM調(diào)度算法應(yīng)用于網(wǎng)絡(luò)控制系統(tǒng)的調(diào)度，并給出了保證系統(tǒng)穩(wěn)定和網(wǎng)絡(luò)可調(diào)度的充分條件。在此基礎(chǔ)上，Branicky等[26]進(jìn)一步對網(wǎng)絡(luò)傳輸時間進(jìn)行了分配，給出了網(wǎng)絡(luò)調(diào)度優(yōu)化方法。

3.2.2 反饋控制實(shí)時調(diào)度

開環(huán)調(diào)度算法在負(fù)載能精確建模的動態(tài)或靜態(tài)系統(tǒng)中可以取得很好的效果，可是在不可測的動態(tài)系統(tǒng)中，算法的有效性要極大地降低。近幾年來，“閉環(huán)”調(diào)度由于可以應(yīng)用于很多實(shí)時領(lǐng)域因而引起了很多人的關(guān)注。在Seto等提出的系統(tǒng)控制和調(diào)度離線集成設(shè)計的基礎(chǔ)上，Cervin[14]提出一種將控制和調(diào)度動態(tài)彈性集成的框架，允許在線平衡控制性能和可用的計算資源。Stankovic等[18]提出了反饋控制實(shí)時調(diào)度的思想，而且還給出了一種結(jié)合PID 控制和EDF 調(diào)度器的反饋控制實(shí)時調(diào)度算法FC-EDF ( Feedback Control- Earliest Deadline First) 。湯賢銘等[2]提出了一種將動態(tài)死區(qū)控制和優(yōu)先級分配相結(jié)合的反饋調(diào)度策略，用以解決在工作負(fù)載變動的環(huán)境中網(wǎng)絡(luò)控制系統(tǒng)的控制與調(diào)度問題。Eker等[15]開發(fā)出了針對線性二次(Linear Quadratic) 控制的反饋控制器。在可調(diào)度的情況下通過調(diào)整控制環(huán)頻率來優(yōu)化控制性能。Zhao[28]提出了一種結(jié)合速率單調(diào)調(diào)度和新的動態(tài)調(diào)度的動態(tài)反饋調(diào)度，用于調(diào)度預(yù)控制器產(chǎn)生的控制信號的傳輸，該調(diào)度算法確保了系統(tǒng)的穩(wěn)定性，并且保證系統(tǒng)時延不超過保證系統(tǒng)穩(wěn)定的上限。

4 進(jìn)一步可研究的參考方向

當(dāng)前，NCS信息調(diào)度的研究已經(jīng)取得了很多有益的成果。然而，NCS應(yīng)用的復(fù)雜化以及NCS控制與調(diào)度的協(xié)調(diào)設(shè)計趨勢，使得現(xiàn)有的信息調(diào)度方法已不能滿足發(fā)展的需求。因此，給出信息調(diào)度的進(jìn)一步研究問題和研究目標(biāo)，以供參考。

（1）網(wǎng)絡(luò)控制的復(fù)雜化和網(wǎng)絡(luò)運(yùn)行狀況的多變性，需要智能化強(qiáng)、實(shí)時性好的在線調(diào)度算法。

（2）現(xiàn)有的研究結(jié)果大多限于單控制回路，對共享網(wǎng)絡(luò)的多個控制回路的優(yōu)化調(diào)度等問題需要進(jìn)一步的研究。

（3）有帶寬約束的變速率網(wǎng)絡(luò)化控制系統(tǒng)的信息調(diào)度問題。

（4）不同數(shù)據(jù)流分配不同比例帶寬，用來提高高優(yōu)先級別數(shù)據(jù)流的服務(wù)質(zhì)量，避免低優(yōu)先級別的數(shù)據(jù)流由于網(wǎng)絡(luò)超時而斷開的研究。

（5）研究NCS 多目標(biāo)優(yōu)化問題的提取和求解。考慮網(wǎng)絡(luò)利用率、數(shù)據(jù)包丟失率、系統(tǒng)穩(wěn)定性等多重約束，建立NCS 多目標(biāo)優(yōu)化問題的數(shù)學(xué)模型。進(jìn)而考慮NCS 的實(shí)時性要求，研究基于遺傳算法等進(jìn)化智能計算方法的NCS 分級多目標(biāo)優(yōu)化問題的求解方法。

（6）將系統(tǒng)性能的優(yōu)化映射為較低層次的系統(tǒng)參數(shù)優(yōu)化、網(wǎng)絡(luò)參數(shù)選取、帶寬資源調(diào)度問題，力求達(dá)到系統(tǒng)設(shè)計與網(wǎng)絡(luò)實(shí)現(xiàn)的總體性能優(yōu)化的目標(biāo)。引入新的、更多的反映系統(tǒng)性能的優(yōu)化指標(biāo)，尋求新的融合網(wǎng)絡(luò)與控制系統(tǒng)其它結(jié)合點(diǎn)將是未來的發(fā)展方向。

參考文獻(xiàn)

[1] 洪艷偉，賴娟，楊斌.基于EDF 算法的可行性判定及實(shí)現(xiàn).計算機(jī)技術(shù)與發(fā)展[J].2006，16(11)：97-102

[2] 湯賢銘，錢凱，俞金壽.網(wǎng)絡(luò)控制系統(tǒng)動態(tài)死區(qū)反饋調(diào)度.華東理工大學(xué)學(xué)報[J].2007，33(5)：716-721

[3] 張慶靈，邱占芝.網(wǎng)絡(luò)控制系統(tǒng)[M].北京市：科學(xué)出版社，2007.37-38

[4] 文遠(yuǎn)保，張炫.單調(diào)比率調(diào)度算法研究及改進(jìn).計算機(jī)工程與科學(xué)[J].2006，28(10)，68-70

[5] 葉明，羅克露，陳慧. 單調(diào)比率(RM)調(diào)度算法及應(yīng)用.計算機(jī)應(yīng)用[J].2005，25(4)：889-891

[6] LIU Luyuan，WAN Renjun，LI Bing. On static scheduling algorithm for networked control based on TTCAN protocol .Control and Decision[J ].2004，19 (7)： 814 - 816

[7] 張奇智，曹春生，張衛(wèi)東.EDF 調(diào)度方法在交換式工業(yè)以太網(wǎng)中的實(shí)現(xiàn).化工自動化及儀表[J]. 2004，31 (6)：41-43

[8] Walsh G C，Hong Ye. Scheduling of networked control systems . IEEE Control System Magazine[J].2001，21 (1)： 57 - 65

[9] Otanez P，Moyne J，Tilbury D. Using deadbands to reduce communication in networked control systems [A].The American Automatic Control Council[C]. Anchorage：Proceedings of the American control conference. 2002：615-619

[10] 劉懷，費(fèi)樹岷.基于EDF的分布式控制系統(tǒng)容錯調(diào)度算法.軟件學(xué)報[J].2003，14(8)1371-1378

[11] 張惠娟，周利華.一種基于EDF算法的多處理器實(shí)時調(diào)度算法.計算機(jī)工程與應(yīng)用[J].2003，30(16)16-17

[12] 王智. 面向現(xiàn)場總線的分布式實(shí)時系統(tǒng)的建模與分析方法[D]. 博士，中國科學(xué)院，2000

[13] 白濤. 網(wǎng)絡(luò)控制系統(tǒng)的性能分析與調(diào)度優(yōu)化[D] . 碩士，上海交通大學(xué)，2005

[14] ARZEN K E，CERVIN A，EKER J . An introduction to control and scheduling co-design[A].In Proceedings of the 39th IEEE Conference on Decision and Control [C]Sydney： 2000，4865 - 4870

[15] EKER J，HAGANDER P，ARZEN K E. A feedback scheduler for real-time controller tasks. Control Engineering Practice[J].2000，8(12)：1369 -1378

[16] KIM Y H，PARK H S，KWON W H.A scheduling method for network based control systems[A]. In Proceedings of IEEE ACC[C].USA，1998：718 - 722

[17] 劉魯源，萬仁君，李斌. 基于TTCAN 協(xié)議的網(wǎng)絡(luò)控制系統(tǒng)靜態(tài)調(diào)度算法的研究.控制與決策 [J].2004，19(7)：813 - 816

[18] STANKOVIC J A，LU C Y，SON S H，et al . The case for feedback control real-time scheduling[A]. In Proceedings of the 11th Euromicro Conference on Real-Time Systems[C]. New York：1999，1：11 - 20

[19] SETO D，LEHOCZKYJ P，SHAL. Task period selection and schedulability in real-time systems[A]. In Proceedings of the 19th IEEE Real-time Systems Symposium[C]. Madrid，1998：188 - 198

[20] CERVIN A. Integrated control and real-time scheduling[D]. Ph. D. Dissertation，Department of Automatic Control Lund Institute of Technology，2003

[21] RYU M，HONG S. Toward automatic synthesis of schedulable real-time controllers. Integrated Computer aided Engineering[J].1998，5(3)：261 - 277

[22] TINDELL K，BUMS A. Analysis of Hard Real-time Communication. Real-Time System[J].1995，9(2)：147 - 173

[23] LEHOCZKYJ，SHAL，DING Y. The rate monotonic scheduling algorithm：exact characterization and average case behavior[A]. In Proceedings of IEEEReal-time Systems Symposium[C].Santa Monica：1989：166 - 171

[24] HE J Q，ZHANG H C，JING Y Z. A integrated control and scheduling optimization method of networked control systems. Journal of Electronic Science and Technology of China[J].2004，2(2)：56 - 59

[25] ZHANG W，BRANICKYM S，PHILIPS S M. Stability of networked control systems. IEEE Control Magazine[J].2001，21 (1)：84 - 99

[26] BRANICKYM S，PHILLIPS S M，ZHAN GW. Scheduling and feedbackcodesign for networked control systems. In Proceedings of IEEE Conference on Decision and Coutrol .Las Vegas[J].2002：1211 - 1217

篇8

論文摘要：運(yùn)用虛擬現(xiàn)實(shí)仿真 (VRS)進(jìn)行實(shí)驗(yàn)教學(xué)是激發(fā)學(xué)生學(xué)習(xí)興趣的有效途徑。針對大學(xué)生的學(xué)習(xí)特點(diǎn)，分析了傳統(tǒng)教學(xué)方法的不足，探討了基于虛擬現(xiàn)實(shí)仿真的“生產(chǎn)與運(yùn)作管理”實(shí)驗(yàn)教學(xué)的特點(diǎn)、內(nèi)容和形式，有助于高校教師優(yōu)化教學(xué)過程，提高教學(xué)質(zhì)量和教學(xué)效果。

縱觀我國工商管理本科專業(yè)人才的就業(yè)去向可以發(fā)現(xiàn)，畢業(yè)生就業(yè)去向大都是金融業(yè)、政府機(jī)關(guān)和高校，極少有人自愿去制造企業(yè)工作，即使到了制造企業(yè)，也只愿意去財務(wù)或營銷部門，而不愿去生產(chǎn)管理部門，原因是生產(chǎn)管理部門的崗位工作環(huán)境較差，待遇較低，付出多，導(dǎo)致集中了企業(yè)絕大部分財力、人力、設(shè)備及其他資源的生產(chǎn)系統(tǒng)受到冷落。在這樣的人才使用環(huán)境中，學(xué)生對于與生產(chǎn)管理相關(guān)的課程自然就不重視。然而，從工業(yè)發(fā)達(dá)國家看，近年來，紛紛將注意力轉(zhuǎn)移到生產(chǎn)領(lǐng)域，企業(yè)界和學(xué)術(shù)界也都開始重新審視企業(yè)內(nèi)部的生產(chǎn)系統(tǒng)及其管理理論，將生產(chǎn)戰(zhàn)略問題作為企業(yè)經(jīng)營戰(zhàn)略的重要組成部分來研究。可見，創(chuàng)新教學(xué)方法，增強(qiáng)學(xué)生學(xué)習(xí) “生產(chǎn)與運(yùn)作管理”課程的興趣，具有非常重要的現(xiàn)實(shí)意義。

1 生產(chǎn)與運(yùn)作管理課程的教學(xué)調(diào)查和教學(xué)方式的分析

1．1 教學(xué)調(diào)查

在浙江省精品課程 “生產(chǎn)與運(yùn)作管理”的建設(shè)過程中，為了有針對性地開展課程教學(xué)方法改革，我們就本課程的學(xué)習(xí)，于2007年對我校 04級工商管理專業(yè)40名學(xué)生做了一次調(diào)查，得到如下結(jié)論：

(1)由于學(xué)生沒有實(shí)際工程背景，缺乏對企業(yè)生產(chǎn)與運(yùn)作管理的感性認(rèn)識，對于生產(chǎn)與運(yùn)作管理的一些理論和方法理解有一定困難；

(2)學(xué)生對生產(chǎn)與運(yùn)作管理課程的認(rèn)識存在誤區(qū)，對相關(guān)理論知識掌握不熟練，對未來是否從事生產(chǎn)管理工作信心不足，導(dǎo)致學(xué)習(xí)該課程的動力不足：

(3)隨著非制造業(yè)在國民經(jīng)濟(jì)中地位的提升以及制造業(yè)和非制造業(yè)現(xiàn)實(shí)的工作性質(zhì)、工作環(huán)境和條件、工資待遇等方面的差異，決定了學(xué)生對以制造業(yè)為主體的生產(chǎn)與運(yùn)作管理課程熱情不高；

(4)學(xué)生對傳統(tǒng)的案例討論、觀看錄像、企業(yè)參觀、專家講座、計算機(jī)輔助教學(xué)等教學(xué)模式基本認(rèn)可，但是對創(chuàng)新教學(xué)方法和手段的需求更為強(qiáng)烈。

1．2 教學(xué)方式分析

生產(chǎn)與運(yùn)作管理是一門實(shí)踐性、操作性強(qiáng)的課程，教學(xué) 的關(guān)鍵是讓學(xué)生產(chǎn)生 “真實(shí)感”。教學(xué)方式除了課堂授課外 ，傳統(tǒng)的教學(xué)方式主要有如下幾種 。

(1)觀看錄像。這種方式比較簡單，國外教材都配有相應(yīng)的錄像教學(xué)光盤，學(xué)生通過觀看錄像了解國外先進(jìn)企業(yè)的生產(chǎn)與運(yùn)作管理經(jīng)驗(yàn)。比如針對質(zhì)量管理專題，播放美國著名酒店的全面質(zhì)量管理錄像；講授 5s現(xiàn)場管理，播放一盤有關(guān)現(xiàn)場改善的錄像；講到供應(yīng)鏈管理、庫存管理時，根據(jù)需要選擇相應(yīng)的錄像播放。

觀看錄像這種方式存在 2個問題，一是現(xiàn)有錄像大多是英文版，錄像的對話比較快，多數(shù)學(xué)生聽不清楚。另外，錄像內(nèi)容以綜合性為主，缺乏針對國內(nèi)生產(chǎn)管理的專題教學(xué)光盤。

(2)參觀企業(yè)。這是一種比較好的理論聯(lián)系實(shí)踐的學(xué)習(xí)方法，能夠讓學(xué)生真實(shí)感受到企業(yè)的實(shí)際生產(chǎn)隋景，并對照所學(xué)的專業(yè)理論知識加以思考。比如，針對紹興紡織特色，選擇了紡織印染企業(yè)作為參觀對象，讓學(xué)生到生產(chǎn)車間看設(shè)備布局、生產(chǎn)流程、生產(chǎn)計劃與調(diào)度、質(zhì)量控制、現(xiàn)場改善與員工的班組建設(shè)等基層運(yùn)作管理。

這種方法在實(shí)施中存在困難，主要是沒有建立固定的教學(xué)基地，與企業(yè)沒有穩(wěn)定的關(guān)系；而且，隨著學(xué)生人數(shù)的逐年增多，許多企業(yè)對學(xué)生參觀不感興趣。

(3)邀請企業(yè)專家講座。對于某些實(shí)務(wù)性、技巧性比較強(qiáng)的內(nèi)容，如生產(chǎn)調(diào)度、員工指派、班組建設(shè)、現(xiàn)場改善等，請企業(yè)專家結(jié)合自己的工作實(shí)際，現(xiàn)身傳授管理技巧和經(jīng)驗(yàn)，比任課教師講效果好，印象深。

與參觀一樣，邀請專家也存在一定困難。由于企業(yè)的工作繁忙，很難保證企業(yè)專家能按照課程的教學(xué)時間來安排講座，這樣很有可能打亂教學(xué)計劃。

(4)案例討論。教學(xué)案例一方面可以增加學(xué)生的實(shí)踐知識，另一方面幫助學(xué)生深入理解相應(yīng)的教學(xué)內(nèi)容，提高學(xué)生分析問題、解決問題的綜合能力。生產(chǎn)與運(yùn)作管理課程案例不同于其他管理課程的案例，它的特點(diǎn)是需要生產(chǎn)與運(yùn)作管理理論知識作基礎(chǔ)解決實(shí)際問題。比如：生產(chǎn)能力規(guī)劃案例只有在學(xué)習(xí)完生產(chǎn)能力查定辦法相關(guān)理論的基礎(chǔ)上，才能進(jìn)行案例分析；庫存管理案例的中心是解決庫存問題，如果不了解庫存管理理論，是很難進(jìn)行案例討論的；又比如網(wǎng)絡(luò)計劃案例，在討論的時候，學(xué)生首先要對網(wǎng)絡(luò)計劃技術(shù)有所了解，然后才能進(jìn)行案例分析。

目前好的生產(chǎn)與運(yùn)作管理案例不多，主要問題是：案例篇幅太長，描述性內(nèi)容多，真正反映生產(chǎn)與運(yùn)作管理的實(shí)際數(shù)據(jù)和實(shí)際場景模擬少，教學(xué)效果不佳。

(5)傳統(tǒng)的計算機(jī)輔助模擬實(shí)驗(yàn)教學(xué)系統(tǒng)(實(shí)驗(yàn)教學(xué)軟件)。采用計算機(jī)和多媒體輔助實(shí)驗(yàn)教學(xué)，教師可以精心設(shè)計教學(xué)內(nèi)容，使復(fù)雜問題簡單化，繁瑣問題條理化，抽象問題具體化，具體問題概括化，使教學(xué)過程以直觀的形式達(dá)到人機(jī)一體，便于圍繞某一學(xué)習(xí)主題進(jìn)行密集、快速的活動，同時增加了課堂教學(xué)的密度和廣度。目前本課程中常用的實(shí)驗(yàn)軟件主要有物料需求計劃／制造資源計劃實(shí)驗(yàn) (MRP／MRP II)、項(xiàng) 目進(jìn)度計劃實(shí)驗(yàn) (PERT)、質(zhì)量管理實(shí)驗(yàn) (排列圖、因果圖、直方圖、控制圖)、工作分析與工作研究實(shí)驗(yàn)等。

從近年來的實(shí)施情況看，學(xué)生對這種傳統(tǒng)的計算機(jī)輔助實(shí)驗(yàn)教學(xué)開始產(chǎn)生視覺疲勞，興趣逐步減弱。原因在于某些實(shí)驗(yàn)教學(xué)軟件只是教學(xué)形式的變化，更多的是將重點(diǎn)放在了生產(chǎn)與運(yùn)作管理活動教學(xué)模型的求解上，而對于更為重要的企業(yè)業(yè)務(wù)流程分析、經(jīng)濟(jì)模型構(gòu)建與咨詢診斷等功能沒有真正體現(xiàn)。實(shí)驗(yàn)過程中，學(xué)生只要記住幾個參數(shù)，并輸入到軟件規(guī)定的相應(yīng)位置，就可以得出實(shí)驗(yàn)結(jié)果，不能真正起到培養(yǎng)學(xué)生知識運(yùn)用能力和創(chuàng)新能力的目的。另一個主要原因是該課程實(shí)踐性很強(qiáng)，而高校教師普遍缺乏企業(yè)生產(chǎn)管理的實(shí)際經(jīng)驗(yàn)。某些教師一直從事教學(xué)工作，沒有企業(yè)的從業(yè)經(jīng)歷，或者即使有一定的生產(chǎn)管理的實(shí)際經(jīng)驗(yàn)，也由于長期在高校從事教學(xué)和學(xué)術(shù)研究，對企業(yè)目前生產(chǎn)運(yùn)營中的某些實(shí)際問題的了解不夠深人。由于實(shí)際管理經(jīng)驗(yàn)的缺乏，教師容易在教學(xué)中造成理論和實(shí)踐脫節(jié)、枯燥和不生動等問題。

2 虛擬現(xiàn)實(shí)仿真技術(shù)在“生產(chǎn)與運(yùn)作管理”教學(xué)中的應(yīng)用

隨著管理思想的發(fā)展和新技術(shù)、新方法、新成果的不斷涌現(xiàn)，生產(chǎn)與運(yùn)作管理學(xué)科的范圍和內(nèi)容在不斷拓展，僅僅依靠人的經(jīng)驗(yàn)及傳統(tǒng)的計算機(jī)技術(shù)難于滿足越來越高的要求?；诂F(xiàn)代計算機(jī)技術(shù)及網(wǎng)絡(luò)的虛擬現(xiàn)實(shí)仿真技術(shù)，已經(jīng)廣泛應(yīng)用于電力、交通運(yùn)輸、通信、化工、核能等各個領(lǐng)域。借助虛擬現(xiàn)實(shí)仿真技術(shù)進(jìn)行本課程的實(shí)驗(yàn)教學(xué)，對企業(yè)業(yè)務(wù)活動進(jìn)行多維仿真，給學(xué)生產(chǎn)生各種感官信號，使學(xué)生有身臨其境的感覺，并能使學(xué)生與虛擬現(xiàn)實(shí)環(huán)境之間進(jìn)行多維信息的交互，從定性和定量結(jié)合集成的虛擬環(huán)境中獲得企業(yè)生產(chǎn)運(yùn)作活動的感性和理性認(rèn)識，體驗(yàn)、接受和認(rèn)識客觀事物，深化對概念、原理和方法的理解，進(jìn)而提出設(shè)計創(chuàng)意。在制造業(yè)生產(chǎn)系統(tǒng)的規(guī)劃、設(shè)計、運(yùn)行、分析及改造的整個生命周期，都可以使用虛擬現(xiàn)實(shí)仿真技術(shù)進(jìn)行實(shí)驗(yàn)教學(xué)，具有代表性的主要有如下幾種。

(1)用于產(chǎn)品研發(fā)的仿真實(shí)驗(yàn)。產(chǎn)品研發(fā)過程可分為概念設(shè)計、細(xì)節(jié)設(shè)計、評審和再設(shè)計階段。每一階段又可以細(xì)分，如詳細(xì)設(shè)計可分為總體CAD、零部件 CAD、計算機(jī)輔助工程、可制造技術(shù)、可裝配性設(shè)計等。產(chǎn)品研發(fā)過程的仿真實(shí)驗(yàn)就是對上述活動進(jìn)行模擬，讓學(xué)生從進(jìn)度、資源和成本等指標(biāo)進(jìn)行綜合分析，選擇集成的最優(yōu)方案。

(2)用于車間設(shè)施規(guī)劃和布局的仿真實(shí)驗(yàn)。根據(jù)車間之間和車間內(nèi)部空間的組織方式，采用虛擬現(xiàn)實(shí)仿真技術(shù)模擬各種方案，判斷車間整體布局是否能滿足車間調(diào)度要求，車間設(shè)備是否得到充分利用，負(fù)荷是否比較平衡，物料處理系統(tǒng)是否能夠和車間的柔性程度相適應(yīng)，生產(chǎn)制造運(yùn)輸費(fèi)用是否合理等。例如在流水線生產(chǎn)系統(tǒng)的仿真實(shí)驗(yàn)中，運(yùn)用WITNESS仿真軟件模擬流水生產(chǎn)過程，加深學(xué)生對流水線組織設(shè)計與技術(shù)設(shè)計的理解和掌握，讓學(xué)生學(xué)會對流水線進(jìn)行控制。目前國內(nèi)外用于輔助車間生產(chǎn)系統(tǒng)設(shè)計的仿真軟件有 PURDUE大學(xué)開發(fā)的 GCMS，System Modeling公 司開 發(fā)的 SIMAN／CINEMA，Auto Simulation公司開發(fā)的 AUTOMOD／AUTOGRAM和清華大學(xué)開發(fā)的 IMMS等。

(3)用于車間生產(chǎn)調(diào)度的仿真實(shí)驗(yàn)。車間內(nèi)部的生產(chǎn)調(diào)度問題包括：確定工件的加工路線，確定工件在機(jī)器上的加工工藝和加工時間，選擇運(yùn)輸路線和工具，指派加工工人等。生產(chǎn)調(diào)度仿真實(shí)驗(yàn)就是對這些調(diào)度問題進(jìn)行分析和評價，目前已經(jīng)有一些成熟的軟件可用來仿真調(diào)度問題，如 Autosched、JobTimePlus、FACTOR、FACTOR／AIM和 SIMNETD等。我國也已研制開發(fā)了用于車間調(diào)度層面的仿真軟件，如南開大學(xué)研制的JobShop，清華大學(xué)與航天部204所等單位開發(fā)的工廠仿真調(diào)度環(huán)境FASE，以及在此基礎(chǔ)上開發(fā)的智能規(guī)劃調(diào)度系統(tǒng)等。

(4)用于物流與供應(yīng)鏈管理的仿真實(shí)驗(yàn)。從生產(chǎn)線到車問到整個工廠，再到供應(yīng)鏈系統(tǒng)的庫存、瓶頸、流程、協(xié)作和信息共享等方面，通過仿真可以快速改變和優(yōu)化系統(tǒng)的流程邏輯和決策數(shù)據(jù)的靈敏度分析。如：在物流系統(tǒng)中配送路線的優(yōu)化實(shí)驗(yàn)中，運(yùn)用 WITNESS軟件的設(shè)計功能，根據(jù)規(guī)劃與物流分析的主要內(nèi)容，以物流系統(tǒng)中運(yùn)輸成本最小為目標(biāo)，設(shè)計物流系統(tǒng)中的配送路線，使整個配送路線最優(yōu)，從而達(dá)到運(yùn)輸成本最低；在垃圾回收物流仿真系統(tǒng)設(shè)計實(shí)驗(yàn)中，仿真程序研究如何設(shè)計物流系統(tǒng)，使收集系統(tǒng)在滿足時間約束、載重約束的條件下，使垃圾處理公司的物流總成本最低。系統(tǒng)涉及的指標(biāo)主要有車輛載重量、隨車工作人員數(shù)和客戶滿意度。

總之，虛擬現(xiàn)實(shí)仿真技術(shù)在制造業(yè)的應(yīng)用已經(jīng)貫穿于產(chǎn)品設(shè)計開發(fā)、生產(chǎn)計劃制定、加工、裝配、測試和銷售的整個生命周期。

除了上述單一企業(yè)的生產(chǎn)管理的虛擬現(xiàn)實(shí)仿真技術(shù)外，用于虛擬企業(yè)業(yè)務(wù)流程集成的虛擬現(xiàn)實(shí)仿真技術(shù)正成為仿真技術(shù)研究的熱點(diǎn)。比較典型的仿真實(shí)驗(yàn)軟件是 CIM—OSA，在應(yīng)用 CIM—OSA進(jìn)行供應(yīng)鏈分析與設(shè)計時，系統(tǒng)描述了2個仿真工具的開發(fā)和設(shè)計。其一是在 Arena仿真平臺上開發(fā)的單機(jī)后勤仿真器，其二是基于 Internet的虛擬企業(yè)內(nèi)供應(yīng)鏈集成仿真環(huán)境。在基于 Internet仿真器的功能設(shè)計上，每個供應(yīng)鏈模塊包括在線的Intemet應(yīng)用和離線的信息管理 2個模塊。Intemet系統(tǒng)在通用的www環(huán)境下進(jìn)行開發(fā)，以支持各類廣泛應(yīng)用的Web服務(wù)器和瀏覽器。根據(jù)不同供應(yīng)鏈伙伴的不同需求，如在線訂購和在線庫存量檢索等，它們的應(yīng)用系統(tǒng)將有所不同。

另外，虛擬現(xiàn)實(shí)仿真技術(shù)的應(yīng)用也正在向服務(wù)業(yè)不斷滲透。目前許多高校在生產(chǎn)與運(yùn)作管理的實(shí)驗(yàn)課程中，都安排了服務(wù)業(yè)的相關(guān)仿真實(shí)驗(yàn)，代表性的是采用 Lanner公司提供的世界領(lǐng)先的仿真工具 WITNESS。通過 WITNESS對實(shí)際商業(yè)系統(tǒng) (工業(yè)工程、制造工程、運(yùn)作管理、供應(yīng)鏈與物流、戰(zhàn)略管理、業(yè)務(wù)流程)的建模和仿真，讓學(xué)生了解不同制造業(yè)、服務(wù)業(yè)的運(yùn)作流程。通過 WITNESS模型的交互菜單，學(xué)生可以作出不同的管理、運(yùn)作流程項(xiàng)目的設(shè)計，并能夠及時運(yùn)行和獲得系統(tǒng)的效果，給學(xué)生提供深刻的流程體驗(yàn)，使學(xué)生能很好地完成生產(chǎn)與運(yùn)作管理課程的各項(xiàng)設(shè)計任務(wù)，達(dá)到真正提高教學(xué)效果的目的。

3 結(jié)束語

生產(chǎn)與運(yùn)作管理是一門實(shí)踐性很強(qiáng)的課程，從增加現(xiàn)實(shí)場景模擬、加強(qiáng)課堂師生互動、強(qiáng)化理論與實(shí)際結(jié)合等方面不斷創(chuàng)新多樣化的教學(xué)方法，對學(xué)生進(jìn)行實(shí)踐技能和科學(xué)研究方法的訓(xùn)練，不僅有助于學(xué)生鞏固課堂所學(xué)知識，加深對生產(chǎn)與運(yùn)作管理基本概念、基本原理和分析方法的理解，掌握從事企業(yè)生產(chǎn)與運(yùn)作管理活動的基本技能，而且，能夠拓寬學(xué)生的知識領(lǐng)域，鍛煉學(xué)生的實(shí)踐技能，培養(yǎng)科學(xué)嚴(yán)謹(jǐn)、求真務(wù)實(shí)的工作作風(fēng)。

參考文獻(xiàn)（References)：

[1]王曉燕．案例教學(xué)法在管理類本科教學(xué)中的應(yīng)用研究 [J]．武漢科技大學(xué)學(xué)報：社會科學(xué)版，2007，9(4)：412．414．

[2]陳志祥．MBA《生產(chǎn)與運(yùn)作管理》課程建設(shè)與教學(xué)方法研究[J]．教育與現(xiàn)代化，2006(3)：3．8．

[3]許志端．《生產(chǎn)與運(yùn)作管理》教學(xué)中企業(yè)參觀的課程設(shè)計[J]．廈門大學(xué)學(xué)報：自然科學(xué) 版，2003，42 (10S)：144—147．

[4]王亞超，馬漢武．生產(chǎn)物流系統(tǒng)建模與仿真 [M]．北京：科學(xué)出版社，2006．

篇9

目前國內(nèi)物流公司的出廠裝箱調(diào)度仍舊采取效率極低的人工調(diào)度，盡管國內(nèi)外二維、三維裝箱調(diào)度問題已經(jīng)有大量研究，但由于國內(nèi)絕大部分物流公司不夠規(guī)范，而采用二維、三維裝箱調(diào)度對人員素質(zhì)要求較高、統(tǒng)計難度較大，同時對公司的信息系統(tǒng)有較高的要求，先進(jìn)的理論在實(shí)踐中沒有得到很好的應(yīng)用，因此本文從整車訂單和轎運(yùn)車配載的過程，不考慮整車目的地和轎運(yùn)車的路徑選擇，抽象出帶裝載組合約束的一維裝車問題，即有n個屬于l種類型的相同（單位）尺寸的物品。有w輛車，每輛車對這l種類型的物品有幾種裝載組合，不同車輛的裝載組合不同，每輛車選擇一種裝載組合并嚴(yán)格按照物品組合進(jìn)行裝載。優(yōu)化目標(biāo)是在滿載的情況下裝載最多的物品，同時給出每個物品的具體配載方案。如：有10個屬于3種類型的物品，每個物品的類型見表1；有2輛車，車輛1有2種裝載組合，車輛2有3種裝載組合，裝載組合見表2。顯然當(dāng)選擇車輛1的裝載組合2，車輛2的裝載組合3時，兩輛車都能滿載且能全部裝完所有10個物品，是最優(yōu)解。

本文假設(shè)車輛資源的節(jié)約價值不大，因此將裝載最多的物品作為優(yōu)化目標(biāo)。同時，定義滿載率來表示車輛的利用率，滿載率為當(dāng)次調(diào)運(yùn)裝載的所有物品數(shù)與參與調(diào)運(yùn)的所有車輛裝載總量之和的比例，本文將滿載率設(shè)置為100％。帶裝載組合約束的一維裝車問題是由實(shí)踐研究中提煉而成的理論模型，相似的問題為有色裝箱問題［1］，后被廣泛應(yīng)用于多處理器任務(wù)調(diào)度［2］、并行處理［3］以及多媒體存儲［4］等問題。Shachnai提出有類型約束的裝箱問題［5］。其他一維裝箱問題的衍生問題有：楊鼎強(qiáng)［6］提出受位置約束的有色裝箱問題，Epstein研究了有類型約束的覆蓋問題［7］，Xavier提出有類型約束的貨架裝箱問題［8］，Marques提出有分區(qū)的背包問題［9］。Hoto給出了分區(qū)背包問題的材料切割實(shí)例［10］。本文從精確算法和啟發(fā)式算法兩個方面入手，首先建立線性混合整數(shù)規(guī)劃模型得出問題的精確解，并根據(jù)問題的特性利用貪婪技術(shù)建立近似算法模型，最后進(jìn)行數(shù)值實(shí)驗(yàn)和參數(shù)的敏感性分析。本文試圖提出針對特定場景下的出廠物流調(diào)度問題的有效算法，并給出合適的參數(shù)設(shè)置，從而提高整車出廠物流調(diào)度的速度與準(zhǔn)確性。本文結(jié)構(gòu)如下：第1節(jié)描述問題并建立線性混合整數(shù)規(guī)劃模型，第2節(jié)建立基于貪婪算法的啟發(fā)式算法，第3節(jié)數(shù)值實(shí)驗(yàn)與敏感性分析，第4節(jié)是本文的結(jié)論與進(jìn)一步研究的展望。

2　問題描述及數(shù)學(xué)建模

2．1　問題假設(shè)本文所研究問題的假設(shè)有：（1）所有物品尺寸為1單位；（2）每輛車以及不同車的裝載組合是獨(dú)立的；在實(shí)際調(diào)度中可能存在兩輛車的裝載組合相同，但考慮到每輛車除了本文提及的信息，還有所歸屬的運(yùn)輸公司、調(diào)運(yùn)目的地偏好等的不同，因此認(rèn)為這兩個裝載組合也是不同的。（3）所有參與裝載的裝載組合都必須滿載。

2．2　問題描述本文研究的帶裝載組合約束的一維裝車問題描述為：物品數(shù)m，物品集合I＝｛1，2，…，m｝；物品的類型為mi，類型數(shù)集合K＝｛1，2，…，l｝，車輛數(shù)w，單位的裝載容量，每輛車只能選用一種裝載組合，并嚴(yán)格按照裝載組合裝載物品。優(yōu)化目標(biāo)是在滿載的情況下裝載最多的物品。

2．3　復(fù)雜性分析考慮帶裝載組合約束的一維裝車問題的簡化問題，當(dāng)每輛車只有一個裝載組合時，問題變?yōu)椋河衛(wèi)種類型的物品，類型k的物品數(shù)Qk，有n個裝載組合，第j個裝載組合對類型k物品的容量Cjk，對所有類型物品的容量Cj，選擇裝載組合以盡可能裝載最多的物品。已知多維背包問題為NP－難問題［11］，多維背包問題是從給定選項(xiàng)的集合I＝｛1，2，…，n｝中選出一組滿足所有約束的項(xiàng)，使其價值之和最大，數(shù)學(xué)公式為其中，pj為項(xiàng)j的價值，令pj＝cj；xj為對應(yīng)項(xiàng)j的變量，項(xiàng)j被選中xj＝0，否則，xj＝0；rkj＞0為項(xiàng)j的消耗資源k的量，令rjk＝Cjk；bk為資源k的總量，令bk＝Qk，Qk為第k種類型的物品數(shù)。此時多維背包問題轉(zhuǎn)化為一維組合裝車問題的簡化問題，則一維組合裝車問題的簡化問題為NP－難問題，顯然一維組合裝車問題更為復(fù)雜，也即一維組合裝車問題為NP－難問題。

2．4　線性混合整數(shù)規(guī)劃模型本文的最終結(jié)果是給出具體的裝載方案，即物品裝載在哪輛車的哪個裝載組合上，因此以物品作為決策主體，物品選擇車輛、裝載組合。其他參數(shù)與變量如下。參數(shù)m：物品數(shù)；l：類型數(shù)；w：車輛數(shù)；v＿n：第v輛車的裝載組合數(shù)，j＝1，2，…，v＿n；Cvjk：第v輛車第j個裝載組合裝載第k種類型物品的容量。變量xivj：1，若物品i裝在車輛v的第j個裝載組合上，否則為0；yvj：1，若車輛v選擇第j個裝載組合，否則為0。數(shù)學(xué)模型基于上述定義，建立如下線性混合整數(shù)規(guī)劃模型?！?yōu)化目標(biāo)為物品裝載數(shù)最多；約束式（1）表示一輛車最多只能選擇一種裝載組合；約束式（2）表示一個物品最多只能被裝載到一輛車的某個裝載組合上；約束式（3）表示每輛車必須嚴(yán)格按照裝載組合裝滿每種類型的物品；式（4）、式（5）定義了變量的取值范圍。

3　啟發(fā)式算法

鑒于問題的NP－難特性，問題規(guī)模變得很大時，利用線性混合整數(shù)規(guī)劃求解問題的精確解將變得非常困難。因此，本節(jié)采用貪婪技術(shù)提出快速有效地求解該模型的近似算法。構(gòu)造貪婪算法的基本迭代思想是：每一次迭代，僅選擇當(dāng)前狀態(tài)下迭代一步時得到的最好解，該方法不考慮迭代二步以上情況下的最優(yōu)解。當(dāng)算法迭代達(dá)到停止準(zhǔn)則時，算法停止，產(chǎn)生近似解［12］。貪婪算法被成功應(yīng)用于背包問題、拓?fù)渑判騿栴}、二分覆蓋問題、最短路徑問題、最小代價生成樹等最優(yōu)化問題的求解。在車輛的裝載組合選擇階段忽略每輛車只能選擇一個裝載組合的約束，每輛車的每個裝載組合都進(jìn)入篩選。第一階段，篩選階段。每一次迭代都將每個類型的物品分配到其裝載能力最高的裝載組合中，當(dāng)所有類型的物品都分配完時該輪篩選結(jié)束。第二階段，車輛選擇階段，如果某輛車裝載組合滿載，則選擇裝載總量最大的一個裝載組合。循環(huán)第一、二階段，直到所有車輛用完或剩余物品不能使任一剩余車輛的任一裝載組合滿載。最后采用最先滿足方法將選出的車輛裝滿相應(yīng)類型的物品。最先滿足方法是指在搜索過程中，選擇最先遇到的滿足條件的物品?；谕愋臀锲窡o差異的假設(shè)，本文選擇依據(jù)為物品的類型。終止條件：所有車輛用完或剩余物品不能使任一剩余車輛的任一裝載組合滿載。貪婪準(zhǔn)則：選擇當(dāng)前可用車輛的可用裝載組合裝載量最大的裝載組合?？捎密囕v是指在未滿載車輛組合中，可用裝載組合指對某種類型的裝載容量大于0且小于等于該類型未分配物品數(shù)。寬恕機(jī)制：當(dāng)出現(xiàn)某輛車的某個裝載組合多數(shù)類型的容量已滿足，未分配物品中存在可以使該裝載組合滿載的物品類型，則選擇未滿載類型數(shù)最少的車輛。顯然當(dāng)全部車輛都能滿載時總裝載物品數(shù)最多，貪婪準(zhǔn)則導(dǎo)致部分車輛因某種類型物品裝載量較低而不被選擇，設(shè)立寬恕機(jī)制可以提高車輛利用率。驟1；如所有裝載組合均不滿載，下一步。步驟4：找出所有存在某種類型的容量已滿足的裝載組合，且未分配物品中存在可以使該裝載組合滿載的物品類型，如果存在，則選擇未滿載類型數(shù)最少或裝載總量最大的車輛，將其放入VO，裝入的物品放入IO。將不在VO中的所有車輛的裝載組合的每個類型標(biāo)記為可用，返回步驟1；否則，算法結(jié)束。步驟5：計算滿載車輛數(shù)，裝載物品數(shù)。

4　數(shù)值實(shí)驗(yàn)與敏感性分析

本文在嵌入64位ILOG　Cplex12．2插件的Visual　Studio2008平臺上采用C＃語言編寫混合整數(shù)規(guī)劃和啟發(fā)式算法的程序軟件，并進(jìn)行各項(xiàng)實(shí)驗(yàn)。

4．1　數(shù)值實(shí)驗(yàn)問題規(guī)模由物品數(shù)n、物品類型數(shù)l、車輛數(shù)w、每輛車的裝載組合數(shù)j＿n等因素決定。根據(jù)實(shí)踐應(yīng)用的需求，設(shè)置裝載組合數(shù)區(qū)間為［5，10］，裝載總?cè)萘繀^(qū)間［8，12］，類型數(shù)為6，物品與車輛比例為10，根據(jù)物品、車輛數(shù)不同規(guī)模，設(shè)置了10組實(shí)驗(yàn)，分別測試混合整數(shù)規(guī)劃模型和啟發(fā)式算法的求解精度與速度。詳細(xì)實(shí)驗(yàn)參數(shù)設(shè)置如表3所示，實(shí)驗(yàn)數(shù)據(jù)為該參數(shù)設(shè)置下生成的隨機(jī)數(shù)據(jù)，每組實(shí)驗(yàn)生成50份數(shù)據(jù)，所生成的輸入數(shù)據(jù)如表4。

為在可接受的時間內(nèi)得出可接受準(zhǔn)確率范圍內(nèi)的結(jié)果，本文在求解程序中設(shè)置Gap值5％，求解時間1800秒。實(shí)驗(yàn)結(jié)果數(shù)據(jù)為具體的裝載方案，除了裝載物品總數(shù)和使用車輛數(shù)，也給出了哪些車輛的哪個裝載組合裝載的物品編號，如表5表示車輛2采用第5種裝載組合裝載物品67、107、116、176、179、181、227和232。統(tǒng)計結(jié)果數(shù)據(jù)時去掉第1份和第50份數(shù)據(jù)以避免干擾因素，每組算例給出了均值、最優(yōu)值和最差值，表6為算法的結(jié)果統(tǒng)計數(shù)據(jù)。

本文采用三個指標(biāo)來評價算法：求解結(jié)果與最優(yōu)值之間的比值，用Gap表示，Gap＝（最優(yōu)值－目標(biāo)函數(shù)值）／最優(yōu)值，最優(yōu)值通過ILOG　Cplex獲取，為模型獲得目標(biāo)函數(shù)值時的最優(yōu)值；車輛利用率＝求解結(jié)果中車輛使用數(shù)／輸入數(shù)據(jù)中車輛數(shù)；程序運(yùn)行時間。分別繪制混合整數(shù)規(guī)劃算法和啟發(fā)式算法Gap值、求解時間的平均值對比圖，見圖1。對比混合整數(shù)規(guī)劃算法與啟發(fā)式算法的結(jié)果，可以發(fā)現(xiàn)，基于貪婪技術(shù)的近似算法在運(yùn)行速度上有絕對的優(yōu)勢，但求解結(jié)果較最優(yōu)化算法較差，車輛利用率較低。

4．2　敏感性分析分析數(shù)值實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)車輛使用率平均值不足90％。原因?yàn)槊枯v車必須嚴(yán)格按照裝載組合滿載裝運(yùn)，裝載組合是制約車輛使用率的關(guān)鍵因素，同時車輛裝載組合數(shù)也是影響問題規(guī)模的因素之一，因此測試裝載組合數(shù)對車輛使用率與運(yùn)行時間的影響很有意義。選用500個分屬于6個不同種類的物品，50輛車分別進(jìn)行裝載組合數(shù)為5、10、15、20、25、30的數(shù)值實(shí)驗(yàn)?；趯?shí)際應(yīng)用中資源（時間、程序運(yùn)行內(nèi)存等）的限制，測試選用精確算法模型并設(shè)置Gap值5％，求解時間1800秒。記錄測試的平均Gap值車輛利用率、運(yùn)行時間，利用表7中平均車輛利用率和平均運(yùn)行時間，繪制每輛車的裝載組合數(shù)與運(yùn)行時間關(guān)系和車輛利用率關(guān)系圖2，可以看出車輛利用率隨著裝載組合數(shù)增加而提高，在每輛車15－2個時，車輛利用率達(dá)到峰值，之后緩慢下降。這是因?yàn)檠b載組合數(shù)增多求解難度加大，在有限的時間內(nèi)更難得出最優(yōu)解，達(dá)到5％Gap需要更長的時間，此時模型求解時間呈指數(shù)型增長。

影響問題規(guī)模的其他因素還有物品數(shù)、車輛數(shù)、類型數(shù)，其中類型數(shù)是算法內(nèi)置參數(shù)，類型數(shù)設(shè)置的好壞不僅影響物品調(diào)度的優(yōu)化程度，也是影響算法難解性的重要參數(shù)。研究類型數(shù)與求解時間的關(guān)系，對實(shí)際應(yīng)用有很好的指導(dǎo)意義。測試物品數(shù)500，車輛數(shù)50，每輛車裝載組合數(shù)10，每個裝載組合裝載總量［8，12］，表8記錄物品類型分別為3、6、9、12、15、18時的運(yùn)行時間，并用其平均情況、最好情況、最差情況以及物品平均裝載數(shù)繪制圖3。由圖3可以看出，隨著類型數(shù)的增加求解時間消耗降低，同時物品裝載數(shù)也迅速減少。在實(shí)際應(yīng)用中需結(jié)合實(shí)際物品特性與時間消耗、求解精度來合理設(shè)置物品的類型數(shù)。

篇10

［關(guān)鍵詞］ 供應(yīng)鏈； 能力分配； 多級制造； 約束滿足

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 18. 044

［中圖分類號］ F273 ［文獻(xiàn)標(biāo)識碼］ A ［文章編號］ 1673 - 0194（2012）18- 0078- 03

1 引 言

現(xiàn)代的市場競爭已經(jīng)不僅僅是企業(yè)與企業(yè)之間的競爭，更是供應(yīng)鏈之間的競爭。市場的瞬息萬變使得企業(yè)面臨著更大的挑戰(zhàn)，要想在激烈的競爭中處于不敗之地，供應(yīng)鏈的整合便顯得尤為重要。早在2000年，馬士華［1］便論述了核心企業(yè)在供應(yīng)鏈運(yùn)作中的地位，探討在供應(yīng)鏈企業(yè)間形成戰(zhàn)略伙伴關(guān)系過程中，處于主導(dǎo)地位的企業(yè)所起的作用及其影響因素。而供應(yīng)鏈整合［2］是企業(yè)有效拓展外部資源、實(shí)現(xiàn)運(yùn)作效率提升與綜合發(fā)展的主導(dǎo)方向之一。但長期以來，該整合過程普遍受制于“如何合理處理客戶服務(wù)滿意水平、資源整合成本與系統(tǒng)整合后運(yùn)營收益三者之間的悖論關(guān)系”，探索如何對復(fù)雜的供應(yīng)鏈進(jìn)行合理高效地整合、運(yùn)作與監(jiān)控，在滿足客戶個性化需求水平前提下實(shí)現(xiàn)供應(yīng)鏈系統(tǒng)各成員的當(dāng)前與長遠(yuǎn)收益是一個必須解決的課題。

國內(nèi)外很多學(xué)者就供應(yīng)鏈集成建模和優(yōu)化問題進(jìn)行了研究。Pinar和Bulent［3］針對單種產(chǎn)品、多供應(yīng)商、多生產(chǎn)商、多分銷商的三級產(chǎn)銷問題給出了混合整數(shù)模型。Chiung Moon［4］等就多工廠供應(yīng)鏈系統(tǒng)的集成工藝規(guī)劃與調(diào)度問題以總延遲最小化為目標(biāo)建立了數(shù)學(xué)模型，并設(shè)計了一種基于啟發(fā)式方法的遺傳算法進(jìn)行求解。姬小利［5］建立了面向供應(yīng)鏈的多產(chǎn)品、多訂單、多時段的訂單任務(wù)分配的混合整數(shù)線性規(guī)劃模型，并設(shè)計了基于遺傳算法和啟發(fā)式規(guī)則相結(jié)合的混合遺傳算法進(jìn)行求解。向晉乾［6］等以集團(tuán)利潤最大化為目標(biāo)，運(yùn)用優(yōu)化理論建立了單目標(biāo)0－1規(guī)劃的訂單分配模型并舉例說明模型的求解。朱寶琳［7］等針對供應(yīng)鏈中分散獨(dú)立的實(shí)體，利用市場價格和中間庫存因素使供應(yīng)鏈上下游企業(yè)結(jié)合成一個整體并建立一個供應(yīng)鏈一體化計劃模型，采用拉格朗日松弛技術(shù)對模型進(jìn)行求解。郭永輝［8］以面向訂單的制造模式為主要研究對象，采用集中式規(guī)劃思想，提出一套基于瓶頸思想的供應(yīng)鏈產(chǎn)能規(guī)劃方法。吳學(xué)靜［9］等研究了帶軟時間窗的分批配送問題及其對需求分配與生產(chǎn)調(diào)度的影響，以運(yùn)作成本最小化為目標(biāo)建立了數(shù)學(xué)模型，并設(shè)計了協(xié)同進(jìn)化粒子群優(yōu)化算法并進(jìn)行求解。齊二石［10］等基于對復(fù)雜零件制造的工藝流程的研究，提出了以工藝流程為核心的制造資源優(yōu)化配置模型，并最終將資源優(yōu)化配置問題歸結(jié)為多目標(biāo)優(yōu)化問題，并利用遺傳算法進(jìn)行求解。

現(xiàn)有研究很少關(guān)注在采購—生產(chǎn)—分銷的供應(yīng)鏈模型中的生產(chǎn)環(huán)節(jié)中上下游制造商之間資源的具體分配情況。而在現(xiàn)實(shí)生產(chǎn)中，在整個生產(chǎn)體系中上下游制造商之間往往會是多對多的關(guān)系，而且由于運(yùn)輸成本，各制造商的差異性等原因，在上下游制造商之間會出現(xiàn)優(yōu)先級的關(guān)系。本文對帶有多級制造商的供應(yīng)鏈（Supply Chain with Multi－stage Manufacture， SC－MM）資源配置方法進(jìn)行研究，應(yīng)用約束滿足技術(shù)進(jìn)行求解，并通過仿真實(shí)驗(yàn)和應(yīng)用案例對模型和算法進(jìn)行驗(yàn)證。

2 問題模型

2．1 模型描述

在圖1所示系統(tǒng)中存在多級的制造商，其中每一級的制造商所制造的產(chǎn)品均為下一級的制造商準(zhǔn)備，包括第一級的供應(yīng)商在內(nèi)，相鄰的兩級的供應(yīng)商或制造商之間的供給存在一個多對多的關(guān)系，而且每一個制造商所對應(yīng)的上游供應(yīng)商或制造商的集合中存在優(yōu)先級的關(guān)系。本文根據(jù)此類供應(yīng)鏈的特點(diǎn)建立數(shù)學(xué)模型，在分銷商產(chǎn)品需求一定的情況下，優(yōu)化每一級中各個供應(yīng)商或制造商對于其下游制造商的資源配置情況，從而使整個供應(yīng)鏈體系的產(chǎn)品利潤最大化、合同飽和度最大化以及產(chǎn)能利用率最大化。

2．2 符號定義

2.2.1 索引

m 最終產(chǎn)品制造商，共有M個最終產(chǎn)品制造商，1 ≤ m ≤ M；

im 第m個最終產(chǎn)品制造商制造的最終產(chǎn)品品種，共有I種最終產(chǎn)品，1 ≤ im ≤ I；

j 最終產(chǎn)品品種，共有I種最終產(chǎn)品，1 ≤ j ≤ I；

l 分銷商，共有L個分銷商，1 ≤ l ≤ L；

n 多級供應(yīng)鏈體系第n級，共有N級，1 ≤ n ≤ N；

nd 多級供應(yīng)鏈體系中第n級中第d個企業(yè)，總共Dn有個，1 ≤ d ≤ Dn；

p 產(chǎn)品品種（包括最終產(chǎn)品），共有P種產(chǎn)品，1 ≤ p ≤ P。

2.2.2 變量

其中，目標(biāo)函數(shù)（1）表示最大化產(chǎn)品利潤；約束（2）表示產(chǎn)品在分銷商的最大供給量約束；約束（3）表示供應(yīng)商或制造商供應(yīng)或生產(chǎn)的最大產(chǎn)能約束；約束（4）表示上游供應(yīng)商或制造商對下游制造商的最大供應(yīng)量約束；約束（5）表示下游制造商選擇上游制造商或供應(yīng)商的優(yōu)先級約束；約束（6）表示生產(chǎn)中某企業(yè)的上下游關(guān)系平衡約束；約束（7）、（8）表示流向變量，其中約束（7）表示若產(chǎn)品p不能生產(chǎn)產(chǎn)品q則沒有產(chǎn)品流量，約束（8）表示若產(chǎn)品p能生產(chǎn)產(chǎn)品q則一定有產(chǎn)品流量；約束（9）表示共享資源約束下的某企業(yè)生產(chǎn)量的計算公式；約束（10）表示共享資源約束下的某企業(yè)得到的分配量的計算公式。同時，在該多級制造供應(yīng)鏈中，每一個供應(yīng)商或制造商只供應(yīng)一種產(chǎn)品，但是，在同一級中的不同供應(yīng)商或制造商可能供應(yīng)的產(chǎn)品相同也可能不同。每個分銷商均會需求多個最終產(chǎn)品。