導語：如何才能寫好一篇數學建模調度問題，這就需要搜集整理更多的資料和文獻，歡迎閱讀由公務員之家整理的十篇范文，供你借鑒。

篇1

【關鍵詞】鋁箔 加工 排產 優化

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

1熱軋問題的使用方法

1.1數學規劃方法

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

1.2非數學規劃的方法

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

1.3數學模型的建立

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

上述的這些方法都是軋制生產中的優化排產的基本理論和方法。由于我國超薄鋁箔的生產不斷的發展，生產要求也隨之提高，在排產計劃和熱處理方面要使生產具有動態性就要根據具體實際進行任務的不斷完善和添加，隨時對排產計劃進行調整，排產的相關實時性要求和方法要快速的計算，增加可靠性和實用性特點。

2代數法建模

2.1符號函數的定義方法

I設置為鋁卷號，I=1，2...，P。J為設備的編號，J=1，2，...，M。工藝路線矩形陣R。R是n*m型矩陣，其中元素R表示鋁卷I在加工工藝路線中設備J所占的順序位。鋁卷號關系表E%表E中每行代表一個鋁卷號的屬性、各列分別表示物料編碼、爐架號、直徑、計劃開始時間、加工時間、設備編號、工藝順序號其中物料編碼、設備編號、工藝順序號、加工時間的數據來源于工藝路線矩陣和加工時間矩陣。圖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.爐架和鋁卷的幾何參數

2.2第一次排序

第一次排序是對訂單池中的鋁卷進行排序，排序按照重要的程度和緊急的程度進行安排，優化的準則體現在評價指數當中。對調度問題的NP難度性，要選擇計算量不大，計算時間不長的效果優化好的啟發式目標函數作為評判的標準。

兼顧能夠對設備的使用率提高、合同按照完工率和裝爐系數等進行多樣性目標的歸集，評價的指數可以參照鋁卷號和爐架號進行歸類。第一次排序是對任務中的全部鋁卷進行加工，按照從小到大的順序進行排序。

2.3第二次排序

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

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

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

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

2.4狀態賦值

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

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

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

在這里i表示設備k加工的上一道鋁卷，熱處理工序的狀態時間是在當前設備加工的前一個爐架的結束時間和當前鋁卷時間的最大值。

3結語

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

參考文獻：

篇2

【關鍵詞】車輛調度；物流配送；多車型

【中圖分類號】U492.2 【文獻標識碼】A

配送車輛調度問題是運籌學和組合優化領域的熱點問題.多車型配送車輛調度問題是配送車輛調度問題的一個分支，一般情況下，配送企業為了適應配送商品種類繁多、性質各異、客戶要求各不相同的情況，往往配置多種類型的配送車輛，以提高車輛的滿載率，降低配送成本.可見，研究多車型配送車輛調度問題具有重要的理論和現實意義.

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

1.對多車型配送車輛調度問題的描述

現實中的多車型配送車輛調度問題十分復雜，為了方便建模和求解，需要對現實問題進行一些抽象和簡化.現對本文研究的多車型配送車輛調度問題作如下描述：

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

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

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

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

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

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

2.構建數學模型

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

gi： 配送點i的需求量；

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

Kl：l車型的數量；

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

dij： 兩個節點間的最短距離，i，j∈V；

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

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

clkij： l型車的第k輛從第i點到第j點的費用，與距離和載重有關：

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

rlkij： l型車的第k輛從第i點到第j點車輛的重量；

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

式（1）表示目標函數，即總配送成本最小；

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

式（3）表示進入每個貨物需求點的車輛卸載后會離開；

式（4）、（5）確保每個貨物需求點只能被一輛車服務一次；

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

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

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

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

式（10）是經過某一配送點時車輛重量不能小于空車重量；

式（11）是l型車的第k輛從第i點到第j點的費用計算公式.

3.算法過程

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

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

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

點需求，車型參數（載重能力、空重、不同車型固定成本）等.任意選定一個初始解x0，記錄當前最優解為xbest，且令xbest=x0，令U（xbest）代表xbest的鄰域.

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

若當U（xbest）=φ時，或滿足其他停止運算的規則時，轉到第四步；

第三步：計算xnow的目標函數值minZ1，若xnow的目標函數值minZ1小于xbest的目標函數值minZ，則xbest=xnow，minZ=minZ1，U=U（xbest），轉到第二步；否則 U=U-xnow，轉到第二步；

第四步：輸出計算結果，停止.

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

4.實驗計算和結果分析

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

5.結 論

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

【參考文獻】

[1]楊浩雄，胡靜，何明珂.配送中多車場多任務多車型車輛調度研究[J].計算機工程與應用，2013，49（10）.

篇3

【關鍵詞】可分負載 任務調度 可分負載理論（DLT）

調度問題是并行分布式系統研究領域中影響系統性能的最主要的因素之一。常用的對并行分布式系統中任務調度問題的建模主要有兩種，一種是基于DAG圖的相關任務調度，另外一直是基于可分負載理論（DLT）的獨立任務調度。

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

可分負載的任務調度采用線性模型對網絡和應用進行建模，并且充分利用了負載可任意劃分的特性，可以使用數學的方法進行分析論證，使得很多重要類型的可分負載問題在特定情況下可以獲得近似最優解或最優解，這是可分負載的任務調度獲得成功的主要原因之一。

可分負載調度算法按對負載的分配方法可以分為：單輪可分負載調度算法和多輪可分負載調度算法兩種類型。

1 可分負載單輪調度

可分負載單輪調度算法就是指主處理機節點將負載劃分成塊數與從處理機節點數相等的子負載塊，然后一次性完成對子負載塊的分配處理。

可分負載單輪調度算法設計的主要難點是：

（1）確定主處理機節點給各個從處理機分發任務時的順序；

（2）確定給每一個從處理機節點分配多少負載量。但是由于后分配的從處理機都要較長的等待時間，所以單輪負載調度算法的效果不是很好。

可分負載單輪調度的研究成果有：

1.1 基本模型

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

1.2 考慮時間延遲的模型

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

（1）如負載足夠大，則所有的處理機都參與計算。

（2）所有參與計算的處理機都必須同時完成計算任務。

（3）當所有的鏈路是相同的時候則各處理機須按照c/w的升序進行負載的接收，如果鏈路速度不同、時間延遲不同則目前還找不到最優的分發順序。經過分析得出，單輪調度下的新的結論：當鏈路速度不同，通信延遲時間不同，各處理機計算速度不同時，當則應該按鏈路速度從大到小的順序進行負載的分發可得到在給定的比較大的時間內的最優調度。

1.3 考慮系統內存容量有限的模型

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

1.4 考慮結果信息返回的模型

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

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

2 可分負載多輪調度

可分負載多輪調度算法是指主處理機節點將應用劃分成塊數大于從處理機數目的子任務，采用并行多次分配的方法多次將子任務分給各個從處理機節點。其算法設計存在的難題是：

（1）如何確定負載劃分的塊數；

（2）每塊負載的大小如何確定；

（3）從處理機接收負載的順序如何。

可分負載多輪調度的研究成果有：

2.1 基本模型

有關文獻研究了在給定趟數時同構平臺下多輪可分負載調度，提出了MI算法，該算法用數學方法得到函數來解決負載塊大小的問題，且該文獻中給出為了得到好的調度，在分配負載的時候該遵循：

（1）各處理機在接收下一負載塊之前要完成當前負載塊的計算；

（2）各從處理機完成當前輪負載計算的時候主處理機也完成了下一輪負載的分發。

2.2 考慮時間延遲的模型

關于考慮時間延遲的XMI算法，但是該算法仍然沒有提出求解最優輪數的方法。為了使多輪調度更有效，學者們又提出了機群系統下考慮時間延遲的均勻多輪調度算法UMR，該算法通過在同構系統下采用每輪分配給各處理機節點負載量相同、異構系統下使每輪各處理機處理時間相同的策略，給出了求解最優調度輪數的方法，使整體的調度性能得到大幅度提高。在UMR算法的基礎上做了擴展，提出了一種可以得到更好調度效果的多輪調度算法RUMR，該算法考慮性能預測中可能存在的錯誤，通過先從小到大遞增負載塊，然后再遞減負載塊的方法進行負載的分配，使得算法更加實用。星型拓撲結構下可分負載的多輪調度問題以及在周期性調度中對相應參數進行優化的問題，并進一步證明了當負載量比較大時，若要得到近似最優的調度算法，應該要保證在通信過程中鏈路不出現空閑。

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

2.3 考慮系統內存容量有限的模型

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

2.4 考慮結果信息返回的模型

有關文獻考慮了同構系統下帶返回信息的多輪調度算法，該文獻分別研究了不考慮時間延遲和考慮時間延遲兩種情況，但該算法針對的是調度輪數給定的情形。在采用FIFO策略提出了異構機群系統上帶返回結果信息的可分負載多輪調度算法。

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

上面所有文獻資料中所提到的算法都是在從處理機接收完負載以后才開始計算（blocking通信模式），而在大型的應用以及實時系統中，這種模式是不適用的，所以在后面的文獻資料中提出了noblocking的通信模式，即從處理機在接收任務的同時就可以開始計算工作。并且得出近似的關于處理時間的表達式及最優的調度順序。可分負載調度在實際應用當中取得的效果，證明了可分負載調度的實用性。另外，隨著多核機器的出現，異構多核機群系統上的可分負載多輪調度算法，系統參數未知的多核異構機群上考慮結果信息返回模型的可分負載多輪調度算法。

3 結語

綜上所述，可分負載單輪的任務調度研究的比較透徹，而可分負載多輪的任務調度的研究成果就比較少，且已有的研究成果大多都是假設內存足夠大、結果的返回時間忽略的情形，且系統的所有參數都是事先確定好的靜態的調度，同時，大多數的研究都是在單核的機群系統上進行的，而在多核機器占主導地位的今天，今后研究在由多核機器組成的機群系統上的可分負載的任務調度就顯得尤為重要。

參考文獻

[1]李顯寧，鐘誠，楊鋒.異構集群系統的可分負載多輪調度算法[J].計算機應用研究，2008，25（4）：1028-1032.

[2]鐘誠，李顯寧.異構機群系統上帶返回信息的可分負載多輪調度算法[J].計算機研究與發展，2008，45（Suppl）：99-104.

[3]黎鶴，孫廣中，許胤龍.未知網絡中可分負載的分布式調度[J].中國科學技術大學學報，2009，39（8）：864-870.

[4]Cheng Zhong，Xia Li，Feng 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-），女，研究生學歷。碩士學位。現為廣西財經學院防城港學院教師。研究方向為網絡與并行計算 。

篇4

[關鍵詞] 仿真 物流系統 供應鏈

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

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

因此,物流系統仿真成為近年來國內外學術界研究的一個熱點問題。本文對物流系統中的供應鏈仿真、生產物流系統仿真和物流配送系統仿真進行綜述。

一、供應鏈仿真

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

近年來，很多學者進行了物流與供應鏈管理的仿真與建模方面的研究。高翔，林杰，張煒等仿真的供應鏈強調上游及下游企業問的信息共享與相互協作，并根據供應鏈中不同的信息做出相應的決策。它將整個供應鏈分為三層結構，即供應商、制造商和銷售商，此外還有運輸商負責不同層面之間的聯系，并通過建模仿真對系統進行優化，提高系統的整體適應能力。

朱衛峰，費奇針對復雜物流系統仿真及其現狀進行了研究，給出了復雜物流系統的網絡圖結構，提出了復雜物流系統仿真CLSim的總體結構，同時指出了復雜物流系統仿真研究的三個問題：復雜物流系統中的不確定性建模、復雜物流系統仿真模型設計與實現及復雜物流系統控制；并將復雜物流系統仿真設計的思想應用于敏捷后勤仿真系統，提出了基于時間步進的事件調度仿真策略，用實體流程圖法設計了敏捷后勤系統的仿真模型。

隨著電子商務的逐步普及，面向制造企業的傳統供應鏈的結構發生了變化，程曙等運用優化方法理論從供應鏈的系統性和整體性視角出發，對此種供應鏈的結構進行詳細的建模和仿真研究，尋找具體的決策優化方法，并探討了其中的目標函數、約束條件等關鍵性問題。

彭建剛在分析供應鏈管理的基礎上，提出“一流二網三關系”的供應鏈建模思想：“一流” 指訂單信息流；“二網” 指物流網和資源網；“三關系”指客戶關系、動態關系和集成關系。同時對供應鏈建模的混合整數規劃和統一優化方法論作了闡述，為供應鏈的建模提供了較為實用的方法。

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

在二級供應鏈研究方面，郭士正研究了服務銷售系統的二級供應鏈模型，是關于設施選址和市場顧客配置的混合整數規劃問題。在實例應用中，對奶制品零售分銷的供應鏈問題進行了計算機仿真計算。

二、生產物流系統仿真

生產物流是指從企業的原材料采購，車間生產，半成品與成品的周轉直至成品發送的全過程中的物流活動。生產物流系統是一個復雜的綜合性系統，如何提高其效率和效益是至關重要的，系統仿真作為一項用于系統分析和研究的十分有效的技術，已經被廣泛用來對生產物流系統進行規劃設計，運輸調度和物料控制等。

A．Sawhney(1999)將Petri網技術用于郵件處理中心，對整個處理中心的工作流程進行了分析與優化，提高了郵件處理的效率。

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

詹躍東基于Petri網建模理論，對煙草行業的卷接包車間的AGVS進行了分析，并對該系統構造了Petri網模型。

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

嵇振平等使用分層有色Petri網(HCPN)和事件操作表(EOL)的方法來減少復雜制造系統建模的復雜性，為物流仿真軟件體系結構的模塊化及層次化設計建立了良好的基礎，并將HCPN應用于寶鋼煉鋼連鑄生產物流仿真系統的建模中。

三、物流配送系統仿真

在現代物流系統中，配送中心是集物流、信息流和資金流為一體的流通型節點，是現代物流系統中的重要組成部分。對物流配送中心，特別是配送中心各個子系統的研究也越來越多。

在配送中心的多個子系統中，分揀系統是較為復雜的，同時又是其核心部分。邵明習等對物流分揀系統進行建模。主要對系統中的設備的選擇進行研究討論．著重描述了分揀設備的動態運行過程，以及速度的選擇對分揀效率的影響。

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

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

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

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

四、結束語

系統仿真作為解決復雜物流系統問題的有效手段，已經廣泛應用于生產物流系統、供應鏈及物流配送系統等研究領域。但是由于實際供應鏈的復雜性，目前的供應鏈仿真只停留在理論研究階段，未能有效地應用于實際的供應鏈管理中。對真實的復雜物流系統的仿真和總體優化是未來研究的方向和重點。

參考文獻：

[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]金淳劉昕露:供應鏈協調的仿真建模方法研究綜述[J]．計算機應用研究，2006，23(4)：1～3

[3]朱衛峰費奇:復雜物流系統仿真及其研究現狀[J].系統仿真學報，2002，l5(3)：353～356

[4]朱衛峰費奇:敏捷后勤仿真系統設計與實現[J]．計算機仿真，2003，2O(6):4～7

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

[6]彭建剛:供應鏈建模分析[J]．現代管理科學，2004，10：75～76

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

[8]郭士正盧震:二級供應鏈建模及仿真研究[J].集美大學學報:自然科學版，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]張穎利邵明習:企業生產物流系統的建模與仿真[J]．物流技術.2005(12)：62～65

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

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

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

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

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

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

篇5

針對連續泊位與橋吊集成調度大規模求解困難的問題，提出一種基于滾動策略的優化方法。首先，建立了最小化船舶偏離偏好泊位的成本以及延遲靠泊、延遲離港的懲罰成本的基本的多目標優化模型；然后，采用滾動調度方法根據動態抵泊的船舶抵達順序將調度過程分成連續的調度窗口，并設計窗口的平移策略、當前窗口對下一窗口的參數更新方式；對每個窗口內船舶進行調度優化，根據每個窗口內的優化結果，更新下一個窗口中數學模型的輸入參數；通過選取以船舶數量表示的滾動計劃窗口和凍結船舶的數量，持續滾動獲得每個窗口的最優解，疊加后獲得對所有船舶的靠泊計劃。通過算例分析表明，滾動調度能夠解決較大規模的調度問題，其效率受滾動窗口大小、凍結船舶數量及滾動次數影響。

關鍵詞：連續泊位分派問題；橋吊分配問題；滾動策略；混合整數規劃；集成調度

0 引言

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

BAP和QCAP是集裝箱港口運作優化領域的熱點問題。根據岸線是否連續，可分為離散泊位分派問題（Discrete BAP）[1]與連續泊位分派問題（Continuous BAP）[2]。在離散BAP中，岸線被分為多個泊位，船停靠時一般不能跨越多個泊位，只能處于某個泊位所限定的位置空間；連續BAP則把岸線看作一個整體，船舶通常可以在任意可以容納它的空閑位置作業。根據船舶抵港時間，可分為靜態泊位分派問題（Static BAP）與動態泊位分派（Dynamic BAP）問題。靜態BAP指在進行泊位分配時，所有需要安排作業的船舶都已經抵達港口[3]；而動態BAP是指泊位分配開始仍有船舶未到港，未到港的船舶會在分配時間段中的某時刻到達[4]。根據船舶抵達的動態性，依抵達順序形成序列，為滾動調度提供基礎。

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

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

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

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

1 基本模型

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

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

2.1 符號定義

（1）集合

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

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

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

（2）參數

1）：船的預期到達時間。

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

3）：船的長度。

4）：船預期離港時間。

5）：船的偏好泊位。

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

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

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

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

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

11）：可用橋吊數的總數量。

12）：表示時空點是否被占用。

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

14）：充分大的正整數。

（3）決策變量

1）：表示是否位于船舶的靠泊計劃矩形區域內，若是則為1，否則為0。

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

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

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

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

6）：表示集裝箱作業的完成時間，即當時，取的最大值+1。

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

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

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

10）：船舶遲于到港時間進行靠泊的時間差。

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

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

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

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

3）：表示占用時空點的船。

1.1 模型構建

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

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

2 滾動調度方法

滾動調度方法是對大規模問題的分解策略，將原問題分解為規模較小的子問題來進行求解，是解決大規模復雜問題的有效手段。劉越洋等[11]針對單機調度問題提出了一種滾動調度策略，有效解決了動態到達的工件在機器上有序加工的調度問題。靠泊計劃是一類多處理機任務調度[10]，能夠借鑒這一單機調度問題的滾動調度策略。在集裝箱碼頭作業過程中，船舶按照預定靠泊時間陸續到港，船舶按照抵達碼頭的先后順序，依次保存在待調度船舶集中等候調度。在滾動調度的操作過程中，將所有船舶分為己靠泊船舶集、待靠泊船舶集、未調度船舶集。其中，已靠泊船舶集指已完成裝卸作業或正在進行裝卸作業的船舶；待靠泊船舶集指在調度中的船舶，尚未開始作業；未調度船舶集指已經到港但調度計劃還未下達的船舶。每次滾動調度優化時，按照一定規則將完成裝卸作業的船舶從窗口中移除，并將未調度船舶集補充進船舶窗口中，運用優化算法對當前窗口船舶進行優化，得到該靜態調度區間的調度方案[10]。

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

約束函數式（2）～（10）和約束函數式（13）～（29）。

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

在t步的滾動結果中，根據調度結果中船舶的開始作業時間排序，取前λ個船舶凍結。λ為滾動調度策略的凍結窗口的長度，即窗口的平移間距。這λ個船舶的調度并入前（t-1）步的已調度部分S（t）構成下一滾動步驟（t+1）的已調度部分V（t），k（t）內未被凍結的剩余船舶包含在V（t）的補集中。然后從該補集中根據靠泊時間排序選擇前k個船舶組成新的滾動窗口k（t+1），如果剩余船舶數量少于k，則取全部剩余船舶。當V（t）包含所有船舶，即所有船舶都已經被調度，則滾動結束，最后一個滾動窗口內的優化調度結果全部執行。

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

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

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

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

步驟4 如果V=sls，即所有船舶都已經調度，則停止執行并返回；否則，更新t=t+1，轉到步驟2。

3 算例仿真

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

根據表1中數據（表中下劃線表示當前實驗下的最優解），采用Cplex作為混合整數規劃模型求解引擎，采用C#編寫滾動調度算法進行求解，得到48h內20條船的靠泊計劃如圖1所示。圖1中給出每條船舶的靠泊時間、離泊時間、靠泊位置，以及給出了所分配的橋吊數量。每個矩形代表船舶靠泊所占據的時空區間，數字代表該時刻分配給該船的橋吊數量。

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

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

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

通過控制凍結船舶的數量進行研究，從表1可以看出，隨著凍結船舶的增加，懲罰成本增加，滾動性能降低。這是由于系統靜態部分的影響。凍結船舶數量增加，每次調度前系統的靜態部分增加。即由前一次決策產生的調度，已經調度但尚未完成部分，也會降低系統的性能，影響優化結果。因為靜態的部分并未參與后一次的局部優化，導致局部優化并非局部最優。凍結船舶數量設置得過小，又會導致滾動次數過多，計算時間過長。在具體調度中，可通過合理設置凍結船舶的數量，減少靜態部分的影響，控制計算時間，提高滾動調度的整體性能。

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

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

表2中的6個實例中，采用滾動調度時，都求得了最優值，而一次調度在船舶規模增長到14條時，就已經內存溢出，無法計算出結果。表明較之于一次調度，滾動調度能夠大大降低計算難度，解決大規模問題。

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

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

4 結語

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

參考文獻：

[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] 楊春霞， 王諾.基于多目標遺傳算法的集裝箱碼頭泊位岸橋分配問題研究[J]. 計算機應用研究， 2010，27（5）： 1720-1725.

[11] 劉越洋，席裕.基于兩步滾動的單機調度算法研究[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] 何軍良， 宓為建，謝塵，等.基于分布式混合遺傳算法的動態泊位分配策略與仿真[J].上海海事大學學報， 2008，29（2）： 52-57.

篇6

關鍵詞:遺傳算法;GA;進化;最優化

中圖分類號:TP18 文獻標識碼: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

一、引言

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

二、遺傳算法基本原理

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

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

三、遺傳算法的主要特點及改進

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

(1)自組織、自適應和自學習性。

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

(3)遺傳算法不要求導或其他輔助知識,而只需要影響搜索方向的目標函數和相應的適應度函數。

(4)遺傳算法強調概率轉換規則,而不是確定的轉換規則。

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

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

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

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

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

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

(3)采用動態自適應技術,在進化過程中調整算法控制參數和編碼粒度;

(4)采用非標準的遺傳操作算子;

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

四、遺傳算法的應用領域

遺傳算法經過幾十年的發展,逐漸被人們接受和運用,遺傳算法的應用研究比理論研究更為豐富,下面是遺傳算法的一些主要應用領域[4]:

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

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

(3)自動控制:在自動控制領域中許多與優化相關的問題需要求解,遺傳算法的應用日益增加,并顯示了良好的效果。例如用遺傳算法進行航空控制系統的優化、基于遺傳算法的參數辨識、利用遺傳算法進行人工神經網絡的結構優化設計和權值學習,都顯示了遺傳算法在這些領域中應用的可能性。

(4)機器人智能控制:機器人是一類復雜的難以精確建模的人工系統,而遺傳算法的起源就來自于對人工自適應系統的研究。例如遺傳算法已經在移動機器人路徑規劃、關節機器人運動軌跡規劃、機器人逆運動學求解、細胞機器人的結構優化和行動協調等方面得到研究和應用。

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

五、總結

遺傳算法作為一種非確定性的模擬自然演化的學習過程的求解問題方法,在很多領域具有廣泛的應用價值,但其在很多方面有待于進一步研究、探討和完善。可以預期,隨著計算機技術的進步和生物學研究的深入,遺傳算法在操作技術和方法上將更通用、更有效。

參考文獻:

[1]王煦法.遺傳算法及其應用.小型微型計算機系統,1995,2

篇7

關鍵詞 網絡控制系統；信息調度；靜/動態調度；混合調度；調度與控制協同設計

1　引言

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

2 　NCS中的信息特征與信息調度概念

在NCS中網絡傳輸的信息主要分為兩類：實時性信息和非實時性信息[3]。實時性信息對時間要求非常苛刻，如果在規定時間的上限內某一信息未能起作用，則該信息將被丟棄，啟用最新的信息。而在NCS信息調度策略中主要調度兩類數據信息：周期性信息和非周期性信息。周期性信息是一種實時性信息，一般要求在傳輸周期時間內必須傳送給目標節點，周期性信息也被稱為時間觸發信息或者同步信息。非周期性信息是指節點間的請求服務等信息，它們的發生時刻是隨機的，非周期性信息也被稱為事件觸發信息、異步信息或者隨機性信息。

此外，在NCS信息調度中不能忽視突發性信息，突發性信息指一些事先無法預知的突發性的或者隨機的事件（例如報警信號、異常處理等），這類信息必須在一定時間內給予處理，否則系統可能出現異常甚至癱瘓。

在網絡控制系統中，信息調度發生在應用層，即傳感器、控制器與執行器之間信息傳遞的過程中。當系統網絡中某節點發生數據傳輸碰撞時，信息調度規定節點的優先發送次序、發送時刻和時間間隔，以避免網絡沖突。

在NCS中，如果網絡控制系統的所有數據傳輸都能在任務時限內完成，則稱網絡控制系統的傳輸是可調度的。

3　典型的NCS信息調度算法

目前對網絡控制系統中信息調度的研究主要分為調度與控制的分開設計和調度與控制的協同設計。

3.1　調度與控制的分開設計

在NCS的研究中，一類研究是針對通信網絡，研究提高網絡服務質量的信息調度方法；另一類研究是在一定的網絡信息調度方法基礎上，研究提高NCS性能的控制方法。因此，信息調度方法對改善NCS性能起著很大的作用。

根據信息對實時性的要求，信息調度分為靜態調度（又稱離線調度）、動態調度（又稱在線調度）和混合調度。

3.1.1　靜態優先級調度

目前靜態調度算法很多，本文著重介紹以下幾種典型的算法以及算法的改進。

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

截至時間單調調度模型(Deadline Monotonic Scheduling Model )策略的任務優先級由任務時限來決定。該調度算法要防止任務越過其時限而得不到調度，從而影響系統的實時性。當任務周期和時限相同或者所有同步周期性任務時，DM算法都是最佳靜態調度算法。

由Hong等提出的基于時間窗的靜態帶寬調度算法避免了數據在網絡傳輸過程中產生干擾和數據沖突。Hong等還將該調度方法應用于循環服務型NCS和CAN 網下的NCS中。

劉魯源[6]等鑒于該調度方法只限于調度網絡中的周期數據，提出基于同步相和異步相的時間窗調度算法，使非周期數據也可以采用該基于時間窗的靜態調度算法。

3.1.2　動態優先級調度

在動態優先級調度算法中，任務的時間約束關系并沒有完全確定，新任務的到達時間是未知的。下面介紹幾種經典的動態優先級調度算法。

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

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

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

Otanez 等[9]人提出的基于死區的動態調度在確保系統性能的基礎上動態地丟棄一定比率的數據，以減輕網絡的負荷。但是當多個獲準訪問網絡的數據包同時競爭網絡資源時，該策略不能確定數據包發送的優先級。

基于業務平滑的動態調度是Kewon等利用業務平滑的技術控制Ethernet網的通信量，通過在Ethernet 網的UDP( TCP/ IP) 層和MAC 層插入定速率業務平滑器和自適應業務平滑器以限定MAC 層數據包的到達速率，并且保證網絡誘導時延的有界性，從而提高網絡的服務質量.

Cena等提出的優先級提升—分布式優先級排隊調度( PP-DPQ)可以保證實時數據傳輸最大間隔具有確定上界，非實時數據在傳輸中公平地競爭網絡資源。

基于時間窗的動態調度（Dynamic Time Window）是Raja對基于時間窗的靜態調度算法進行改進，提出優先級循環服務和動態時間窗的帶寬分配策略。

模糊動態調度是白濤[13]等將模糊控制理論引入到NCS 信息調度中，利用基于IF2THEN 規則的模糊邏輯確定數據傳輸的優先級。

3.1.3　混合調度

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

3.2　調度與控制的協同設計

目前關于控制與調度共同設計成為研究熱點受到越來越多的重視，大體可分為開環調度和反饋控制實時調度兩方面。

3.2.1　開環調度

1）對NCS 中各個控制環中數據傳輸節點采樣周期和采樣時刻的調度

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

2）調度優化

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

3.2.2 反饋控制實時調度

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

4 進一步可研究的參考方向

當前，NCS信息調度的研究已經取得了很多有益的成果。然而，NCS應用的復雜化以及NCS控制與調度的協調設計趨勢，使得現有的信息調度方法已不能滿足發展的需求。因此，給出信息調度的進一步研究問題和研究目標，以供參考。

（1）網絡控制的復雜化和網絡運行狀況的多變性，需要智能化強、實時性好的在線調度算法。

（2）現有的研究結果大多限于單控制回路，對共享網絡的多個控制回路的優化調度等問題需要進一步的研究。

（3）有帶寬約束的變速率網絡化控制系統的信息調度問題。

（4）不同數據流分配不同比例帶寬，用來提高高優先級別數據流的服務質量，避免低優先級別的數據流由于網絡超時而斷開的研究。

（5）研究NCS 多目標優化問題的提取和求解。考慮網絡利用率、數據包丟失率、系統穩定性等多重約束，建立NCS 多目標優化問題的數學模型。進而考慮NCS 的實時性要求，研究基于遺傳算法等進化智能計算方法的NCS 分級多目標優化問題的求解方法。

（6）將系統性能的優化映射為較低層次的系統參數優化、網絡參數選取、帶寬資源調度問題，力求達到系統設計與網絡實現的總體性能優化的目標。引入新的、更多的反映系統性能的優化指標，尋求新的融合網絡與控制系統其它結合點將是未來的發展方向。

參考文獻

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

[2] 湯賢銘，錢凱，俞金壽.網絡控制系統動態死區反饋調度.華東理工大學學報[J].2007，33(5)：716-721

[3] 張慶靈，邱占芝.網絡控制系統[M].北京市：科學出版社，2007.37-38

[4] 文遠保，張炫.單調比率調度算法研究及改進.計算機工程與科學[J].2006，28(10)，68-70

[5] 葉明，羅克露，陳慧. 單調比率(RM)調度算法及應用.計算機應用[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] 張奇智，曹春生，張衛東.EDF 調度方法在交換式工業以太網中的實現.化工自動化及儀表[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] 劉懷，費樹岷.基于EDF的分布式控制系統容錯調度算法.軟件學報[J].2003，14(8)1371-1378

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

[12] 王智. 面向現場總線的分布式實時系統的建模與分析方法[D]. 博士，中國科學院，2000

[13] 白濤. 網絡控制系統的性能分析與調度優化[D] . 碩士，上海交通大學，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 協議的網絡控制系統靜態調度算法的研究.控制與決策 [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

論文摘要：運用虛擬現實仿真 (VRS)進行實驗教學是激發學生學習興趣的有效途徑。針對大學生的學習特點，分析了傳統教學方法的不足，探討了基于虛擬現實仿真的“生產與運作管理”實驗教學的特點、內容和形式，有助于高校教師優化教學過程，提高教學質量和教學效果。

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

1 生產與運作管理課程的教學調查和教學方式的分析

1．1 教學調查

在浙江省精品課程 “生產與運作管理”的建設過程中，為了有針對性地開展課程教學方法改革，我們就本課程的學習，于2007年對我校 04級工商管理專業40名學生做了一次調查，得到如下結論：

(1)由于學生沒有實際工程背景，缺乏對企業生產與運作管理的感性認識，對于生產與運作管理的一些理論和方法理解有一定困難；

(2)學生對生產與運作管理課程的認識存在誤區，對相關理論知識掌握不熟練，對未來是否從事生產管理工作信心不足，導致學習該課程的動力不足：

(3)隨著非制造業在國民經濟中地位的提升以及制造業和非制造業現實的工作性質、工作環境和條件、工資待遇等方面的差異，決定了學生對以制造業為主體的生產與運作管理課程熱情不高；

(4)學生對傳統的案例討論、觀看錄像、企業參觀、專家講座、計算機輔助教學等教學模式基本認可，但是對創新教學方法和手段的需求更為強烈。

1．2 教學方式分析

生產與運作管理是一門實踐性、操作性強的課程，教學 的關鍵是讓學生產生 “真實感”。教學方式除了課堂授課外 ，傳統的教學方式主要有如下幾種 。

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

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

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

這種方法在實施中存在困難，主要是沒有建立固定的教學基地，與企業沒有穩定的關系；而且，隨著學生人數的逐年增多，許多企業對學生參觀不感興趣。

(3)邀請企業專家講座。對于某些實務性、技巧性比較強的內容，如生產調度、員工指派、班組建設、現場改善等，請企業專家結合自己的工作實際，現身傳授管理技巧和經驗，比任課教師講效果好，印象深。

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

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

目前好的生產與運作管理案例不多，主要問題是：案例篇幅太長，描述性內容多，真正反映生產與運作管理的實際數據和實際場景模擬少，教學效果不佳。

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

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

2 虛擬現實仿真技術在“生產與運作管理”教學中的應用

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

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

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

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

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

總之，虛擬現實仿真技術在制造業的應用已經貫穿于產品設計開發、生產計劃制定、加工、裝配、測試和銷售的整個生命周期。

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

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

3 結束語

生產與運作管理是一門實踐性很強的課程，從增加現實場景模擬、加強課堂師生互動、強化理論與實際結合等方面不斷創新多樣化的教學方法，對學生進行實踐技能和科學研究方法的訓練，不僅有助于學生鞏固課堂所學知識，加深對生產與運作管理基本概念、基本原理和分析方法的理解，掌握從事企業生產與運作管理活動的基本技能，而且，能夠拓寬學生的知識領域，鍛煉學生的實踐技能，培養科學嚴謹、求真務實的工作作風。

參考文獻（References)：

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

[2]陳志祥．MBA《生產與運作管理》課程建設與教學方法研究[J]．教育與現代化，2006(3)：3．8．

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

[4]王亞超，馬漢武．生產物流系統建模與仿真 [M]．北京：科學出版社，2006．

篇9

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

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

2　問題描述及數學建模

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

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

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

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

3　啟發式算法

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

4　數值實驗與敏感性分析

本文在嵌入64位ILOG　Cplex12．2插件的Visual　Studio2008平臺上采用C＃語言編寫混合整數規劃和啟發式算法的程序軟件，并進行各項實驗。

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

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

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

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

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

篇10

［關鍵詞］ 供應鏈； 能力分配； 多級制造； 約束滿足

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

［中圖分類號］ F273 ［文獻標識碼］ A ［文章編號］ 1673 - 0194（2012）18- 0078- 03

1 引 言

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

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

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

2 問題模型

2．1 模型描述

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

2．2 符號定義

2.2.1 索引

m 最終產品制造商，共有M個最終產品制造商，1 ≤ m ≤ M；

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

j 最終產品品種，共有I種最終產品，1 ≤ j ≤ I；

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

n 多級供應鏈體系第n級，共有N級，1 ≤ n ≤ N；

nd 多級供應鏈體系中第n級中第d個企業，總共Dn有個，1 ≤ d ≤ Dn；

p 產品品種（包括最終產品），共有P種產品，1 ≤ p ≤ P。

2.2.2 變量

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