基于生產資源的柔性作業調度任務優選方法

施 爍，李蓓智，鄒 攀，楊建國

（東華大學 機械工程學院，上海 201620）

0 引言

多品種小批量柔性敏捷制造企業，任意時刻可能都有計劃外的任務到達。企業或車間調度任務池中的任務是連續的，往往會高于設備的生產能力。因此，生產任務的優先權問題成為制定生產排成的關鍵。

不少的研究人員對此類問題作了相關研究[1～4]，大多數的調度任務優選主要是以訂單為研究對象，依據訂單自身的優先級排列加工任務，忽略了生產任務與車間實際生產能力的匹配問題。因此，研究基于生產資源的柔性作業調度任務優選方法是十分重要的。另外，在有關柔性作業車間調度方法的大量研究中[5～7]，取得了令人滿意的結果。

本文從訂單的任務交貨期富裕度、重要度以及工序難易程度三個方面對其進行優先級排序，通過構建車間生產設備的互換規則，綜合考慮訂單優先級、工件柔性工序及生產資源的協調優化，實現多目標柔性作業調度任務的自動優選和生產能力平衡，為提高柔性作業調度方法的適用性、工作效率，調度結果的有效執行，縮短生產周期和訂單交貨期，降低柔性敏捷制造成本等奠定良好的科學依據。

1 調度周期任務優選問題的描述

調度周期任務優選問題可以描述為：根據任務工件的優先級評價指標對各工件進行優先排序，按照先滿足優先工件的原則，再兼顧充分利用車間設備資源的目標，自動選擇工件進入調度任務池。

根據該問題建立了訂單任務—車間資源—加工效益的數學模型為：工件任務池Pt中有n個工件{J1,J2,…,Jn}，需要在m臺設備{M1, M2,…, Mm}上加工。每個工件由一系列工序Ojx(x=1,2,…,TOj)組成，Bj和Sj分別表示工件j的批量處理的工序（如熱處理等）集合和單件處理的工序（如車、銑等）集合，Ojx和TOj分別表示工件j的第x道工序和工件j的總工序數，Bj+Sj∈Ojx；工序Ojx在可用設備集Mθjx內的任一設備Mijx上加工，Mijx∈Mθjx，Mθjx∈{M1, M2,…, Mm}，準備時間為t0ijx，加工時間為tijx；工件Jj的優先等級序列為Tpj，調度周期T內設備Mi的生產能力為TFMCi，設備集Mθ的生產能力為ΣTFMCi。求解的目標則是根據任務優先等級序列Tpj及設備生產能力自動選擇任務進入調度任務池Ps，同時使得總任務最大完工時間最小，設備最大負荷Cm與設備平均負荷之差最小（均衡率最優）以及設備的利用率最大。

2 生產資源能力的定義及分析

2.1 機床集及其互換原則定義

根據機械加工的工藝類型及特點，結合車間資源信息，將車間機床劃分為不同的大機床集系列，分別是車系列、銑系列、鏜系列等；每一個大機床集系列又可劃分為不同的加工類型集，將其定義為小機床集系列，如車系列又可分為普通車、數控立車、數控臥車及數車加工中心等。

小機床集內的機床（工藝類型相同）在滿足加工尺寸范圍及加工精度的要求下，可以進行互換；大機床集內、機床集間的互換，則還需考慮加工工藝類型的匹配等。根據實際需求，定義如下的機床互換原則：

1）小機床集內的互換性（加工規模原則）：小規格機床可以被大規格的機床代替，反之若加工零件超過機床加工范圍則不可替換；

2）大機床集內（間）的互換性（加工類型原則）：可互換的機床必須具有相同的加工特征，如三軸加工中心可以替換數控立銑等；

3）機床間的互換性，應滿足一些簡單的互換原則條件，如加工規模原則應在加工精度匹配的情況下使用，滿足加工類型原則的機床還應該滿足加工規模原則等；

4）如果互換的代價較大時，不考慮互換。不考慮機床加工精度上有較大差別的互換，如高精密數控臥車替換普通車等；不考慮機床規格有較大差別的互換，如龍門刨床替換普通刨床等。

2.2 機床能力定義及描述

傳統的生產調度方法中，將調度周期的每臺機床初始工作時間統一設為0或調度周期的開始時刻，而在實際生產中，根據設備的不同情況及其加工任務，不一定能統一啟動。

假定調度的起始日期為Ts，調度周期為t（單位：天），機床Mi每天的生產班次為mi，每班次工作的小時數為twi，數量為Qi，其已有工作負荷為Tri(單位：小時)工作量，并考慮機床最大能力的η(%)作為其實際的加工能力。定義機床Mi的生產能力為TFMCi，如式(1)所示，則機床集Mθ的生產能力TFMC即為該組所包含設備生產能力之和，如式(2)所示。

3 任務優先級評價指標及其優選算法實現

3.1 任務優先級評價指標的定義

1）交貨期富裕度Tr%

訂單能否按期交貨，取決于訂單的交貨期和訂單任務的生產周期。將工件的交貨日期（Tf）與開始加工日期（Ts）之差（Tf-Ts）作為工件交貨緊急度的描述顯然是不夠全面的，忽略了生產周期的影響。將Tr定義為訂單工件的交貨期富裕度（交貨時間的冗余期），即為工件可剩余的加工時間占其總時間的百分比。

通過計算工件的冗余期，選擇該指標衡量任務工件的優先級，是較為合理的方法。計算工件任務池Pt中工件j的冗余期Trj，冗余期的計算如式(3)～式(5)所示。

其中，Ts表示任務工件調度的指定起始日期，Tfj表示工件j的交貨日期，Tbj表示工件j的批量處理工序時間總和，Tsj表示工件j的單件處理工序時間

總和，Uj表示工件j的數量。

2）重要度v

工件的重要度與很多因素有關，除了工件本身的屬性，如屬于某個關鍵件中的重要零件，還包括一些潛在的制約因素，如工件所屬訂單的客戶屬性，訂單的利潤等。因此，對工件重要度的評價可以根據企業具體情況進行規定，選取不同的衡量指標，各指標之間的相對權重，車間可根據實際的需求給出。

工件j的重要度用vj表示，vj的取值范圍為[0，1)，根據vj的范圍可以將工件的重要度分為很重要、重要、比較重要、一般、不重要等等級，比如(1)很重要，0.9≤vj；(2)重要，0.7≤vj<0.9；(3)比較重要，0.5≤vj<0.7；(4)一般，0.3 ≤vj<0.5；(5)不重要，vj<0.3。車間亦可根據實際需要更改工件重要度等級范圍的值。

3）加工的難易系數L

不同的任務具有不同的加工難易程度，如新老產品的差別或屬于試制工藝還是成熟工藝等。加工難度大的工件則屬于難加工的工件，在加工過程中容易出現廢品，對這一類廢品率較高的工件，可通過增加其生產批次的方法來保證工件的合格數。工件的廢品率越高，應投產的生產批次應越大，工件的加工時間會增加，冗余期就會相應減小。而在有限的生產時間內，為了保證工件按期交貨，需要考慮更充分的調整時間。

本文根據工件j加工的難易系數Lj，通過取（1+Lj）影響因子來增大工件的投產量，從而減小工件冗余期。工件加工的難易系數Lj的取值范圍為[0，1]，難度由0到1逐漸增大。Lj的取值主要參考車間該類工件的歷史數據庫并根據實際情況由車間有經驗的人員指定。

3.2 任務優先級評價的計算模型

根據以上的評價指標，現建立任務優先級評價的數學計算模型。根據工件j加工的難易系數Lj，取（1+Lj）影響因子對工件的交貨期富裕度Trj進行修正，得到修正后的工件交貨期富裕度Trj'。Trj'的計算如式(6)所示。

由修正后的工件交貨期富裕度Trj'及工件的重要度vj兩個指標共同確定任務工件的優先等級，得到工件的優先級序列Tpj，其計算模型如式(7)所示。Tpj越小，表示工件j的優先級越高。

其中，α表示修正后的工件交貨期富裕度指標的權值，β表示工件的重要度權值，α+β=1。

3.3 任務優選關鍵算法實現

調度任務優選模塊主要分為任務的優先級計算及排序、任務-設備的綜合遴選兩個部分。算法流程如圖1所示。本文算法采用C#語言編寫，調度算法[8]采用MATLAB編寫，后臺采用SQL Server2008數據庫。

圖1 任務優選算法流程圖

算法關鍵步驟描述：

步驟1：讀取任務池工件信息及車間設備資源信息；

步驟2：計算每個任務工件的冗余期及優先級序列，并將任務按照優先級序列從小到大進行排列；

步驟3：讀取車間動態設備信息庫，統計各預定設備組在調度周期內可用的加工能力；

步驟4：按照工件的優先級順序選取工件，并更新調度周期預選任務庫，同時計算設備組剩余的加工能力，更新調度周期設備負荷庫；

步驟5：如果出現某一設備組滿負荷(TFMC≤0)，判斷是否有可替換設備組可以提供加工能力，如果有，繼續選擇該工件，轉入步驟3，否則轉入步驟6；

步驟6：返回調度周期預選任務庫，刪除該任務的選擇，轉入步驟4；

步驟7：當任務池信息庫中所有任務全部遍歷完畢，或所有的設備組均到達滿負荷時，算法終止，得到調度任務池工件，即優先選出的調度任務工件，否則，返回步驟4；

步驟8：結束。

4 測試案例設計與結果分析

4.1 標準案例的組合及其目標與約束設計

為了驗證本文提出的任務優選方法與算法的有效性，將標準庫中MK01（10×6）與FL5×6兩個柔性調度案例進行組合，并對訂單交貨期和設備維修約束等進行假設，并按機床互換性原則，定義工序設備的互換性。

1）工件代號的歸一化處理：令MK01中10個工件的代號為J1-J10，FL5×6中5個工件的代號為J11-J15。

2）任務交貨期目標的假設：工件J11交貨期的單位時間為20，工件J14為30。

3）調度周期假設：該批任務可在2～3個調度周期內完成，并令第1個調度周期為30。

4）資源信息約束假設：某機床在某個時間段內因故維修，并令為機床5在第1個調度周期0～3時間段內需要維修；其余機床從零時刻起可用。下一個調度周期的資源信息則根據上一周期各機床的剩余加工能力而定。

5）調度目標設計：任務總完工時間makespan最小，設備最大負荷Cm與設備平均負荷之差最小（均衡率最優）以及設備的利用率最大。

4.2 調度結果及分析

基于以上的約束假設和本文算法，對15個工件優選調度的甘特圖如圖2所示，細實線框表示第一個調度周期內的作業任務，粗實線框表示第二個調度周期內的作業任務。

1）第一個調度周期，完成J1、J3等8個工件全部加工，makespan為30，其中具有交貨期目標約束的J11的最終完工時間為15，J14的最終完工時間為29，均滿足交貨期要求。M5在0～3時間段無加工任務，符合機床維修不可使用的約束。

2）第二個調度周期，完成J2、J6等7個工件的加工，makespan為28。

3）15 個工件的總完工時間為58，少于目前已知的最優解[9]40+27=67，可見即使增加了諸多目標和約束，本文調度結果仍可使makespan降低13%。

4）設備最大負荷Cm為52（機床4），與各臺機床的平均負荷45僅相差7，設備的均衡性較優，設備的利用率達到269/327=82.3%。

圖2 任務優選后調度甘特圖

5 結束語

本文對基于生產資源的柔性作業調度任務優選方法進行了研究，對算法關鍵部分作了詳細設計。考慮車間實際的生產狀況，建立了任務優先級評價的計算模型，同時制定了車間設備可互換原則，考慮調度周期內資源的生產能力，實現對車間調度任務自動化優選的目的。該方法已在某航天設備制造企業得到初步應用，為解決實際的柔性作業車間調度問題提供了科學依據，具有良好的工程應用前景。

[1]唐麗春,蔡曉毅.供應鏈環境下訂單優先權確定[J].系統工程理論與實踐,2009(9):41-46.

[2]雙兵,顧幸生.考慮訂單優先級的連續過程生產調度[A].第五屆全球智能控制與自動化大會會議論文集[C].(4).2004.

[3]張紅,郭飛鵬.面向敏捷詢單處理的訂單優先級排序方法[J].計算機工程與設計,2012,33(3):963-967.

[4]李浩,沈祖志,鄧明榮.訂貨型企業基于約束理論的訂單排產優化研究[J].中國機械工程,2004,15(10):865-869.

[5]Collotta M,Gentile L,Pau G, et al.Flexible IEEE 802.15.4 deadline-aware scheduling for DPCSs using priority-based CSMA-CA[J].Computers in Industry,2014, 65(8): 1181-1192.

[6]Wang W, Wang X,Ge X,et al.Multi-objective optimization model for multi-project scheduling on critical chain[J].Advances in Engineering Software,2014,68:33-39.

[7]陳成,邢立寧.求解柔性作業車間調度問題的遺傳—蟻群算法[J].計算機集成制造系統,2011,17(3):615-621.

[8]史峰,王輝,等.MATLAB智能算法30個案例分析[M].北京:北京航空航天大學出版社,2011.

[9]高亮,張國輝,王曉娟.柔性作業車間調度智能算法及其應用[M].武漢:華中科技大學出版社,2012.