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

（東華大學(xué) 機(jī)械工程學(xué)院，上海 201620）

0 引言

多品種小批量柔性敏捷制造企業(yè)，任意時(shí)刻可能都有計(jì)劃外的任務(wù)到達(dá)。企業(yè)或車間調(diào)度任務(wù)池中的任務(wù)是連續(xù)的，往往會(huì)高于設(shè)備的生產(chǎn)能力。因此，生產(chǎn)任務(wù)的優(yōu)先權(quán)問題成為制定生產(chǎn)排成的關(guān)鍵。

不少的研究人員對(duì)此類問題作了相關(guān)研究[1～4]，大多數(shù)的調(diào)度任務(wù)優(yōu)選主要是以訂單為研究對(duì)象，依據(jù)訂單自身的優(yōu)先級(jí)排列加工任務(wù)，忽略了生產(chǎn)任務(wù)與車間實(shí)際生產(chǎn)能力的匹配問題。因此，研究基于生產(chǎn)資源的柔性作業(yè)調(diào)度任務(wù)優(yōu)選方法是十分重要的。另外，在有關(guān)柔性作業(yè)車間調(diào)度方法的大量研究中[5～7]，取得了令人滿意的結(jié)果。

本文從訂單的任務(wù)交貨期富裕度、重要度以及工序難易程度三個(gè)方面對(duì)其進(jìn)行優(yōu)先級(jí)排序，通過構(gòu)建車間生產(chǎn)設(shè)備的互換規(guī)則，綜合考慮訂單優(yōu)先級(jí)、工件柔性工序及生產(chǎn)資源的協(xié)調(diào)優(yōu)化，實(shí)現(xiàn)多目標(biāo)柔性作業(yè)調(diào)度任務(wù)的自動(dòng)優(yōu)選和生產(chǎn)能力平衡，為提高柔性作業(yè)調(diào)度方法的適用性、工作效率，調(diào)度結(jié)果的有效執(zhí)行，縮短生產(chǎn)周期和訂單交貨期，降低柔性敏捷制造成本等奠定良好的科學(xué)依據(jù)。

1 調(diào)度周期任務(wù)優(yōu)選問題的描述

調(diào)度周期任務(wù)優(yōu)選問題可以描述為：根據(jù)任務(wù)工件的優(yōu)先級(jí)評(píng)價(jià)指標(biāo)對(duì)各工件進(jìn)行優(yōu)先排序，按照先滿足優(yōu)先工件的原則，再兼顧充分利用車間設(shè)備資源的目標(biāo)，自動(dòng)選擇工件進(jìn)入調(diào)度任務(wù)池。

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

2 生產(chǎn)資源能力的定義及分析

2.1 機(jī)床集及其互換原則定義

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

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

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

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

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

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

2.2 機(jī)床能力定義及描述

傳統(tǒng)的生產(chǎn)調(diào)度方法中，將調(diào)度周期的每臺(tái)機(jī)床初始工作時(shí)間統(tǒng)一設(shè)為0或調(diào)度周期的開始時(shí)刻，而在實(shí)際生產(chǎn)中，根據(jù)設(shè)備的不同情況及其加工任務(wù)，不一定能統(tǒng)一啟動(dòng)。

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

3 任務(wù)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)及其優(yōu)選算法實(shí)現(xiàn)

3.1 任務(wù)優(yōu)先級(jí)評(píng)價(jià)指標(biāo)的定義

1）交貨期富裕度Tr%

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

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

其中，Ts表示任務(wù)工件調(diào)度的指定起始日期，Tfj表示工件j的交貨日期，Tbj表示工件j的批量處理工序時(shí)間總和，Tsj表示工件j的單件處理工序時(shí)間

總和，Uj表示工件j的數(shù)量。

2）重要度v

工件的重要度與很多因素有關(guān)，除了工件本身的屬性，如屬于某個(gè)關(guān)鍵件中的重要零件，還包括一些潛在的制約因素，如工件所屬訂單的客戶屬性，訂單的利潤(rùn)等。因此，對(duì)工件重要度的評(píng)價(jià)可以根據(jù)企業(yè)具體情況進(jìn)行規(guī)定，選取不同的衡量指標(biāo)，各指標(biāo)之間的相對(duì)權(quán)重，車間可根據(jù)實(shí)際的需求給出。

工件j的重要度用vj表示，vj的取值范圍為[0，1)，根據(jù)vj的范圍可以將工件的重要度分為很重要、重要、比較重要、一般、不重要等等級(jí)，比如(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。車間亦可根據(jù)實(shí)際需要更改工件重要度等級(jí)范圍的值。

3）加工的難易系數(shù)L

不同的任務(wù)具有不同的加工難易程度，如新老產(chǎn)品的差別或?qū)儆谠囍乒に囘€是成熟工藝等。加工難度大的工件則屬于難加工的工件，在加工過程中容易出現(xiàn)廢品，對(duì)這一類廢品率較高的工件，可通過增加其生產(chǎn)批次的方法來保證工件的合格數(shù)。工件的廢品率越高，應(yīng)投產(chǎn)的生產(chǎn)批次應(yīng)越大，工件的加工時(shí)間會(huì)增加，冗余期就會(huì)相應(yīng)減小。而在有限的生產(chǎn)時(shí)間內(nèi)，為了保證工件按期交貨，需要考慮更充分的調(diào)整時(shí)間。

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

3.2 任務(wù)優(yōu)先級(jí)評(píng)價(jià)的計(jì)算模型

根據(jù)以上的評(píng)價(jià)指標(biāo)，現(xiàn)建立任務(wù)優(yōu)先級(jí)評(píng)價(jià)的數(shù)學(xué)計(jì)算模型。根據(jù)工件j加工的難易系數(shù)Lj，?。?+Lj）影響因子對(duì)工件的交貨期富裕度Trj進(jìn)行修正，得到修正后的工件交貨期富裕度Trj'。Trj'的計(jì)算如式(6)所示。

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

其中，α表示修正后的工件交貨期富裕度指標(biāo)的權(quán)值，β表示工件的重要度權(quán)值，α+β=1。

3.3 任務(wù)優(yōu)選關(guān)鍵算法實(shí)現(xiàn)

調(diào)度任務(wù)優(yōu)選模塊主要分為任務(wù)的優(yōu)先級(jí)計(jì)算及排序、任務(wù)-設(shè)備的綜合遴選兩個(gè)部分。算法流程如圖1所示。本文算法采用C#語言編寫，調(diào)度算法[8]采用MATLAB編寫，后臺(tái)采用SQL Server2008數(shù)據(jù)庫。

圖1 任務(wù)優(yōu)選算法流程圖

算法關(guān)鍵步驟描述：

步驟1：讀取任務(wù)池工件信息及車間設(shè)備資源信息；

步驟2：計(jì)算每個(gè)任務(wù)工件的冗余期及優(yōu)先級(jí)序列，并將任務(wù)按照優(yōu)先級(jí)序列從小到大進(jìn)行排列；

步驟3：讀取車間動(dòng)態(tài)設(shè)備信息庫，統(tǒng)計(jì)各預(yù)定設(shè)備組在調(diào)度周期內(nèi)可用的加工能力；

步驟4：按照工件的優(yōu)先級(jí)順序選取工件，并更新調(diào)度周期預(yù)選任務(wù)庫，同時(shí)計(jì)算設(shè)備組剩余的加工能力，更新調(diào)度周期設(shè)備負(fù)荷庫；

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

步驟6：返回調(diào)度周期預(yù)選任務(wù)庫，刪除該任務(wù)的選擇，轉(zhuǎn)入步驟4；

步驟7：當(dāng)任務(wù)池信息庫中所有任務(wù)全部遍歷完畢，或所有的設(shè)備組均到達(dá)滿負(fù)荷時(shí)，算法終止，得到調(diào)度任務(wù)池工件，即優(yōu)先選出的調(diào)度任務(wù)工件，否則，返回步驟4；

步驟8：結(jié)束。

4 測(cè)試案例設(shè)計(jì)與結(jié)果分析

4.1 標(biāo)準(zhǔn)案例的組合及其目標(biāo)與約束設(shè)計(jì)

為了驗(yàn)證本文提出的任務(wù)優(yōu)選方法與算法的有效性，將標(biāo)準(zhǔn)庫中MK01（10×6）與FL5×6兩個(gè)柔性調(diào)度案例進(jìn)行組合，并對(duì)訂單交貨期和設(shè)備維修約束等進(jìn)行假設(shè)，并按機(jī)床互換性原則，定義工序設(shè)備的互換性。

1）工件代號(hào)的歸一化處理：令MK01中10個(gè)工件的代號(hào)為J1-J10，F(xiàn)L5×6中5個(gè)工件的代號(hào)為J11-J15。

2）任務(wù)交貨期目標(biāo)的假設(shè)：工件J11交貨期的單位時(shí)間為20，工件J14為30。

3）調(diào)度周期假設(shè)：該批任務(wù)可在2～3個(gè)調(diào)度周期內(nèi)完成，并令第1個(gè)調(diào)度周期為30。

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

5）調(diào)度目標(biāo)設(shè)計(jì)：任務(wù)總完工時(shí)間makespan最小，設(shè)備最大負(fù)荷Cm與設(shè)備平均負(fù)荷之差最?。ň饴首顑?yōu)）以及設(shè)備的利用率最大。

4.2 調(diào)度結(jié)果及分析

基于以上的約束假設(shè)和本文算法，對(duì)15個(gè)工件優(yōu)選調(diào)度的甘特圖如圖2所示，細(xì)實(shí)線框表示第一個(gè)調(diào)度周期內(nèi)的作業(yè)任務(wù)，粗實(shí)線框表示第二個(gè)調(diào)度周期內(nèi)的作業(yè)任務(wù)。

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

2）第二個(gè)調(diào)度周期，完成J2、J6等7個(gè)工件的加工，makespan為28。

3）15 個(gè)工件的總完工時(shí)間為58，少于目前已知的最優(yōu)解[9]40+27=67，可見即使增加了諸多目標(biāo)和約束，本文調(diào)度結(jié)果仍可使makespan降低13%。

4）設(shè)備最大負(fù)荷Cm為52（機(jī)床4），與各臺(tái)機(jī)床的平均負(fù)荷45僅相差7，設(shè)備的均衡性較優(yōu)，設(shè)備的利用率達(dá)到269/327=82.3%。

圖2 任務(wù)優(yōu)選后調(diào)度甘特圖

5 結(jié)束語

本文對(duì)基于生產(chǎn)資源的柔性作業(yè)調(diào)度任務(wù)優(yōu)選方法進(jìn)行了研究，對(duì)算法關(guān)鍵部分作了詳細(xì)設(shè)計(jì)?？紤]車間實(shí)際的生產(chǎn)狀況，建立了任務(wù)優(yōu)先級(jí)評(píng)價(jià)的計(jì)算模型，同時(shí)制定了車間設(shè)備可互換原則，考慮調(diào)度周期內(nèi)資源的生產(chǎn)能力，實(shí)現(xiàn)對(duì)車間調(diào)度任務(wù)自動(dòng)化優(yōu)選的目的。該方法已在某航天設(shè)備制造企業(yè)得到初步應(yīng)用，為解決實(shí)際的柔性作業(yè)車間調(diào)度問題提供了科學(xué)依據(jù)，具有良好的工程應(yīng)用前景。

[1]唐麗春,蔡曉毅.供應(yīng)鏈環(huán)境下訂單優(yōu)先權(quán)確定[J].系統(tǒng)工程理論與實(shí)踐,2009(9):41-46.

[2]雙兵,顧幸生.考慮訂單優(yōu)先級(jí)的連續(xù)過程生產(chǎn)調(diào)度[A].第五屆全球智能控制與自動(dòng)化大會(huì)會(huì)議論文集[C].(4).2004.

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

[4]李浩,沈祖志,鄧明榮.訂貨型企業(yè)基于約束理論的訂單排產(chǎn)優(yōu)化研究[J].中國機(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]陳成,邢立寧.求解柔性作業(yè)車間調(diào)度問題的遺傳—蟻群算法[J].計(jì)算機(jī)集成制造系統(tǒng),2011,17(3):615-621.

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

[9]高亮,張國輝,王曉娟.柔性作業(yè)車間調(diào)度智能算法及其應(yīng)用[M].武漢:華中科技大學(xué)出版社,2012.