摘要：為解決數控（kòng）加工中心任務與刀具的集（jí）成優化調度（dù）問題，以生產總成本最小為優化目標，建立了考慮任務交貨（huò）期和工步並行加工的數控加工中心任務與刀具集成調度模型，產生麵（miàn）向數控（kòng）加工（gōng）中心任務與刀（dāo）具的協同（tóng）優化（huà）調度結（jié）果。為實現（xiàn）對該調度模型的優化求解，提出了一種改（gǎi）進自適應遺傳算法，設計了（le）合理（lǐ）的編碼（mǎ）方式和自適應（yīng）進化操作，並（bìng）通過任務－刀具關聯矩陣保證搜索過程中解的可行性，從而（ér）顯著提高了（le）算法的收斂性（xìng）能和求解效（xiào）率。算例結果表明，該模型能夠最大限度地降低加工成本和拖期率，同時算法的收（shōu）斂速度和穩（wěn）定性也得到了明顯（xiǎn）提高，大大降低了問題求解的迭代次數。

      關鍵詞（cí）：數控加工中心；刀具調度（dù）；並行（háng）加工；自適應遺傳算法

　    隨著車間加工自動化程度的（de）日益提高，數控裝備逐漸取代（dài）傳統的加工機床，成為（wéi）企業加工的核心，顯著提高了企業的加工質（zhì）量與效率，而（ér）刀具作為數控加工中心的重要組成部分，受到了越來越多的關注［１］。與傳統的加工機床相比，數控裝備特別是高端數控加工中心（如（rú）車銑複合加工中心）更（gèng）能適應（yīng）多品種、小批量生產模式（shì）需求，具有多工序（xù）、多工步並行加工的特點，能滿足複雜多尺度產品的（de）加工需求（qiú）［２］。但（dàn）是，在數控加工中心（xīn）的加工過程中（zhōng），為保證其多任務的柔性、高效、高質量（liàng）、低（dī）成本加工需求，加工任務（工序、工步）的合理排序與刀具資源的合（hé）理選配已經成為迫切需要（yào）解決的關鍵（jiàn）問（wèn）題，二者相輔相成、缺一不可。特別是刀具資源在逐步成為（wéi）企業瓶頸資源的基礎上，刀具選配的合理與否將直（zhí）接關係到任務的加工效（xiào）率和生產成本。在此環境下，探（tàn）求一種合適的任務與（yǔ）刀具集成調度方案對提升（shēng）數控加工中心的加工質量與效率（lǜ）就顯得尤為重要［３－６］。

      在傳（chuán）統的數控加工中心加工中，任務與刀具規劃調度是割裂開來的［７－８］。加工任務的規劃與調度過程中（zhōng）未考慮刀具的製約因素，並假定刀具資源是充（chōng）足的，而刀具的選（xuǎn）配則是依據規劃好（hǎo）的加工任務（加工順（shùn）序）來直接分配，二（èr）者是一種串行的因果關係。顯然，該方法並未充分考慮任務與刀具之間的製約關係，從加工成（chéng）本、加工效率等角度考慮，得出的方案往往是可行方（fāng）案，而非最佳（jiā）方案，甚至導致不可行方案的產生。為（wéi）此，本文針對單（dān）台數控加工中心，從任務與刀具調度協同優化的角度出（chū）發，提出一種數控加工中心任務與刀具（jù）集成調度方法與模型，並（bìng）采用自適（shì）應遺傳算法實（shí）現對模型的（de）優化求解，得出任務與刀具優化分配、調度（dù）結果，達到提升數控加工中心的加工效率、刀具資源利用率及降低加工成本的目（mù）標。

      １　、數（shù）控加工中心（xīn）任務與刀具集成調度模型

      １．１　變量符號定義

      在建（jiàn）立（lì）數控加工中心任務與刀具（jù）集成調度數學模（mó）型（xíng）之前，首先定義如下變量符（fú）號。

      １．２　任務與刀具集成調度數學模型

      一台數控加工中心分配（pèi）了ｎ 個工件｛Ｊ１，Ｊ２，…，Ｊｎ｝各工序（xù）（含１道或多道工步）加工任務，各工序包（bāo）含的工步加工順序由工藝要求預先確定，某些工步根據實際需要可（kě）並行加工。每道工步（bù）的可選（xuǎn）加工刀具由工藝規程確定（dìng）（對於特（tè）定加工特征，一般存在同類型的多（duō）把刀具可以滿足要求），至少有一把待選刀具可對其進行加工，其加工時間隨所選刀具的不同而不同，加工整批任務共有ｍ 把待選刀（dāo）具｛Ｍ１，Ｍ２，…，Ｍｍ｝可供選擇，ｎ個待加工工件有各自的交貨期要求｛Ｄ１，Ｄ２，…，Ｄｎ｝。調度的目標是確定所有工件的加工（gōng）順（shùn）序並為每道工步選擇合適（shì）的刀具，以使整批任務的加（jiā）工費用指標達到最優。圖１和表１描述了數控加工（gōng）中心（xīn）２工件、５刀具的集成調度問（wèn）題。

  
      加工過程中需要滿足以（yǐ）下約束條件。

     （１）不同工件（jiàn）的（de）工步之（zhī）間沒有（yǒu）先（xiān）後約（yuē）束，同一工件的工步之間（jiān）有先後關係，且（qiě）提前已知，不可改動。
     （２）同（tóng）一工件的不同工步之間存在並行加工關係，並行加工情況（kuàng）提前已知。
     （３）每個工件（jiàn）一旦（dàn）開始加工不能中斷。
     （４）同一把刀具在某一時刻隻能（néng）加工（gōng）一個零件。
     （５）工件具有各自的（de）理想交貨期和極限交貨期（qī）。
     （６）所（suǒ）有工件在零時刻都可以被加工。

      基於（yú）以上（shàng）假設，本文以最小化加工費用為優化目（mù）標，除刀（dāo）具使用（yòng）費用外，由於考慮交貨期（qī）要求，可能會（huì）存在工件不能準時完（wán）工的情況，所以（yǐ）如何減小拖期工件數量，降低拖期懲（chéng）罰費用也是本問（wèn）題的關（guān）鍵。綜上，總費用應包括（kuò）刀具使用費用和拖期懲罰費用，由問（wèn）題定（dìng）義易知刀具使用費用為

      式中：Ｄｉ，ｍａｘ為任務的（de）極限（xiàn）交貨期，與（yǔ）理想交貨期Ｄｉ的差（chà）值說明了工件的重要性。越重要的工件其交貨期控製越嚴格，所允許的變動（dòng）量就越（yuè）小，反之越大。據此（cǐ）得到加（jiā）工（gōng）費用指標的目（mù）標函數（shù）為（wéi）

      式（５）說明，由於考慮了並行加（jiā）工，可以有多把刀具同時進行加工；式（６）保證（zhèng）每把刀具同時隻能（néng）加工一道任務；式（７）保證（zhèng）調度為所有任務的全排列；式（８）表（biǎo）示用於零件加（jiā）工的（de）所（suǒ）有（yǒu）刀（dāo）具數量Ｎｕｍ｛·｝不大於所（suǒ）提供的備選刀具數量；式（９）表示完工時間等於（yú）開始時間與加工（gōng）時間之和；式（１０）、式（１１）保證後一道（dào）加工（gōng）任（rèn）務必須在前一（yī）道加工任務完成後開始；式（１２）則保證並（bìng）行（háng）加工的工步同時開始。

      ２　、自適應遺傳算法的設計

      由於傳統遺傳算法在求（qiú）解類似問題過程（chéng）中，存在著收斂速度慢，常陷於局部最優值的缺（quē）點（diǎn）。本文為實現對刀具與任務集成調度問題的綜合求解，采用自適（shì）應遺傳算法，通過在搜（sōu）索過（guò）程中，交叉、變異概率的自動變化來提高算法的收斂速度，跳出局部最優解。算法流程（chéng）如圖２所示。

      ２．１　染色體編（biān）碼與解（jiě）碼

      數（shù）控加工中心的刀（dāo）具與任務集成調度問題需要為每（měi）個工件（jiàn）的每道工步選擇（zé）一把刀具，並對所有待加工任（rèn）務進行排序，因此編（biān）碼需同時考慮這兩方麵的（de）問題。總體上采用如下實數矩陣編碼結（jié）構

      ｛·｝表示取小數（shù）。約定按（àn）Ｐｉ值由小到大確定各工（gōng）件的加工順序。融合這兩部分編碼，便可形成一個表示刀具與任務集成（chéng）調度方案的矩陣編碼。

      為（wéi）保證整個矩陣的維數相同，約定凡小於（yú）最大工步數的工件整數部（bù）分編碼用０表示。例如圖１的工件２、刀具５調度問題，其（qí）矩陣編碼為

      通過對矩陣元素的拆分後，即可確定調度方案，即先加工工（gōng）件２，再加工（gōng）工件１；工件２的２道工步分別（bié）采用刀具２和刀具１進行加工；工件１的３道工步分別采（cǎi）用刀具２、３、５進行加工。

      ２．２　適應度函數

      適應度值是評價解的優良（liáng）性能（néng）的重要指標，本文是求解目標（biāo）函數最小化問（wèn）題，故采用如下反比例函（hán）數（shù）作為適應度函數

      ２．３　初始解的生成

      初始解的質量對於遺傳算法的求解（jiě）效果有較大影響，采用（yòng）隨機初始化會產生較多的不可行解（jiě），需要（yào）算法在優化過程（chéng）中（zhōng）不斷剔除，這就（jiù）增加了搜索過程的迭代次數和收（shōu）斂時間（jiān）。本文通過引入工步－刀（dāo）具關聯矩陣來保證進化過程（chéng）中刀（dāo）具分配方案的可行性（xìng）。若用ｙｉｊｔ表示矩陣元素（sù）（ｉ為工件號，ｊ 為工步號，ｔ為刀具號），其取值規則為

      在解（jiě）編碼的初始化與交叉（chā）、變異（yì）過程中，始終對照該矩陣，選擇ｙｉｊｔ＝１的刀具號生成編碼，從而產生（shēng）可行調度（dù）方案，提高（gāo）算法搜（sōu）索過（guò）程的穩定性。

      ２．４　算法的進化操作

      交叉操作主要為保（bǎo）留父（fù）代個（gè）體的（de）優秀基因。為保證交叉之後染色體（tǐ）的合法性，本文采用染（rǎn）色體同位置基因（yīn）互（hù）換的方法，基於該原則，交叉操作可以多樣化設（shè）計（jì）。本（běn）文針對矩陣編碼分別采用基於行和列的單點、兩（liǎng）點和多點交叉，如圖３、圖（tú）４所示（shì）。

      類似交叉操作，變異也采用基於（yú）行和列（liè）的單點、兩點和多點變異。在變異過程中，要保證［ａｉｊ］∈Ｘｉｊ，從而保證染色體的合法性。

      對（duì）於交叉、變異過程，優良個體以較高的（de）概率交叉更符合自然法則；低劣個體以較大概率變異，這更有利於保（bǎo）護並產生新的優良解。這一原（yuán）則應該體現在整個進化操（cāo）作過程中。文獻［９］對自適應遺傳算法的Ｐｃ、Ｐｍ做以下調整

      上述調整一定程度上改進了遺傳（chuán）性能，但不足之處在於，用線性函數表示交叉、變異概（gài）率的變（biàn）化過程（chéng），無法描述整個進（jìn）化過程中參數的變化幅度。為了更清晰地說（shuō）明在進化不同階段參數變（biàn）化的幅度區別（bié），進一步提高算法的自適（shì）應性（xìng），本文引入三角函數來表示（shì）這一變化過程，重新給出交叉、變異概率的計算公式如下

      ３　、實例驗證與結果分析（xī）

      為了驗證模型的正確性，並比較本文自適應遺（yí）傳算法在解（jiě）決（jué）該問題中的優越性，特設計加工實例進行分析。在模型（xíng）方麵，設計（jì）按交貨期順序加工模型與本模型進行（háng）對比；在算法上（shàng），設計傳統遺傳（chuán）算法與本算法進行（háng）比較。

      ３．１　加工實例介紹（shào）

      本文以西安（ān）西電開關有限公司機加（jiā）車間為應用（yòng）示範基地，以型號ＮＨ６３００－ＤＣＧ的數控（kòng）加工（gōng）中心的一批實例加工任務為例，計算其調度過程（chéng）。實例（lì）中，該加工中心分配了１０個工件某一（yī）道工序的加工（gōng）任（rèn）務（wù），每道工序（xù）包含了多道工步。現提供（gòng）１２把待（dài）選刀具對（duì）整批任務進行加工，與任務相關的刀具需求信息、加工時間、刀具使用成本、並行加工信息及各加工任務（wù）交貨期等信息如表３、表４所示。

      改進自適應遺傳算法采（cǎi）用ＭＡＴＬＡＢ編程實現，最小、最大交叉概率Ｐｃ１＝０．６、Ｐｃ２＝０．９，最小、最大（dà）遺傳概率Ｐｍ１＝０．２、Ｐｍ２＝０．５，種群規模設置為１００，迭代次數為３００次。

      ３．２　結果（guǒ）對比與（yǔ）分析

      調度結果如圖６所示，圖中方（fāng）框代表對應Ｚ 步加（jiā）工過程，垂（chuí）直線Ｄｉ代表工件ｉ的交（jiāo）貨期。由圖６ａ可知（zhī），在按交貨期排序的加工（gōng）方案中，從第３個工件開始拖（tuō）期完工，拖期率達７０％，拖期懲罰Ｗｆ＝２７６元。在圖６ｂ工序優化後的方案中，隻有（yǒu）工件（jiàn）１、２沒有按交貨期要求進行加工，拖期率降到２０％，相應的拖期懲罰Ｗｆ＝９４．５元。

      表５對兩種方案的調度結果進行了對比，可以看出，采用（yòng）遺傳算法在對刀具進行選配的同時，對加工序列進（jìn）行不斷調整，可以最（zuì）大限度地減少拖期工件數量，降低拖期懲罰（fá），證明了本模型的可行性。由以上結果可以看出，常（cháng）規按照交貨期順序進行加工的調度方案會造成延誤時間（jiān）的疊加，從而影響（xiǎng）任務整體的（de）正常生產。采用本模型，通過損失部分不緊急子任務的準時生（shēng）產，可以（yǐ）最大限度地換（huàn）取任務整體加工的準時性。同時，本（běn）文的調度方案可以用於指導（dǎo）交貨期的製定，如對工件（jiàn）１和工件２的交貨期作適當調整，則整批任務的生產計劃和調度方案則會更加合理。

      ４、　結束語
 

       對於數控加（jiā）工中心的一批加工任（rèn）務來（lái）講，刀具選配與任務規劃（huá）是影響加工總成本的兩個關鍵環節，隻有將兩者結合在一（yī）起共同優化，才有可（kě）能得到該（gāi）批任務加工（gōng）總成本的全局最優解。為此，本文提出了數（shù）控加工中心任務與刀具（jù）的集成（chéng）調度方法與模型，並利用改進後的自適應遺傳算法對該問題進行求解，最後設計加工實例對問題模型和算法進行分析。結果證明，結合本模型（xíng）和改進（jìn）後的自適應遺傳（chuán）算法，可在實際生產中得到更為滿意的結果。