考慮準備時間和工件分批的柔性作業(yè)車間調度

李田豐 朱斌 張奎

關鍵詞：柔性作業(yè)車間調度;改進遺傳算法;準備時間;柔性分批

0引言

車間調度是制造系統(tǒng)的基礎，在滿足約束條件的情況下，通過優(yōu)化生產性能指標，充分利用生產資源合理地安排不同種類工件的作業(yè)加工次序，以降低企業(yè)的生產成本，提高企業(yè)的競爭力。車間調度是一個復雜的問題，具有離散性、復雜性、不確定性和多約束性等特點。柔性作業(yè)車間調度問題（Flexible Job Shop Scheduling Problem，F(xiàn)JSP）是作業(yè)車間調度問題（Job Shop Scheduling Problem，JSP）的擴展，是更為復雜的組合優(yōu)化問題。考慮準備時間和工件分批的柔性作業(yè)車間調度問題，是根據(jù)車間實際生產過程中受準備時間和工件批量影響的特點，對工件進行合理地分批，確定最優(yōu)的調度方案，滿足實際生產的需要。

近年來，眾多學者對柔性作業(yè)車間調度問題進行了深入研究。張國輝等采用改進的遺傳算法求解柔性作業(yè)車間調度問題。方水良等提出改進遺傳算法，采用雙鏈結構編碼方式解決柔性車間調度問題。Singh等采用粒子群優(yōu)化算法，求解考慮完工時間和延遲等多個目標的柔性作業(yè)車間調度問題。張騰飛等采用改進遺傳算法，產生具有基因多樣性的初始解，解決柔性作業(yè)車間調度問題。在車間實際生產過程中，工件往往成批加工，如何對工件進行分批并安排機器進行加工，已經(jīng)成為急需解決的問題。對于柔性作業(yè)車間的分批調度問題，也有學者進行了研究。王云等提出一種改進的強度Pareto進化算法，用于求解柔性作業(yè)車間中分批調度多目標優(yōu)化問題。陸漢東等提出一種禁忌搜索算法對分批調度中批次加工路線和子批加工順序進行了優(yōu)化。Gao等運用兩階段人工蜂群算法求解柔性作業(yè)車間分批調度問題。周亞勤等采用嵌套式遺傳算法，對工件進行批量劃分、加工路徑確定和生產調度的綜合優(yōu)化。胡燕海爭提出染色體兩級編碼的方法，用遺傳算法求解柔性作業(yè)車間柔性分批調度問題。這些論文雖然對柔性作業(yè)車間分批調度問題進行了研究，但是沒有考慮工件不同工序間準備時間不同的特點。

考慮準備時間和工件分批的柔性作業(yè)車間調度問題，是在滿足實際生產過程中所需準備時間和工件分批的約束條件下，合理地安排加工路線，以實現(xiàn)最大加工時間的最小化，提高生產效率。本文以生產準備時間和工件柔性分批為約束條件，采用改進的遺傳算法對柔性作業(yè)車間調度問題進行求解，最后通過對調度案例進行分析，驗證了該算法可以很好地解決考慮準備時間和工件分批的柔性作業(yè)車間調度問題，能夠得到最優(yōu)的調度方案，使得工件的最大完工時間最小。

1柔性作業(yè)車間調度模型

1.1問題描述

柔性作業(yè)車間調度問題可描述為：有n種工件在M臺機器上加工，每種工件可批量劃分為若干子批，各子批次批量數(shù)隨機分配;每種工件各子批次的每道工序可按照一定的工藝次序在若干臺機器上進行加工，具有柔性的加工路徑，各子批次工件不同工序之間需要一定的調整準備時間。工件在加工過程中應滿足以下假設條件：

（1）每種工件的每道工序在可加工機器上的加工時間確定;

（2）同一時刻每臺機器只能加工一道工序;

（3）同一臺機器加工完同一批次的工件后再加工下一批次的工件;

（4）每道工序的生產準備時間已知;

（5）同種工件同一工序在同一臺機器上加工時，不需要準備時間。

在滿足以上假設條件下，以最小化最大完工時間為優(yōu)化指標，制定合理的調度方案。

1.2符號定義

1.3約束和目標函數(shù)

約束1：各工件子批的每道工序只能在一臺機器上加工，則有：

表1所示為一個柔性作業(yè)車間調度問題實例，有3種工件，在4臺機器上加工，每種工件有20個，每個工件有3道工序，每道工序均可在多臺機器上加工。

在該實例中，x為該工件的當前工序不能在對應的機器上加工;D12為工件1的第2道工序，可選擇的機器集M=[M2，M4]。

2求解算法

2.1柔性分批方法

對工件進行合理的批量劃分是解決柔性作業(yè)車間調度問題的關鍵，采用柔性分批方式對工件進行分批，可以均衡機器負荷，提高生產效率。對工件進行柔性分批時，假設各工件的子批上限為Ⅳ，各工件的子批數(shù)量和各子批的批量數(shù)隨機產生。

以表1所示的調度實例為例，假設各工件的子批上限為4，分批方案如表2所示。

2.2編碼

在用改進的遺傳算法求解柔性作業(yè)車間調度問題時，工序排序和機器選擇部分是編碼的關鍵。本文采用雙層編碼的方式解決工件分批和各工件子批工序調度排序的問題，染色體由兩層組成，每層染色體各由兩部分組成。第一層前一部分表示工件分批編碼，后一部分表示各工件子批的工序排序編碼。在第二層編碼中與工件分批編碼對應的部分用無意義的“0”表示，機器選擇部分要與第一層的工件子批工序排序部分一一對應。

以表2中第二種分批方式為例，對工序編碼中的數(shù)字予以說明，如表3所示。

采用雙層編碼方式進行編碼時，其中一條染色體如圖1所示。

在圖1所示的染色體編碼中，3種工件的分批方案為（3，2，2）。在第一層工件子批工序調度編碼中，第一次出現(xiàn)的6表示工件3的第1個子批的第1道工序，第二次出現(xiàn)的6表示工件3的第1個子批的第2道工序。在第二層機器選擇編碼中，工序O有3臺機器可以選擇，編碼中的4表示在機器M4上加工。

2.3解碼

染色體解碼過程是將染色體轉化為工件工序的調度解，主要是解決工件各子批工序排序和機器選擇問題。在對染色體進行解碼時，先對各工件分批編碼進行解碼。在對機器選擇部分進行解碼時，從左到右依次讀取染色體的機器編碼，轉換為機器矩陣J、工件加工時間矩陣T1和機器準備時間矩陣T2。在對工序排序進行解碼時，從左到右讀取染色體的工序編碼部分。同一種工件的各子批之間存在并行工序，采用間隙擠壓算法計算各工件子批工序在機器上的加工時間段。解碼過程中要對工件的加工結束時間與機器的空閑時間段進行比較，之后在可加工該道工序的所有機器中選擇完工時間最早的機器。

2.4選擇

遺傳算法的每一次迭代都需要用選擇算子選擇出需要進行交叉或變異的個體，選擇適當?shù)膫€體進入下一代。選擇算子有不同的性質和適應范圍，由優(yōu)化調度目標確定選擇策略。田曼等提出的錦標賽選擇方式對染色體的基因進行選擇，保留種群中的最優(yōu)個體。

2.5交叉

交叉是將父代染色體的基因交換組合之后產生新個體，交叉操作決定了遺傳算法的性能。在雙層編碼中，工序分批編碼的改變會引起下層機器選擇編碼的改變，在進行交叉操作時只需對工序分批編碼進行交叉操作。劉瓊等提出的IPOX交叉方法對染色體的工序編碼進行交叉操作。以表1中的調度實例為例，將3種工件分為2個集合、為2個父代染色體，C1、C2為交叉產生的2個子代染色體。染色體的工序分批編碼交叉操作過程如圖2所示。

2.6變異

變異操作是通過隨機改變染色體的某些基因以產生新的個體，增加種群的多樣性。周超等提出變異方法，進行變異操作。同交叉操作一樣，只需對工序分批編碼進行變異操作。以圖1中染色體編碼為例，將染色體中的工序分批編碼進行倒序排序，再將染色體中任意一個基因插到染色體最前面，可以得到子代染色體。染色體的工序分批編碼變異操作如圖3所示。

3調度案例

對一個4X6型柔性作業(yè)車間調度進行實例仿真，以徐本柱等提出的實例數(shù)據(jù)驗證改進遺傳算法的性能。該調度問題中有4種工件，在6臺機器上加工，每種工件有8個，每個工件有3道工序，每道工序均可在多臺機器上加工。徐本柱等采用工序并行解碼算法，求得最大完工時間為83min，得到工件的最優(yōu)分批方案為（1，1，4，4）。本文采用改進的遺傳算法，得到的最大完工時間的最優(yōu)值為79min，工件的最優(yōu)分批方案為（4，1，3，4），優(yōu)于徐本柱等采用的算法。采用改進的遺傳算法求解時，各工件分批方案的最大完工時間如表4所示。

在實際加工過程中，工件在不同機器上加工時，安裝、定位及刀具的更換等需要加工準備時間。在文獻中4X6算例的基礎上，考慮工件的加工準備時間，工件分批加工時工序的準備時間等于工序單個工件的加工時間。在考慮準備時間和工件分批的情況下，用本文改進的遺傳算法求解時，求得最大完工時間的最優(yōu)值為99 min，其最優(yōu)分批調度方案為（4，1，4，4），第2種工件不分批，其余工件均分為4批，各批次的批量數(shù)為：（2，3，2，1）、（2，2，2，2）、（3，1，2，2）。對應調度方案的甘特圖如圖4所示。

在圖4中，黑色部分表示工件的加工準備時間，F(xiàn)5為第2種工件，首次出現(xiàn)在機器M3上，表示第2種工件的第1道工序在機器M5上加工。F7為工件3的第2個子批，最后一道工序在機器慨上完成，完工時間為99min。

4結束語

本文對柔性作業(yè)車間調度問題進行了描述，結合實際車間生產要求，以準備時間和工件分批為約束條件，以最小化最大完工時間為優(yōu)化目標，建立了考慮準備時間和工件分批的柔性作業(yè)車間調度模型。采用柔性分批的方法對工件進行批量劃分，用雙層編碼的方式對模型進行求解，對工件的批量劃分和工序調度進行了優(yōu)化，提高了算法的求解效率。通過分析考慮準備時間和工件分批的柔性作業(yè)車間調度案例，得到最優(yōu)的調度方案，驗證了算法的可行性和有效性，能夠更好地解決實際柔性作業(yè)車間調度問題。