一種面向柔性生產的動態調度模型

摘 要:為解決柔性生產中兩個生產單元與多作業對象的優化調度問題，提出一種基于能力平衡的動態調度模型。將生產單元模型化為一種容器，把生產能力視為容積，并劃分為設定能力和機動能力。通過建立兩單元的機動能力連通模型，根據流體力學原理提出了一組動態調度規則，并開發了可用于現場調度的高效的啟發式優化算法。在滾裝運輸企業進行的案例研究表明，該模型及其算法在實際生產運作中具有切實的可行性和有效性。

關鍵詞:柔性生產; 動態調度; 能力平衡; 啟發式算法; 滾裝船

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2009)09-3239-03

doi:10.3969/j.issn.1001-3695.2009.09.010

Dynamic scheduling model oriented to flexible production

LIU Xiao-bing LI Zhong-kai HUANG Xue-wen SONG Qing-jie2

(1.School of Management， Dalian University of Technology， Dalian Liaoning 116024， China; 2.Dept. of Operations Management， Dalianwan New Port Service Company， Dalian Ocean Fishery Group of Corporations， Dalian Liaoning 116113， China)

Abstract:To optimize scheduling pertaining to two production units and many tasks in flexible production， this paper proposed a dynamic scheduling model， considering capacity balance. Modeled each production unit as a kind of container whose capacity symbolized the throughout. Divided the capacity to planned and spared parts. Joining spared capacities in two units to build a connected vessel， created the state-of-art dynamic scheduling rules according to the hydromechanical theory， and developed a practical heuristic algorithm for the model. Tested the model was as feasible and effective in a case study conducted at a ro-ro shipping company.

Key words:flexible production; dynamic scheduling; capacity balance; heuristic algorithm; ro-ro ship

在21世紀的新經濟時代，柔性技術作為一種有效的應對環境不確定性的理論和方法[1]，在多種研究領域中受到重視。其中柔性生產技術在提高生產效率和增強企業競爭力方面具有重大的現實意義和研究價值，因而柔性生產的動態調度算法和模型得到專家學者的廣泛關注，典型研究有反饋調度、自適應調度、適時調度、在線調度等[2]。由于柔性調度問題的復雜性，一般其求解需采用結合多種算法的混合式算法[3， 4]、增加多種特殊的規則[5， 6]，或使用減少計算量的約束[7]或算子[8]等各種措施，這些算法一般需較多的參數和良好的運算環境，因而在實際生產過程中的應用還較少。各行業和企業的生產方式和組織形式存在較大差別，為了提高動態調度的效率和可行性，研究針對典型的具體情形的模型和解決方案是必要的。

在船舶滾裝運輸的生產管理中，存在一種典型的兩個生產單元和多個作業對象的動態調度問題。對于每一艘船舶的裝載問題，屬于典型的背包問題，即將有限種數的具有一定長度和價格的車輛安排到船舶上多個車道中，以獲得最佳經濟效益。同時每個車道具備特殊的約束，如不能裝載超過某長度的車輛等。對于單船舶的標準優化裝載問題，可在作業開始前預先使用線性優化等方法得到最佳優化方案。然而，由于市場需求的不穩定性和裝載過程中的意外事故等因素，每個船舶的優化配載方案幾乎不可能完全得到執行。必須對兩兩相鄰的航班之間進行動態調度，以減少虧艙，即生產能力的剩余和浪費。由于滾裝運輸生產的即時性等特殊要求，需要一種新的動態調度模型來提高其生產柔性，解決生產過程中的多種不確定性引起的問題。

本文借鑒推動式和拉動式排產調度模型[9]的原理，根據兩個生產單元能力平衡的需要，建立了一種兩個生產單元的生產能力連通和平衡模型，并根據流體力學原理提出了這種動態調度模型的調度規則和求解算法。該模型根據現實的生產需求建立，其算法簡潔直觀，可以在生產作業現場中得以實際應用，有效提高生產柔性，增加生產效率。

1 模型描述

每個生產單元分別具有包括各種作業對象類型和數量的最佳作業方案，但該方案只能作為參考方案。為應對需求變動等不確定因素，針對每個生產單元只將一部分生產能力分配給計劃內必須完成的任務，稱為設定能力，而將其他的生產能力稱為機動能力。在計劃任務完成時，可根據動態算法的決策結果來決定是否使用機動能力和選擇哪些生產任務作為機動任務進行作業，以達到生產效率的最優化或接近最優化。而對于兩個時間或空間上相鄰的生產單元，則需要決定如何調度兩者的機動能力和協同完成機動的作業任務，以達到最佳生產效率。

1.1 單個生產單元的控制

對于單個生產單元，將其模型化為一種柱狀體容器，其生產能力即容器的容積。生產任務被模型化為液體，生產任務被執行時，認為容器被注入液體。生產單元模型的容積不直接對應物理的生產作業量的生產能力，而是表示為與優化目標對應的表示經濟效益的生產能力。相應地，在制訂生產計劃時，把生產任務也分為兩部分，即上文所述的計劃任務和機動任務。生產單元的容器化模型如圖1所示。

如圖1所示，陰影所示的部分即設定的容積，虛線表示液面。與該模型有關的關鍵屬性和變量如下所列，并可分別應用于根據生產過程劃分的計劃階段和生產階段即動態調度階段。

C:設定的容積，即生產開始前預先優化得到的應完成多種作業任務的計劃生產能力;

C′:保留的部分容積，即機動的生產能力;

V:計劃任務部分所對應的液體體積，標志生產能力的占用情況;

V′:生產任務的機動部分所對應的液體體積，標志生產能力的占用情況;

H:容器的高度，標志該生產單元的總生產能力;

h:計劃任務部分所對應的液體高度，標志生產任務完成情況;

h′:生產任務的機動部分所對應的液體高度，表示機動作業任務完成情況;

S:容器的截面積。

為了簡化模型的求解，可將所有生產單元的截面積S均設為1單位面積，則在數量關系上有

V=h(1)

V′=h′(2)

C+C′=H(3)

且h+h′≤H。

一般來說，C′所占的比例較小，具體由決策人員根據當時季節的市場情況和其他統計數據等來確定。生產作業開始執行時，計劃內的作業任務首先被執行，即容器中開始注入液體。當生產任務進行至液體體積V達到C 時，即進入動態調度階段，此后必須同時考慮相鄰的生產單元，以協同完成機動生產作業任務。

1.2 相鄰生產單元的動態調度

使用兩個時間或者空間上相鄰的生產單元模型，其編號分別為1、2，可建立如圖2所示的動態調度模型，在兩容器的設定容積對應的高度以上安裝導管使之構成一種連通器， 以此使兩者的機動生產能力可以協同完成生產任務并獲得最佳生產效率。兩個生產單元模型中的參數變量分別使用其編號作為數字下標來區分。為了更加靈活地調度生產任務，以更有效的方式配置資源，對每個生產單元模型增加一個變量，即在容器下放置高度分別為L1、L2的底座，以此可獲得多種能力平衡狀態，使得兩個生產單元可以提供不同程度的優先作業。

當被分配至兩個生產單元的計劃任務都已完成時，才可以連通兩者的機動生產能力，進行動態調度。此時，設定生產能力不一定恰好被完全占用，有可能由于計劃內作業的特殊情況導致設定生產能力未用盡或部分機動能力已被占用。根據動態調度的結果，每個作業對象由被選擇的生產單元完成。每一次作業結束后，立即與最新的作業任務情況一起被初始化為下一調度過程的起始條件，對下一個作業活動的調度產生影響。根據作業完成后的反饋和上級作業計劃的信息，如果機動任務按照預訂計劃完成，占用了正常的生產能力，而且同時沒有新的機動任務被上級作業計劃管理系統分配，則不重新進行調度，而是繼續執行既定的機動作業隊列;否則，需要重新運行動態調度算法，產生新的調度指令。通過這種對最小的可調度生產作業活動的動態調度，可最大限度地達到模型中所示的流體力學所產生的最佳能力平衡效果。

該動態調度過程的目標是在完成計劃的作業任務之后，最大限度地利用機動生產能力，進一步提高經濟效益。該優化目標的特殊性在于，不需要考慮已完成的作業任務，而只考慮將來可以完成的機動任務。根據模型的設計和特性分析，其優化目標和重要約束如下所示:

max f([λ0…λi…λI])=

∑Ii=0[piλi(2-λi)+p′iλi(λi-1)/2](4)

s.t.λi∈{0，1，2}

h1+∑Ii=0[piλi(2-λi)]≤H1

h2+∑Ii=0[p′iλi(λi-1)/2]≤H2

其中:λi表示機動兩作業任務隊列中相應作業對象的調度結果，即0表示不被任何單元接受，1表示分配到生產單元1，2表示分配到生產單元2;pi表示被生產單元1對第i+1個作業對象的收益;p′i則表示生產單元2對第i+1個作業對象的單位收益，其約束條件分別為兩個生產單元的生產能力約束。

由于生產單元在時間或其他方面的差異，同一作業對象由不同生產單元完成時，其收益是不同的，同時認為動態調度的結果不引起成本的變動。例如在滾裝運輸中，存在船只、出發時間等引起的價格差異，而每個航班的成本則幾乎不受機動作業任務的影響。一般來說，其原因是生產過程中固定成本的比重特別大。本模型可以通過調整參數L1和L2來調整生產單元的優先順序，參數較小的為優先的生產單元，且兩參數差越大，其優先程度越高。

在串聯的連續工序上，存在著為達到生產能力均衡目的而建立的推式或拉式排產調度模型，而對于本動態調度模型中在一定程度上并列的兩個生產單元，則可利用連通器內由流體力學原理決定的液體平衡規律，使用如下規則調整既有方案，以獲得達到能力平衡的方案:

當L1+h1+h′1=L2+h2+h′2時，達到能力平衡，接受該方案。

當L1+h1+h′1

當L1+h1+h′1>L2+h2+h′2時，將分配到生產單元1的部分機動任務調整到生產單元2。

由于實際生產調度一般不可能達到液體平衡的效果，可設置一種近似平衡，作為可接受的調度結果。設a為可接受的兩個生產單元的作業任務的經濟效益差別，則當滿足如下公式時，即認為達到了生產能力的平衡:

L1+h1+h′1-(L2+h2+h′2)≤a(5)

根據式(5)，上述調度規則可調整為

當L1+h1+h′1-(L2+h2+h′2)≤a時，達到能力平衡，接受該方案。

當L1+h1+h′1+a

當L1+h1+h，1>L2+h2+h，2+a時，將分配到生產單元1的部分機動任務調整到生產單元2。

該優化問題屬于一種較復雜的背包問題，同時因為其現實應用的需要，必須尋求一種快速有效的算法，以迅速得到優化解決方案。在實際生產中，機動任務隨時會發生變化，而生產過程需要連續進行，生產作業的結果對生產能力也可能產生無法預期的影響，因此，不可能得到理想化的最優調度結果。針對動態調度的實際情形，可采取適當的優化算法，忽略部分細節，簡化調度過程，得到接近最優的調度計劃，并設定規則分階段調整調度計劃，從而達到根據生產過程進行動態優化調度并使調度結果實際可行的目的。

2 算法設計

對動態調度模型的求解可采取兩類算法:一類是傳統優化方法，如數學規劃、調度規則、仿真優化等方法;另一類是智能調度算法，如使用專家系統、神經網絡、多代理、啟發式算法等方法[2]。本文的動態調度模型對計算速度方面的要求非常高，同時又處于整個生產過程中的后期調整階段，屬于對生產過程的再優化和對生產能力平衡的再處理，因此，可選擇使用具有顯著的速度優勢的一類啟發式算法來求解該模型。

根據企業生產管理的實際需要，對于生產現場的動態調度，其每次計算的用時最長不應超過5 s。其中包含在服務器與用戶手持設備等終端之間的傳輸時間。針對本文動態調度模型的特點，在動態調度模型中，可使用簡便快捷的啟發式優化算法，并充分利用生產過程中既有規律的優勢，以更高的可能性在最短時間內搜索到近似最優解。

在相鄰生產單元的能力連通動態調度模型中，應盡可能利用多種提高經濟效益的已知措施。對于作業對象和生產單元，應優先選取性價比更高的產品;優先使用由時間要求、定價策略等多種因素決定的優先生產單元。初始的機動作業任務的集合，應由更高級的作業計劃管理系統提供，其屬性滿足每個生產單元的約束條件。從動態調度算法開始執行直到計算結果被接受期間，只考慮該集合和剩余的機動能力等既定的初始條件。利用這些已知的規則和規律，根據模型設計和實際生產過程的需要，可開發具有如下關鍵步驟的簡化啟發式優化算法:

a)設定所有的初始條件和約束條件，包括可接受的兩生產單元作業任務的經濟效益差a及其遞增量Δa，并設定枚舉次數限制參數S，鎖定機動作業任務的集合。

b)生成默認機動作業任務隊列。分別把兩個機動作業任務隊列根據其作業對象的性價比由高到低排列，作為默認的作業順序。

c)枚舉下一方案。根據基于能力平衡的動態調度規則多次調整方案，以獲得新方案。每次枚舉均取一方隊列的首個作業對象，調整到另一隊列并插入合適的位置。同時累計枚舉次數L。當L≥S時，直接轉入e)。

d)驗證相關的約束條件。如果不滿足約束條件，則不能接受該作業隊列，放寬能力平衡約束:將a的值增加Δa，轉入c);否則，可以接受該作業隊列組合，進入e)。

e)接受當前機動作業任務隊列，給出調度指令，即兩個生產單元的下一作業對象和機動作業任務有序隊列，結束本次調度。

在兩個生產單元中只有其一已完成設定生產任務時，調度算法仍可正常運行。由于未完成設定生產任務的生產單元不執行動態調度指令，從而不會給出反饋，其機動作業任務隊列可隨著動態調度的過程繼續優化，而不會發生錯誤。

為了保證算法的即時性和實用性，相關參數應根據作業對象種類的分布情況、市場飽和程度和生產現場情況等多種因素進行適當調整。如果某作業對象被足夠多個作業單元拒絕后，動態調度系統應反饋給其上級作業計劃管理系統，使其列入下一作業單元的設定能力內，以保證客戶滿意度。為了避免在特殊情況下算法執行時間過長，除對算法執行次數進行限制外，還可以采取限制總執行時間的措施。在市場極度飽和或極度貧乏等特殊情況下，則可以不使用動態調度，而是由管理人員制訂更簡單直觀的操作規則，直接應用到實際調度操作中。

該算法計算量小、效率高、適合于支持現場操作。如果在一次指令被正常執行且能力占用等輸出正常，同時沒有新的機動任務加入，則可以不重新調度，繼續使用既有的機動任務隊列，從而節省資源，進一步提高效率。通過綜合利用啟發式算法和規則的優勢，這種針對兩生產單元的動態調度，可在多種生產狀況下，通過平衡生能力達到提高綜合經濟效益的目的。

3 應用實例

本文動態調度模型在遼寧省大連海洋漁業集團下屬的大連灣新港港務公司得以實際應用。該港務公司與煙臺渤海輪渡有限公司合作運營滾裝運輸業務，目前經營五艘大型滾裝船，每天在大連與煙臺之間往返十個航班。由于滾裝運輸具有裝卸方便、快捷的特點，滾裝碼頭可以給客戶提供近乎“來車即上”的服務，這同時也增加了裝載過程中的隨機性，使得難以達到裝載的最優化。針對這種隨機和動態的特點，通過對滾裝船的裝載系數和車輛的有關屬性進行定義，設計了優化裝載作業流程，基于動態調度模型，充分利用相鄰航班即生產單元的能力連通特點，提高了滾裝作業效率，取得了可觀的經濟效益。

車輛作為滾裝作業對象，可根據其占用船艙中車道的長度確定其價格，而船艙中車道的長度即船舶的作業能力。在優化方案設計中，作業能力表示為經濟效益，不直接使用車道長度的等比公式，而是需要考慮影響裝載效率、對車道的特殊要求和各服務環節中的費用等多種因素，如式(6)所示:

p=∑Nn=0anln(6)

其中:l為占用的車道長度，an是第 n+1種與價格有關的參數。由此可知，車輛的差異對經濟效益影響非常顯著。因此，在該港務公司的現場滾裝作業中，采取了設定機動作業能力和進行動態調度的措施，以減少作業能力的浪費，同時提高了作業柔性，避免因為計劃過于呆板和對意外情況反應遲緩而造成的客戶滿意度下降。

為了在生產作業中實施動態調度，應采取一系列輔助措施。對于售票系統，在設定能力被完全使用后，應在機動能力限制內售出候補票，即需要根據動態調度的結果決定其航班和具體登船順序及時間的機動作業任務。在滾裝碼頭，則需要合理規劃停車場地和登船口等位置，以便于順利調度車輛，減少每次調度作業的時間。同時，需要使用無線網絡、手持終端等信息化手段，以進行傳輸和接收調度指令、反饋調度結果等操作。合理規劃和實施功能完善的信息化整體解決方案，可增加信息傳遞的準確性和及時性，有效提高動態調度的效率。

2007年始，該港務公司采取基于本文動態調度模型的裝載優化方案，取得了良好的經濟效益，使單航次運價收入的增量達到了1.5~3萬元的效益空間。2007年11月8日，五班船總的出口量為543輛次，平均單運價達2 101.38元/車，車輛總收入達114.1萬元，創下當年內單船車輛平均單價和日運量及收入的最高記錄。

4 結束語

本文針對柔性生產中兩生產單元對多作業對象的情形，把生產單元模型化為容器，將其容積視為生產能力，并劃分為設定能力和機動能力，通過模擬連通器建立了連通機動能力的一種動態調度模型。根據流體力學原理，建立了基于能力平衡的動態調度規則，并開發了可應用于調度操作現場的高效率啟發式優化算法。該模型在滾裝運輸的船舶裝載過程中得以實際應用，為企業取得了良好的經濟效益，驗證了其可行性和有效性。同時，該模型及其算法的成功應用對其他優化模型的工業應用具有參考價值。

參考文獻:

[1]張留建. 新經濟時代的柔性生產方式研究[D]. 武漢:武漢理工大學， 2007.

[2]錢曉龍，唐立新， 劉文新. 動態調度的研究方法綜述[J].控制與決策， 2001，16(2):141-145.

[3]周炳海，蔣舒宇，何平，等. 基于雙重資源的柔性生產系統調度算法[J]. 華南理工大學學報:自然科學版， 2008，36(4):45-49.

[4]GAO Jie， GEN M， SUN Lin-yan， et al. A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems[J].Computers Industrial Engineering， 2007，53(1):149-162.

[5]李琳，江志斌. 虛擬生產系統的自適應動態調度機理及算法[J]. 計算機集成制造系統， 2006，12(9):1444-1452.

[6]RUIZ-TORRES A J， CENTENO G. Scheduling with flexible resources in parallel workcenters to minimize maximum completion time[J].Computers Operations Research， 2007，34(1):48-69.

[7]AL-FAWZAN M A. An algorithm for production planning in a flexible production system[J].Computers Industrial Engineering， 2005，48(4):681-691.

[8]KUMAR A， PRAKASH， TIWARI M K， et al. Solving machine-loa-ding problem of a flexible manufacturing system with constraint-based genetic algorithm[J]. European Journal of Operational Research， 2006，175(2):1043-1069.

[9]MARTINICH J S. Production and operations management: an applied modern approach[M]. New York : Wiley， 1996:751-785.