李崢峰，于小忠，張國輝，崔陸軍

(1.中原工學(xué)院 機電學(xué)院，河南 鄭州450007；2.鄭州航空工業(yè)管理學(xué)院 管理工程學(xué)院，河南 鄭州450015)

柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem，F(xiàn)JSP)中有多個設(shè)備可以完成工件加工任務(wù)，即某工件的某道工序可以由多臺設(shè)備完成加工任務(wù)，其加工時間因加工設(shè)備的差異而有所差別。在柔性作業(yè)車間中，工件工藝的加工設(shè)備具有更多選擇性，其加工具有更高的柔性，但也增加了求解規(guī)模和復(fù)雜程度。在實際應(yīng)用中，柔性作業(yè)車間具有更普遍的意義，其調(diào)度問題的研究對指導(dǎo)實踐生產(chǎn)具有重要的意義。

FJSP描述如下。在i臺設(shè)備{M1,M2, ···,Mi}上加工j個工件的多道工序，每個工件至少有1道加工工序 ，其工序的加工順序是確定的。每道工序有多臺可選加工設(shè)備可以完成該工序的加工工藝，同一道工序的加工時間由于所選機器的差異而有所不同。目前，僅考慮加工時間因素的柔性作業(yè)車間調(diào)度問題研究相對比較成熟，并獲得了大量的研究成果。由于考慮輔助時間更加貼近車間調(diào)度的實際應(yīng)用，近年來考慮輔助時間的研究逐漸引起了大家的重視。制造企業(yè)調(diào)查統(tǒng)計表明[1]：在制造過程中，非加工時間占整個生產(chǎn)時間的90%以上。這說明輔助時間對生產(chǎn)效率有極其重要的作用，有必要對輔助時間進行深入的研究。

在柔性作業(yè)車間調(diào)度中，目前已經(jīng)有部分學(xué)者對輔助時間的作用加以重視，開始考慮某種輔助時間因素的一種或幾種，如調(diào)整時間、運輸時間和故障時間等對車間調(diào)度的影響[2-9]。文獻[2]對考慮故障時間的柔性作業(yè)車間魯棒調(diào)度進行了研究。文獻[3]對維修任務(wù)調(diào)度進行了研究。文獻[4]研究了預(yù)防性設(shè)備維護的柔性作業(yè)車間調(diào)度問題。文獻[5]對考慮調(diào)整時間的作業(yè)車間調(diào)度問題的國內(nèi)外研究進行了綜述，對批量調(diào)整時間、非批量調(diào)整時間、順序相關(guān)調(diào)整時間、順序無關(guān)調(diào)整時間的作業(yè)車間調(diào)度問題研究進行了分析。文獻[6]從順序相關(guān)調(diào)整時間(調(diào)整成本)、順序無關(guān)調(diào)整時間(調(diào)整成本)、組調(diào)整時間等方面對考慮調(diào)整時間調(diào)度問題的單機、并行機、流水車間、裝配流水車間、作業(yè)車間、柔性作業(yè)車間和開放車間等進行了分析綜述。文獻[7]對近20多年的柔性作業(yè)車間調(diào)度技術(shù)進行了綜述，從調(diào)度目標和求解方法層面進行了分析，相對于理論研究，其實際應(yīng)用研究相對缺乏。文獻[8]研究了考慮運輸時間的柔性作業(yè)車間調(diào)度問題，建立了關(guān)鍵鏈優(yōu)化方法。文獻[9]研究了帶準備時間的作業(yè)車間分批排序問題。

雖然上述研究取得了一定的成果，但大多考慮某一種或幾種輔助時間因素，沒有從車間生產(chǎn)系統(tǒng)層面分析輔助時間，甚至某些時間劃分存在某種重疊、模糊、不一致，比如等待時間包括故障時間、機器占用等待時間、工件運輸?shù)却龝r間等。本文從車間調(diào)度的角度出發(fā)，分析生產(chǎn)中的多種非加工時間因素，從工件生產(chǎn)過程實踐出發(fā)，建立車間生產(chǎn)過程的時間模型，在此基礎(chǔ)上建立考慮多種輔助時間的FJSP調(diào)度模型，并設(shè)計混合遺傳算法求解。

1柔性作業(yè)車間生產(chǎn)過程時間模型

基于不同的出發(fā)點，對生產(chǎn)中各個時間的定義會有重疊，這影響了調(diào)度的理論研究及其應(yīng)用。有的時間定義的對象不同，比如以工件為對象的加工時間，以機器設(shè)備為對象的故障時間；有的時間出發(fā)點不同，比如等待時間包括故障時間、機器占用等待時間、工件運輸?shù)却龝r間等。只有進一步細化區(qū)分這些輔助時間，才能使調(diào)度理論研究更好應(yīng)用于車間生產(chǎn)實踐。

一般意義上，等待時間為工件前后工序加工間的停頓時間。從調(diào)度理論研究的角度出發(fā)，把等待時間分解為工件運輸時間、機器調(diào)整時間、機器故障時間和機器占用時間等4個部分。其中，其他工件的加工時間包含機器占用時間，而工件運輸時間、機器調(diào)整時間、機器故障時間需要進行單獨考慮。為更加符合柔性作業(yè)車間生產(chǎn)情況并符合調(diào)度研究的需要，生產(chǎn)過程時間參數(shù)定義明確沒有重疊，如圖1所示。具體劃分如下。

加工時間指生產(chǎn)設(shè)備完成工件某道工序加工所需的時間。根據(jù)工藝和加工設(shè)備的不同，不同工序加工時間不同。

準備時間：在通常情況下，假設(shè)工件準備就緒隨時可以加工，即準備時間為0。

等待時間通常為工件前后工序加工停頓的時間。本文定義機器被其他工件加工占用而導(dǎo)致本工件加工停頓的時間為等待時間，并從中分離出運輸時間、故障時間、調(diào)整時間進行單獨研究。該等待時間不影響完工時間的優(yōu)化。

故障時間為由于機器設(shè)備故障導(dǎo)致工件不能正常加工的時間。一般從機器不滿足工件加工質(zhì)量要求開始計時，經(jīng)維修、修復(fù)、重新啟動直到正常待機開始正常加工為止。

圖1生產(chǎn)過程時間模型Figure 1 The model of production process time

調(diào)整時間是指由于加工設(shè)備上加工的工件工序的變換，需要進行模具、家具、裝卸、啟動等操作而產(chǎn)生的時間，可以分為順序相關(guān)和順序無關(guān)調(diào)整時間2類。

運輸時間是指移動搬運工件所產(chǎn)生的時間。

2基于生產(chǎn)過程時間的FJSP建模

經(jīng)過上述生產(chǎn)過程時間模型的分析，單獨分離調(diào)整時間、故障時間以及運輸時間，來研究柔性作業(yè)車間的優(yōu)化調(diào)度問題。

考慮調(diào)整時間的工序順序性質(zhì)，建立一個三維調(diào)整時間表，其中第1維表示當前要加工的工序，第2維表示上道加工工序，第3維表示所有機器設(shè)備。根據(jù)第3維的設(shè)備確定加工設(shè)備，然后在第1維和第2維組成的平面上可以找到任意2個該設(shè)備上加工的工序及上道加工工序，從而可以確定其調(diào)整順序相關(guān)時間。針對順序無關(guān)調(diào)整時間，可以選擇相同的工序即對角線上的時間表示。

在實際生產(chǎn)活動中，對某類型工件而言，其體積、重量、運輸方式比較固定，可以假定與此相關(guān)的初始時間為常數(shù)Tc。此時，運輸時間為

其中，j為工件號，h為工序號，f(d)為運輸距離的正比例函數(shù)，參考調(diào)整時間和加工時間大小，可以直接用設(shè)備的間隔數(shù)表示距離。

設(shè)備的故障時間是不確定和隨機的，根據(jù)車間生產(chǎn)的實際經(jīng)驗并參考工序加工時間的大小，設(shè)備以一定概率發(fā)生故障。

考慮加工時間、調(diào)整時間、故障時間、運輸時間以及綜合調(diào)整時間和運輸時間、故障時間，以工件最大完工時間最小化為目標的柔性作業(yè)車間調(diào)度模型如下。

其中，工件每道工序的開始時間和完工時間分別為

其中，Tsjh為工件j工序h的加工開始時間；Tcjh為工件j工序h的完工時間；Tzi為設(shè)備i的空閑時間，即上個工件工序的完工時間；TSi為工件j工序h在設(shè)備i上的調(diào)整時間；Tbi為設(shè)備i的故障時間，Tpi jh為工件j在設(shè)備i上進行工序h加工的時間。

優(yōu)化過程中，還需要滿足以下約束條件：1臺機器某時刻只能加工1個工件；1個工件某時刻只能在1臺設(shè)備上加工；工件工序加工過程中不中斷且無故障；工件工序按工藝先后順序加工；工件的首道工序到設(shè)備的運輸時間相同；設(shè)備故障后進行調(diào)整，不考慮調(diào)整后設(shè)備故障；首工序考慮調(diào)整時間。

3求解FJSP的混合遺傳算法設(shè)計

選擇工件的加工機器和機器上工件的先后加工順序，是解決FJSP調(diào)度問題的2個問題。前者是機器選擇問題，解決機器上加工哪些工件工序的問題；后者是工序排序問題，解決工序在所選機器上加工的次序和開工時間問題。在FJSP問題的遺傳算法研究的基礎(chǔ)上[10-13]，設(shè)計了如圖2所示的混合遺傳求解算法。

圖2混合遺傳算法流程圖Figure 2 Flow chart of hybrid genetic algorithm

3.1編碼

編碼采用分段整數(shù)編碼方式，包含如下2個部分。

1)工序排序部分。工序基因數(shù)目等于所有工件工序的總和。每一位基因用工件號碼表示，即某工件有幾道工序，該工件號就在染色體中出現(xiàn)幾次，出現(xiàn)的序次就是其工序數(shù)。

2)機器選擇部分。機器基因數(shù)目與工序部分基因數(shù)目相等，其基因位是相應(yīng)工序的可加工機器號。

3.2解碼

工序排序染色體部分和機器選擇染色體部分組成FJSP的染色體，考慮到兩部分染色體的編碼含義不同，在解碼過程中分別對其進行解碼，并最終生成機器上加工工序先后加工順序的活動調(diào)度。首先，逐位解碼工序部分染色體基因，先確定基因位的工件工序含義；然后，按照對應(yīng)的機器選擇部分染色體編碼基因，選擇其加工機器，生成工序在所選機器上的活動調(diào)度；最后，對所有工件工序進行先后排序得到調(diào)度結(jié)果。其具體步驟如下。

步驟1讀取染色體的1位基因，計算其在染色體出現(xiàn)的位置和次數(shù)，解碼為工件j的第h道工序Ojh。

步驟2從機器選擇染色體對應(yīng)位置確定其加工機器Mi，并獲取加工時間Tpi jh。

步驟3生成機器加工的活動調(diào)度，即從起始時間開始依次判斷機器上已排序加工工件的時間間隔是否可以插入該工件的加工。

1)設(shè)該工序Ojh插入位置為k，k=0，表示插入到設(shè)備加工工件順序的首位，此時機器空閑時間Tzi=0；

2)根據(jù)式(3)計算Tsjh和 式(4)計算Tcjh。

3)判斷后面是否還有工件。若沒有，則表示插入到最后位置，結(jié)束判斷；否則繼續(xù)下一步。

4)判斷是否滿足該工序Ojh完工時間不大于k位置后工件的開工時間。如滿足，則表示可以插入該工件前，結(jié)束判斷；否則繼續(xù)下一步。

5)判斷下一個工件間隔是否可以插入，即把插入位置向后移動1位，k=k+1，獲得其完工時間Tck，同時該機器空閑時間Tzi=Tck，轉(zhuǎn)至2)，重新計算Tsjh和Tcjh。

4)工序部分染色體的基因是否解碼完畢。是則解碼過程結(jié)束；否則轉(zhuǎn)步驟1繼續(xù)。

至此，完成FJSP染色體的解碼，生成FJSP工件加工的活動調(diào)度，并可以排出每臺加工機器上加工工件的順序，從而得到所有工序加工的開始和結(jié)束時間。

某例染色體解碼后生成活動調(diào)度如圖3所示。其中，Oef、Ojh、Oml、Ouv表示設(shè)備Mi上加工的不同工件的某道工序，TSijh表示設(shè)備Mi上加工工件j的h工序需要的調(diào)整時間，Tbi表示設(shè)備Mi的故障時間。

圖3染色體解碼生成活動調(diào)度Figure 3 The active scheduling of chromesome encoding

3.3 FJSP的初始化

FJSP染色體包含工序排序問題和機器選擇問題，其初始化要同時解決這2個問題。隨機初始化具有樣本多樣性的優(yōu)點，有利于GA初始種群的多樣化并且分布于整個解空間。所以本文采用隨機初始化染色體方式。

工序染色體生成方法如下。

1)原始代碼空間由所有工件的工序組成，工序由工件號表示，空間中工件號數(shù)量與其工序數(shù)量相同。

2)隨機選擇代碼空間工件號作為工序基因，同時在原始空間去除該代碼，直到生成工序部分染色體的全部基因。

機器染色體生成方法：染色體基因位表示工件工序加工機器序號，該數(shù)字的選擇是可選機器序號隨機產(chǎn)生的。

1)從工序染色體第一位基因開始，選出工件的工序。

2)從工序可選機器集隨機選出機器代碼作為機器染色體基因。

從當年“三天建一層樓”的“深圳速度”，到今天破舊立新的自貿(mào)區(qū)探索，都是“一個汗珠摔八瓣”拼出來的。不做光說不練的“假把式”，爭當腳踏實地的“實干家”，“擼起袖子加油干”就是成就改革事業(yè)的“硬道理”。

3)選擇工序染色體的下一位基因，重復(fù)執(zhí)行2)，直到所有工序基因選擇加工機器，即完成了所有加工機器的選擇。

3.4交叉操作

3.4.1工序排序部分

采用POX方法交叉操作，可以保持父代染色體的優(yōu)良特征[10]。

1)工件集{J1,J2,···,Jn}采用隨機方式進行工件抽取，從而得到工件子集set1和set 2；

2)分別對2個工件子集生成其子代C1/C2，如圖4(a)所示。

對工件子集set1生成子代C1，依次按父代染色體基因位進行順序復(fù)制。如果父代染色體P1的基因位是set1所包含的工件，則保持位置和順序不變，復(fù)制到子代C1；然后根據(jù)C1空白位置，按順序依次復(fù)制父代染色體P2中的非set1工件的基因位到C1。

同樣的方式，對工件子集set 2生成子代C2。

3.4.2機器選擇部分

1)在染色體長度N0內(nèi)隨機產(chǎn)生整數(shù)r表示交叉的基因數(shù)目；

2)在長度N0范圍內(nèi)隨機產(chǎn)生r個不等的整數(shù)表示交叉基因的位置；

3)根據(jù)步驟2)產(chǎn)生的交叉基因的位置，復(fù)制該位置的父代P1基因到子代C1相應(yīng)位置，然后根據(jù)C1染色體基因的空白位置，把對應(yīng)位置的父代P2基因復(fù)制到子代C1相應(yīng)基因位置；

4)同樣地，復(fù)制相應(yīng)位置的父代P2的基因到子代染色體C2，并把其他位置復(fù)制父代染色體P1的對應(yīng)基因，得到子代染色體C2。

如圖4(b)所示，圖中隨機生成灰色基因位，C1復(fù)制相應(yīng)位置P1中的基因，C1空白位置基因按順序依次復(fù)制P2白色基因位，獲得新的染色體C1。

3.5變異操作

工序染色體的變異操作采用隨機互換兩點基因變異。

對機器選擇染色體部分，為較好保持機器順序信息，本文采用如下的變異方法。

1)隨機選擇一位基因，設(shè)置為加工時間最短的機器號；

圖4交叉操作Figure 4 Crossover operation

2)再隨機選擇一位基因，設(shè)置為可選的隨機的機器號。

3.6 局部搜索

采用參考文獻[13]中的兩級鄰域搜索方法，即通過改變工件的可選設(shè)備進行跨機器移動工序和移動同機器上工序的前后加工順序?qū)崿F(xiàn)兩級鄰域搜索方法，對適應(yīng)值前10%的進行局部搜索，提高解的質(zhì)量。

3.7 選擇操作

采用錦標賽方法和精英保留策略，隨機選擇3個適應(yīng)度最高的染色體到交叉池中，如果適應(yīng)值相同，優(yōu)先選擇擁擠距離大的進入交叉池，直到交叉池染色體全部選擇完成后，結(jié)束選擇循環(huán)操作。

4測試實例

采用VC++編程，程序在酷睿i7，CPU主頻2.8 G，內(nèi)存32 G的筆記本上運行。初始種群個數(shù)為200，交叉概率為0.8，變異率為0.01，迭代100次，采用保優(yōu)策略。采用上述遺傳算法對經(jīng)典FJSP問題用例MK01、8P和10P問題進行了測試對比。這3個用例中MK01和8P代表部分柔性作業(yè)車間，其工件工序數(shù)和可加工設(shè)備不同。10P代表了完全柔性作業(yè)車間，其工件工序數(shù)相同且可加工設(shè)備相同；而8P和10P的工件工藝加工時間相似，可以采用相同的調(diào)整時間、運輸時間、故障時間進行性能改進效果對比。參考所選經(jīng)典用例工件的加工時間，用例的調(diào)整時間可以采用小于3的隨機數(shù)；運輸時間中常數(shù)Tc假定為1；f(d)直接用設(shè)備數(shù)間隔表示；設(shè)備以10%的概率產(chǎn)生4以內(nèi)的隨機數(shù)為故障時間。測試結(jié)果如表1所示。表中各列中實例問題表示測試用例；最優(yōu)解表示僅考慮加工時間的最優(yōu)完工時間；輔助時間表示考慮了哪些細分輔助時間，改進前數(shù)據(jù)表示優(yōu)化時不考慮該輔助時間但實際生產(chǎn)具有輔助時間的情況下的最大完工時間；改進后數(shù)據(jù)表示優(yōu)化時考慮輔助時間優(yōu)化的最大完工時間；優(yōu)化百分比為改進后完工時間相對改進前完工時間的減少百分比。測試結(jié)果顯示，相對不考慮輔助時間進行車間調(diào)度優(yōu)化，考慮輔助時間的車間調(diào)度優(yōu)化，其性能有明顯差別。以8P為例，存在輔助時間的情況下，6種情況的調(diào)度甘特圖對比如圖5～10所示，可以明顯看出調(diào)度結(jié)果有很大不同，并且完工時間有明顯的改進。

表1柔性作業(yè)車間調(diào)度測試結(jié)果Table 1 The test results of flexible job shop

圖5是否考慮順序無關(guān)調(diào)整時間優(yōu)化的調(diào)度甘特圖Figure 5 The Gant chart of scheduling with sequence-independent setup time or not

圖6是否考慮順序相關(guān)調(diào)整時間優(yōu)化的調(diào)度甘特圖Figure 6 The Gant chart of scheduling with sequence-dependent setup time or not

圖7 是否考慮運輸時間優(yōu)化的調(diào)度甘特圖Figure 7 The Gant chart of scheduling with transportation time or not

圖8 是否考慮故障時間優(yōu)化的調(diào)度甘特圖Figure 8 The Gant chart of scheduling with failure time or not

5小結(jié)

本文分析了柔性作業(yè)車間生產(chǎn)過程中的各個時間段，建立了生產(chǎn)過程時間模型，研究了柔性作業(yè)車間調(diào)度問題，并設(shè)計基于工序整數(shù)編碼和機器整數(shù)編碼的混合GA 算法來求解FJSP。最后采用FJSP的典型用例，對考慮調(diào)整時間、故障時間以及運輸時間因素的柔性作業(yè)車間調(diào)度問題模型進行了驗證、對比、分析和總結(jié)。結(jié)果顯示，輔助時間對優(yōu)化性能和結(jié)果都有明顯影響，在進行車間調(diào)度優(yōu)化研究時應(yīng)該給予充分考慮，從而使得理論調(diào)度在實踐中得到良好應(yīng)用。

圖9是否考慮順序無關(guān)+運輸時間+故障時間優(yōu)化的調(diào)度甘特圖Figure 9 The Gant chart of scheduling with sequence-independent setup time +transportation time +failure time or not

圖10 是否考慮順序相關(guān)+運輸時間+故障時間優(yōu)化的調(diào)度甘特圖Figure 10 The Gant chart of scheduling with sequence-dependent setup time +transportation time +failure time or not