李田豐 朱斌 張奎

關(guān)鍵詞：柔性作業(yè)車間調(diào)度;改進(jìn)遺傳算法;準(zhǔn)備時(shí)間;柔性分批

0引言

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

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

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

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

1.1問題描述

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

（1）每種工件的每道工序在可加工機(jī)器上的加工時(shí)間確定;

（2）同一時(shí)刻每臺機(jī)器只能加工一道工序;

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

（4）每道工序的生產(chǎn)準(zhǔn)備時(shí)間已知;

（5）同種工件同一工序在同一臺機(jī)器上加工時(shí)，不需要準(zhǔn)備時(shí)間。

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

1.2符號定義

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

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

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

在該實(shí)例中，x為該工件的當(dāng)前工序不能在對應(yīng)的機(jī)器上加工;D12為工件1的第2道工序，可選擇的機(jī)器集M=[M2，M4]。

2求解算法

2.1柔性分批方法

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

以表1所示的調(diào)度實(shí)例為例，假設(shè)各工件的子批上限為4，分批方案如表2所示。

2.2編碼

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

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

采用雙層編碼方式進(jìn)行編碼時(shí)，其中一條染色體如圖1所示。

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

2.3解碼

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

2.4選擇

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

2.5交叉

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

2.6變異

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

3調(diào)度案例

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

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

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

4結(jié)束語

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