復合工藝流程下批量生產車間調度多目標優化

曾 強 楊 育 王勇智 程 博

1.重慶大學機械傳動國家重點實驗室，重慶，400030 2.河南理工大學，焦作，454000 3.重慶紅江機械有限責任公司，重慶，402100

0 引言

我國的多品種、中小批量生產企業在生產中，部分產品存在復合工藝流程。復合工藝流程是指同一種產品存在多個工藝流程，各個工藝流程的工序數可能相同也可能不同，工藝流程之間可相互替代，但不同的工藝流程所消耗的設備資源及生產效率存在差異。產生復合工藝流程的主要原因有兩個：①大多數車間普遍存在普通設備與數控設備共存、功能不一的數控設備共存、數控設備與加工中心共存的現狀[1]，為充分利用設備資源，同一產品可能需按不同的工藝流程加工；②企業進行技術改進，某些產品存在新舊工藝流程并存現象。學者已對傳統的作業車間調度問題（Job Shop scheduling problem，JSP）和柔性作業車間調度問題（flexible Job Shop scheduling problem，FJSP）進行了大量的研究并取得了豐富的成果。但是，傳統JSP和FJSP解決方案已不能解決復合工藝流程下批量生產車間調度問題。主要原因有兩個：其一是傳統JSP和 FJSP[2－5]針對的是單工藝流程而非復合工藝流程，具有復合工藝流程的車間調度問題是在傳統的JSP或FJSP基礎上增加了工藝流程合理選取的問題，比傳統的JSP或FJSP更復雜。其二是傳統的JSP和FJSP針對單件調度問題[5－8]或近似將批量車間調度問題視為單件調度問題，直接采用傳統的JSP或FJSP解決方法對批量車間調度問題進行處理的方式不夠精細，不利于生產效率的提升。文獻[2-4，9－11]的研究表明，對于批量生產車間調度問題，通過將工序總時間區分為批量啟動時間和工序加工時間，并將產品進行合理分批能取得較好的調度效果。

按各工序是否具有可選加工設備分類，復合工藝流程下批量生產車間調度主要有兩個研究方向：復合工藝流程下作業車間調度問題（Job Shop scheduling problem with multiple process flows，MPF－JSP）和復合工藝流程下柔性作業車間調度問題（flexible Job Shop scheduling problem with multiple process flows，MPF－FJSP）。本文針對MPF－JSP，建立了一類復合工藝流程下批量生產作業車間多目標優化模型。在此基礎上，提出并設計了一種復合工藝流程下作業車間調度多目標優化方法。

1 多目標優化模型

1.1 問題描述

車間需在M臺設備上對N種按批量方式生產的產品進行優化調度，同一種產品的工藝流程不唯一，其不同工藝流程的工序數可不同。假設：①產品按等量分批原則分批；②工序在設備k上的加工時間確定，加工批次的裝卸時間算在加工時間內；③批量啟動時間已知；④ 加工批次的搬運時間不計；⑤ 加工批次之間具有相同的優先級；⑥加工批次一旦開始不可中斷；⑦ 加工是非搶占式的。要求：在以上假設條件下進行工藝流程的合理選擇和加工順序的合理安排，在滿足一定約束條件下同時使多個性能指標最優。為滿足假設條件①需保證下式成立：

其中，Qn、Bn、Ln分別為產品n的生產量、加工批次數量和加工批量；Ln取Qn的約數。

1.2 優化模型

生產車間調度最關注的目標主要有三類：時間、成本、質量。復合工藝流程下的批量生產作業車間調度，因工藝流程可選，故不同工藝流程下各工序所用設備可能不同，批量啟動時間及批量啟動成本、加工時間及加工成本相應發生變化；同時，不同加工順序會影響完工時間和制造成本。假定采用不同的工藝流程都需保證加工質量一致，因此，本文以完工時間、制造成本兩個性能指標為優化目標，建立批量生產作業車間調度多目標優化模型。

式中，te為全部產品完工時刻；Cm為總制造成本；H 為加工批次總數

式（2）表示最大完工時間最小化，式（3）表示制造成本最小化。

約束條件：

式中，Sirjk、Eirjk分別為Ji工藝流程r的工序j在設備k上的開始時刻和完成時刻；Rir1jdr2gk為標志變量，d＝1，2，…，H；g＝1，2，…，Nod；若Ji的工藝流程r1的工序j和Jd的工藝流程r2的工序g在同一臺設備k上加工且工序j先于工序g，則Rir1jdr2gk為1，否則為0；Ld為加工批次Jd的加工批量。

式（4）表示若Ji上道工序與下道工序所用設備不同，則上道工序完工后才能開始下道工序加工，但可以提前進行準備使上道工序完工后可立即開始加工；式（5）表示若Ji上道工序與下道工序所用設備相同，則Ji下道工序必須在Ji完工后才能開始準備；式（6）表示同一臺設備k不能同時加工兩個工序；式（7）表示任意工序的完工時間與開始時間之差不能小于其所需時間。

2 算法設計

2.1 定義對象

為便于處理復雜的實體邏輯關系，提高程序設計的可讀性、計算效率、可擴展性，引入面向對象技術到算法整個設計過程中。本文共定義了加工設備對象、加工批次對象和染色體對象共三類對象，如圖1所示。

各對象之間的邏輯關系如下：①各對象從數據源獲取原始信息；②染體色對象CHR（f）根據J（i）.Np生成合法的工藝流程編碼賦給PFORDER屬 性；③CHR（f）根 據 J（i）.PF（PFORDER（i））.No，生成合法的加工順序編碼賦給JORDER屬性；

圖1 對象定義

④CHR（f）根據其 PFORDER、JORDER、MACH（k）.FREE 及J（i）.PF（PFORDER（i））.OPR解碼得調度矩陣R；⑤CHR（f）根據調度矩陣R計算目標向量O。

2.2 計算流程

基于Pareto尋優思想，提出并設計了改進的快速非支配排序遺傳（NSGA－Ⅱ）算法以求解上述多目標優化調度模型。算法總體計算流程[12-13]如圖2所示。

圖2 算法流程圖

2.3 編碼操作

復合工藝流程下批量生產作業車間調度問題包括兩個子問題：工藝流程的選擇和加工順序的安排。根據這個特點，采用分段編碼，即對各加工批次的工藝流程號和加工順序分別編碼。因引入了面向對象技術，可將兩個編碼分別賦予染色體對象CHR（f）的PFORDER和JORDER屬性。

式（8）所示的PFORDER編碼表示加工批次J1、J2、…、JH－1、JH分別選用工藝流程2、1、…、1、2。

JORDER采用基于工序的編碼方式，由Not個自然數組成，Not的值由式（10）計算。加工批次號i出現J（i）.PF（PFORDER（i））.No次。例如，式（9）的JORDER中的3個1分別代表加工批次J1的工序1、2、3，依此類推。這種編碼方式自然保證JORDER編碼可行且其任意排列總能產生可行加工順序。可見，各工藝流程下工序數不同可導致JORDER為變長結構。

2.4 種群初始化

設種群規模為Psize，則按如下步驟產生Psize個染色體，完成種群初始化操作。

（1）令f＝1；

（2）初始化 CHR（f）.PFORDER。 對PFORDER每一基因位i，隨機產生一個1～J（i）.Np的自然數賦給PFORDER（i）；

（3）按式（10）計算CHR（f）的工序總數Not；

（4）產生一長度為CHR（f）.Not的零向量賦給CHR（f）.JORDER；

（5）按如下的偽代碼給CHR（f）.JORDER賦值：

for p＝1to H－1

在 CHR（f）.JORDER中隨機尋找J（i）.PF（PFORDER（i））.No個為0的位置，并將此位置的值賦為iNext

將CHR（f）.JORDER中剩余為0的位置賦為H

（6）令f←f＋1；

（7）若f≤Psize，則轉步驟（2），否則種群初始化結束。

2.5 非支配排序

非支配排序的目的是計算種群中各染色體的前沿值Ra。將所有染色體進行分層，具體過程如下：找出當前種群中不被任何其他染色體支配的染色體，這些染色體的集合為第1級非支配染色體集，令Ra＝1；將第1級非支配集中的染色體從當前種群中去除，然后從剩余染色體中找出非支配染色體集，令Ra＝2；依此類推，直到種群中所有染色體的前沿值確定為止。

2.6 擁擠度計算

為增強種群的多樣性，引入染色體擁擠度Cd的概念。CHR（f）.Cd反映了該染色體周圍（同一級）相似染色體的數量，其計算公式為

式中，m為優化目標數；fq（f）為CHR（f）的第q個目標值；maxfq、minfq分別為某一前沿面上所有染色體第q個目標的最大值和最小值。

從式（11）可見，擁擠度CHR（f）.Cd越大，說明CHR（f）周圍的點越稀疏，進化過程中應給以較大的生存概率以保證種群多樣性。

2.7 遺傳操作

2.7.1 選擇操作

選擇操作采用二元聯賽機制，每次從父代種群中隨機選擇2個染色體，若二者的Ra不相等，則選擇Ra小的染色體，若二者相等，則選擇擁擠度大的染色體，將選中的染色體加入配對池POOLPOP，另一個舍棄，直到達到規模Psize／2為止。

2.7.2 交叉操作

因PFORDER為定長結構，JORDER為變長結構，故規定交叉操作只對PFORDER進行。由于PFORDER交叉后，相應加工批次Ji的工序數可能發生變化，因此需對JORDER進行修復。

如圖3所示，采用兩點交叉法，隨機產生1～H 的自然數C1和C2并使C1≤C2，將PFORDER1與PFORDER2的C1～C2之間對應的基因值進行對換。根據PFORDER1的C1～C2之間每一個基因值的變化情況，按如圖4所示的流程對JORDER1進行修復。同理，根據PFORDER2對JORDER2進行修復。

圖3 PFORDER交叉操作示意圖

2.7.3 變異操作

變異操作采用分段方式進行，包括PFORDER的變異和JORDER的變異。變異的原則是兩者分別獨立變異，即PFORDER變異則JORDER不變異，JORDER變異則PFORDER不變異。

對PFORDER的變異采用單點變異，隨機產生一個自然數i（i＝1，2，…，H）代表要變異的基因座，再隨機產生一個自然數a（a＝1，2，…，J（i）.Np）代表變異后的工藝流程號，用a取代PFORDER（i），再利用與圖4相似的原則對JORDER進行修復。

圖4 JORDER修復流程

對JORDER的變異操作設計了兩種：逆序變異和兩點交換變異。將兩種變異方式相結合有利于增強種群多樣性和尋優能力。采用這兩種變異方式可保證變異后的JORDER仍然可行，不必進行修復。

2.8 解碼操作

為充分提高生產率，在算法中采用3種精細化調度技術來減少設備空閑時間。第一，將工序總時間區分為批量啟動時間和工序加工時間，使下道工序可以提前準備，一旦上道工序加工完畢可立即開始加工下道工序[2，9]；第二，若將同一產品不同加工批次的同一工序前后安排在同一臺設備上，則后一道工序省去批量啟動時間及批量啟動成本；第三，對工序采用“間隙擠壓法”[8]進行“插入式”安排以產生活動化調度。整個調度算法的原理如圖5所示，其中白色方框代表已安排的時間段，黑色方框、條紋方框分別代表當前待安排工序的批量啟動時間段和加工時間段，Fyb為設備k的第y空閑時間段的起始時間，Fye為設備k的第y空閑時間段的結束時間，其值需根據圖6流程進行修正。

圖5 解碼示意圖

圖6 Fye值修正流程圖

解碼過程如下：

（1）從加工順序編碼JORDER中取出下一道待安排工序，設為Ji的工藝流程r的第j道工序，加工設備為k。

（2）對設備k的每一空閑時間段，按式（12）從左向右依次尋找待安排工序的可插入位置，一旦找到則退出尋找過程。

①批量啟動時間Stirjk按如下原則確定。若設備k第y空閑時間段前面的工序與待安排工序屬于同一產品不同加工批次的同一個工序，則Stirjk＝0；否則Stirjk取待安排工序在設備k上的批量啟動時間。②工序最早允許開始時間u按如下原則確定。若j＝1，則u＝Sir1k；若j＞1，令j－1工序所用設備為m，分兩種情況處理：若k＝m（圖5b），則令u＝Eir（j－1）m；否則（圖5c）令u＝Eir（j－1）m－Sirlk。

（3）將待安排工序安排在所找到的y空閑時間段內，則其起始時間為 max（u，Fyb），結束時間為 max（u，Fyb）＋Stirjk＋CtirjkLi。

（4）根據flag值修正y空閑間段后道工序的批量啟動時間、批量啟動時刻。

（5）更新設備k的空閑時間表MACH（k）.FREE。

2.9 目標值計算及終止條件

根據解碼得到的調度矩陣R計算該調度方案對應的目標值，包括最大完工時間te和制造成本Cm。采用基于最大迭代次數的終止方式，即當迭代次數超過最大迭代次數Nmax時退出進化過程。

3 實例分析

為驗證本文方法的有效性，以MATLAB 2007為編程環境實現了上述算法，并將其在某船舶零配件企業金屬加工車間生產調度中進行應用。該車間在某調度周期內要在7臺設備（車床M1、立式銑床M2、磨床M3、臥式銑床 M4、立式加工中心M5、臥式加工中心M6、搖臂鉆M7）上安排4種產品（P1、P2、P3、P4）的生產，各產品均存在2個工藝流程，編號為1、2，生產量均為200件。產品工藝參數如表1所示，表1中產品P1第一行工序1對應的向量（1，8，30，50，40）分別表示P1的工藝流程1的工序1在設備1上加工，單件加工時間為8min，批量啟動時間為30min，加工費率為50元／h，批量啟動費率為40元／h，以次類推。取最大迭代次數Nmax為200，種群規劃Psize為50。

表1 工藝參數

3.1 復合工藝流程與單一工藝流程的對比

固定加工批量向量L＝（100，100，100，100），它表示J1～J4對應的加工批量均為100件，對工藝流程1、工藝流程2和復合工藝流程分別進行優化，得到的Pareto最優解集如圖7所示，圖8～圖10是各工藝流程下某調度方案對應的設備甘特圖。

圖7 單一工藝流程與復合工藝流程下的Pareto解集

圖8 工藝流程1下A方案設備甘特圖

圖9 工藝流程2下C方案設備甘特圖

實例分析可知：

（1）由圖7和圖8可見，工藝流程1下得到了多個Pareto解，但分布過于集中，生產排產柔性不足；在工藝流程1下，4種產品用到了一般數控設備1、2、3、4、7，制造成本較低，但因加工時間長，使得完工時間較長。

圖10 復合工藝流程下B方案設備甘特圖

（2）由圖7和圖9可見，工藝流程2下只得到了一個Pareto解，說明生產排產柔性很差；在工藝流程2下，4種產品用到了設備1、2、5、6、7，其中設備5、6為加工中心，制造成本高，但它們能獨自完成原來由幾臺一般數控設備才能完成的多道工序，同時因加工中心加工速度快，使完工時間短于工藝流程1。

（3）由圖7和圖10可見，復合工藝流程下得到了多個Pareto解且解的個數較多、分布較均勻，生產排產柔性很強；在復合工藝流程下，一般數控設備與加工中心相結合，通過將產品分成多個加工批次，在數控設備和加工中心之間進行負荷均衡分配，使完工時間較短，制造成本位于單一工藝流程1和工藝流程2的制造成本之間。

3.2 復合工藝流程下不同加工批量對比

取復合工藝流程，以4種不同的加工批量方案分別進行優化：①加工批量向量L＝（200，200，200，200），②加工批量向量L＝（100，100，100，100），③加工批量向量L＝（50，50，50，50），④加工批量向量L＝（20，20，20，20），得到的 Pareto最優解集如圖11所示。

實例分析可知：

（1）在一定的范圍內，隨著加工批量的減小，Pareto解集向“左下”方向平移，說明調度解整體優化；

（2）當加工批量減小到一定幅度后再繼續減小加工批量，Pareto解集向“右上”平移，說明調度解整體發生了惡化。

產生以上現象的原因是：加工批量過大時，單個加工批次的加工時間較長，下道工序開工較晚，設備等待時間較長；進行工序插入式安排時可使空閑時間段減少，設備“時間碎片”增多，延長了完工時間；加工批次過少，生產排產柔性差，設備難以得到均衡利用。反之，隨著加工批量的減小，加工批次增多，單個加工批次的加工時間縮短、生產排產柔性增強，調度效果逐步得到改善；加工批量減小時，加工批次的增多導致加工批次的批量啟動時間所占比例逐漸增大，批量啟動成本也逐漸增加；加工批量過小時，批量啟動時間所占比例及批量啟動成本均大大增加，整體上表現出調度解的質量發生惡化。因此，可以推測，理論上存在一個最優的加工批量方案使得完工時間和生產成本綜合效果最佳。然而，問題的“組合爆炸”特點使得這個最優方案的時間成本相當高，甚至缺乏時效性。

圖11 Pareto解集

4 結論

（1）復合工藝流程下批量生產車間調度多目標優化方法能有效解決復合工藝流程下的批量生產作業車間多目標優化調度問題，幫助調度人員尋找滿意調度方案。

（2）復合工藝流程下通過分批將產品不同加工批次按不同的工藝流程進行加工，可達到均衡設備負荷的目的，使批量生產作業車間多目標調度優化效果明顯優于單一工藝流程下優化效果。

（3）加工批量大小對復合工藝流程下批量生產作業車間多目標調度效果具有顯著影響，理論上存在最優的加工批量方案使調度效果最佳，但準確確定最優的加工批量方案的時間成本很高。

[1]周延佑，陳長年.多品種、單件、小批量生產和少品種、大批量生產解決方案的新發展[J].制造技術與機床，2007（5）：28-36.

[2]潘全科，朱劍英.多工藝路線的批量生產調度優化[J].機械工程學報，2004，40（4）：36－39.

[3]孫志峻，安進，黃衛清.作業車間多工藝路線批量作業計劃優化[J].中國機械工程，2008，19（2）：183－187.

[4]孫志峻，喬冰，潘全科，等.具有柔性加工路徑的作業車間批量調度優化研究[J].機械科學與技術，2002，21（3）：348－354.

[5]潘全科，朱劍英.多工藝路線多資源多目標的作業調度優化[J].中國機械工程，2005，16（20）：1821－1826.

[6]Seo Minseok，Kim Daecheol.Ant Colony Optimisation with Parameterised Search Space for the Job Shop Scheduling Problem[J].International Journal of Production Research，2010，48（4）：1143－1154.

[7]Bagheri A，Zandieh M，Mahdavi I，et al.An Artificial Immune Algorithm for the Flexible Job－shop Scheduling Problem[J].Future Generation Computer Systems，2010，26（4）：533－541.

[8]吳秀麗，孫樹棟，余建軍，等.多目標柔性作業車間調度優化研究[J].計算機集成制造系統－CIMS，2006，12（5）：731－736.

[9]周亞勤，李蓓智，楊建國.考慮批量和輔助時間等生產工況的智能調度方法[J].機械工程學報，2006，42（1）：52－56.

[10]Jeong H L，Park J，Leachman R C.Batch Splitting Method for a Job Shop Scheduling Problem in an MRP Environment[J].International Journal of Production Research，1999，37（15）：3583－3598.

[11]Huang Rong Hwa.Multi－objective Job－shop Scheduling with Lot－splitting Production[J].International Journal of Production Economics，2010，124（1）：206－213.

[12]陳華平，谷峰，古春生，等.兩級排序遺傳算法在柔性工作車間調度中的應用[J].系統仿真學報，2006，18（6）：1717－1720.

[13]衛田，范文慧.基于NSGAⅡ的物流配送中車輛路徑問題研究[J].計算機集成制造系統，2008，14（4）：778－784.