面向智能制造的柔性車間調(diào)度算法研究

何 濤

（溫州職業(yè)技術(shù)學(xué)院，浙江 溫州 325000）

一、引言

2015年中國發(fā)布《中國制造2025》，部署推進(jìn)實施制造強國戰(zhàn)略，提出以推進(jìn)信息化和工業(yè)化深度融合為主線，大力發(fā)展智能制造。在多品種、小批量的生產(chǎn)模式成為主流市場環(huán)境下，如何優(yōu)化生產(chǎn)調(diào)度，實現(xiàn)智能、低耗和準(zhǔn)時交貨成為管理者追求的目標(biāo)。智能生產(chǎn)要求在設(shè)計、供應(yīng)、生產(chǎn)和服務(wù)各環(huán)節(jié)實現(xiàn)端到端無縫協(xié)作，從而使整個制造過程的感知、思維、推理、路徑規(guī)劃和決策成為一個整體。智能生產(chǎn)是智能制造的主線，而智能車間是智能生產(chǎn)的主要載體。在智能生產(chǎn)車間獲得訂單加工的任務(wù)后，需進(jìn)一步對該任務(wù)以制造系統(tǒng)預(yù)先設(shè)定的某個或多個性能指標(biāo)為目標(biāo)進(jìn)行優(yōu)化計算。只有基于內(nèi)嵌調(diào)度算法的局部最優(yōu)或次優(yōu)，才能真正實現(xiàn)制造車間調(diào)度的柔性、適應(yīng)性和可靠性[1-5]。

本文面向智能制造的需求對作業(yè)車間調(diào)度優(yōu)化管理問題進(jìn)行研究，根據(jù)多品種小批量生產(chǎn)的柔性車間作業(yè)實際情況，考慮加工時間、機臺負(fù)荷率、總的負(fù)荷率等因素，建立調(diào)度優(yōu)化的多目標(biāo)函數(shù)，并引入分解思維對多目標(biāo)優(yōu)化算法進(jìn)行改進(jìn)設(shè)計，實現(xiàn)多目標(biāo)組合優(yōu)化的柔性車間調(diào)度系統(tǒng)。

二、柔性車間作業(yè)調(diào)度問題概述

柔性車間的作業(yè)調(diào)度問題可概述為：有n 個工件（J 表示工件作業(yè)集）需在m 臺設(shè)備上加工（M 表示機設(shè)備集）[6-7]。每個作業(yè)Ji（1≤i≤n）有ni道工序Oij（1≤i≤n，1≤j ≤n）需要加工。每道工序Oij由可加工的機床集Mij中任一臺機床加工，其中Mij?M。調(diào)度管理的目標(biāo)是在滿足各種資源約束和工序前后關(guān)系約束的前提下，以優(yōu)化管理的目標(biāo)為導(dǎo)向，為工件的加工作業(yè)集選擇最優(yōu)的加工設(shè)備集，并給每臺加工設(shè)備規(guī)劃最佳的作業(yè)加工次序和起始加工時間。因此，需要解決問題：（1）路徑分配子問題，即確定各工件的加工機器；（2）加工排序子問題，即對確定各個機器上的加工先后順序。

通常企業(yè)生產(chǎn)調(diào)度優(yōu)化管理考慮下列四種目標(biāo)因素中的一種或多種因素的組合：（1）與生產(chǎn)量相關(guān)，如makespan、平均流程時間、最大流程時間等；（2）與作業(yè)交貨期相關(guān)，如延誤作業(yè)百分比、平均延誤、最大延誤等；（3）與在制品相關(guān)，如作業(yè)平均等待時間等；（4）與設(shè)備利用率相關(guān)，如設(shè)備總的使用率，關(guān)鍵設(shè)備使用率等。

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

為了更加貼近生產(chǎn)時間，本文同時選取最大作業(yè)完工時間、最大設(shè)備負(fù)荷和所有設(shè)備總負(fù)荷這三個性能指標(biāo)，建立如下目標(biāo)函數(shù)：

1.最大作業(yè)完工時間

式（1）中，Ti是設(shè)備Mi的完工時間。

2.最大的設(shè)備負(fù)荷WM

式（2）中，Wi是設(shè)備Mi的工作負(fù)荷。

3.所有設(shè)備的總負(fù)荷

三、基于MOEA/D 的柔性車間調(diào)度的多目標(biāo)算法設(shè)計

以上論述已經(jīng)建立了多目標(biāo)優(yōu)化問題的模型，如何求解是重要的一環(huán)。本文采用分解思想，采用基于分解的多目標(biāo)進(jìn)化算法（MOEA/D）（Qingfu Zhang 等）[8]，利用切比雪夫聚合方法將多目標(biāo)車間調(diào)度的求解轉(zhuǎn)化成為多個單目標(biāo)問題同時優(yōu)化，降低了計算難度、提高了優(yōu)化效率。

其中，λ=（λ1，…，λm）是一組權(quán)重向量，為參考點，對于所有的i=1，…，m，有。

具體而言，首先對多目標(biāo)調(diào)度問題的可行解的編碼形式進(jìn)行設(shè)計；然后是種群的初始化；接著產(chǎn)生每個子目標(biāo)的權(quán)重向量；再根據(jù)向量間的歐幾里得距離計算將種群劃分成為多個鄰域集合，并在選定的鄰域空間內(nèi)完成個體的交叉、變異等遺傳進(jìn)化操作；最后將新生成的個體擇優(yōu)保存下來，進(jìn)入下一輪迭代，直到達(dá)到設(shè)定條件時結(jié)束。整個算法設(shè)計的流程圖如圖1 所示。

圖1 柔性車間作業(yè)調(diào)度算法流程框架

關(guān)鍵步驟包含如下幾個方面：

（一）編碼和解碼

柔性作業(yè)車間調(diào)度問題的可行解實質(zhì)上是作業(yè)任務(wù)在可加工設(shè)備集中進(jìn)行選擇，并完成所有的作業(yè)進(jìn)行排序。因此，解的編碼形式可以解決機器分配和作業(yè)排序兩個決策問題。根據(jù)其特點，采用雙層編碼形式：第一層工序編碼染色體，確定工序間的先后加工順序，解決作業(yè)排序的問題；第二層是機器編碼染色體，確定所選擇的加工機器，解決機器分配的問題。兩層融合一起形成一條染色體，即為柔性作業(yè)車間調(diào)度的一個可行解。

1.編碼。結(jié)合表1，說明具體的編碼過程。表1是包含有3 個工件和5 臺機器的車間生產(chǎn)。首先生成基于工序的編碼染色體，為了表示工件的加工順序，生成表1 的工件編碼染色體矩陣，矩陣的元素aij表示工件i 的第j 道作業(yè)工序，該元素對應(yīng)的取值表示對應(yīng)作業(yè)工序的排列順序，工件不存在的工序?qū)?yīng)位置的元素置為0。因此對于表1，有矩陣編碼O，可以在初始化的時候，隨機生成一個對應(yīng)的實際加工作業(yè)工序矩陣。比如生成O1：

表示生產(chǎn)的工件工序的加工先后順序為：O21-O11-O31-O12-O22-O13，即為形成了一個編碼染色體的第一層。

接著生產(chǎn)編碼染色體的第二層：根據(jù)工序的加工順序，選擇加工設(shè)備。對照表1 中，按照第一層編碼的基因順序，形成每個作業(yè)基因的可加工設(shè)備集。比如有，k 個作業(yè)工序，形成k 個可選設(shè)備的子集{S1，S2，…，Sk}，其中Si表示第i 個作業(yè)工序的可加工設(shè)備集合。編碼過程如圖2 所示。

圖2 編碼形式

2.解碼。解碼時先對雙層編碼的第一層的作業(yè)工序編碼基因串進(jìn)行解碼，按照從左往右的順序依次獲取編碼的基因，從而確定所有作業(yè)工序的加工順序，即形成一個有序的作業(yè)工序列表；然后依據(jù)第二層機器編碼基因串確定每個作業(yè)的對應(yīng)的加工機器，即形成設(shè)備加工的時間順序表格；最后按照設(shè)備加工順序表以最早允許加工時間為開始時間，進(jìn)行加工作業(yè)安排，即可形成可行解。

（二）種群初始化和選擇方法

種群初始化選擇現(xiàn)有的方法較多，各有利弊。常見的方法有：比例選擇（輪盤賭選擇）、穩(wěn)態(tài)繁殖、反向?qū)W習(xí)選擇、排序選擇法等。為了合適的種群初始化選擇，本文采用隨機的輪盤賭選擇法和精英個體解選擇的兩階段初始化方法。

1.種群初始化

首先，隨機初始化工序編碼鏈。對應(yīng)前面的工序矩陣編碼O，隨機生成其對應(yīng)的每個元素的值。生成元素的值的范圍應(yīng)該是在[1，2，…，k]，其中，k 為總的工序數(shù)，不存在的工序，其對應(yīng)的元素值為0。比如上文中O1即為隨機長生的工序個體，對應(yīng)的加工工序染色體為：O21-O11-O31-O12-O22-O13。

其次，隨機初始化工序編碼鏈。對應(yīng)雙層編碼的第一層的每個工序基因隨機初始化選擇可加工的機器，從而生成機器編碼鏈。比如對照O1工序鏈對應(yīng)生成機器鏈M5-M1-M3-M2-M5-M1。

2.選擇方法

首先，使用隨機的輪盤賭選擇法。假設(shè)最初產(chǎn)生的n 個可行解，個體i 的適應(yīng)度值為fi，那么該個體被種群選擇保留的概率表示為

其次，保留初始化種群中的精英個體。對所有的個體按照適應(yīng)度進(jìn)行排序，挑選群體中最優(yōu)的幾個個體進(jìn)行保留。

（三）權(quán)重向量的產(chǎn)生

（四）個體交叉操作

首先，確定上層的交叉方式，然后根據(jù)上層交叉形式來實現(xiàn)兩層編碼的同時交叉操作，一方面保證在工序交叉過程中同一工件的不同工序間一定的先后順序不能錯位，另一方保證下層的機器交叉對應(yīng)工序交叉，從而使得整個二層編碼依然是調(diào)度方案的可行解。具體過程如下：

步驟1：利用交叉概率Pc，選出需要交叉的父代個體。

步驟2：隨機產(chǎn)生一個整數(shù)r，1≤r≤k；將所有的工件作業(yè)工序按照r 分成兩個部分：Ji，1 ≤i≤r 和r＜j≤k。

步驟3：選擇一個父代1，在其第一層工序編碼層中將Jr工件包含的基因位和第二層對應(yīng)的基因保持不變，并復(fù)制到子代染色體對應(yīng)基因位上去；將另外一個父代2 中的除Jr工件外的其余工件對應(yīng)的兩層基因依次復(fù)制到子代染色體剩余的基因位中去；第二層設(shè)備編碼層依然對應(yīng)第一層的位置進(jìn)行交叉操作，從而簡單有效地滿足機器約束。假設(shè)隨機產(chǎn)生數(shù)r=2，則加工工件結(jié)合分為兩個部分{J1，J2}和{J3}，整個操作過程如圖3所示。

圖3 交叉過程

（五）變異操作

選擇適當(dāng)?shù)淖儺惙椒ň植康玫礁鼉?yōu)的解。根據(jù)雙層編碼的特點，變異操作采用兩種方式：第一層部分基因交叉變異，第二層對應(yīng)基因自變異的形式。具體過程如下：

步驟1：產(chǎn)生變異概率Pb，選出需要變異的父代個體。

步驟2：隨機產(chǎn)生一個整數(shù)r，1≤r≤k；將染色體編碼層的第一層的工件作業(yè)工序基因Jk與其鄰域基因Jk+1，進(jìn)行交叉變異操作；將染色體編碼層的第二層對應(yīng)的基因位在可加工設(shè)備集進(jìn)行隨機自變異操作，具體過程如圖4 所示。

圖4 變異過程

四、仿真及分析

為對上述方法正確性進(jìn)行驗證，選取Kacem基準(zhǔn)測試中的一個實例進(jìn)行仿真，該測試集具體詳細(xì)信息如表2 所示。設(shè)定種群大小為100，進(jìn)化迭代數(shù)為100，交叉概率為0.5，變異概率為0.01，連續(xù)仿真10 次后，可得部分最優(yōu)解如表3 所示。

表2 仿真實例

表3 仿真支配解

根據(jù)上述求得的最佳非支配解，從最大作業(yè)完工時間、最大的機器負(fù)荷、所有機器總負(fù)荷等三個方面因素來綜合衡量，以解1 最優(yōu)，可以得到甘特圖（見圖5）。

圖5 甘特圖

五、總結(jié)

根據(jù)智能制造對作業(yè)車間調(diào)度優(yōu)化管理的新要求，研究多品種小批量生產(chǎn)的柔性作業(yè)車間調(diào)度，綜合考慮最大作業(yè)完工時間、最大的機器負(fù)荷、所有機器總負(fù)荷等因素，建立多目標(biāo)函數(shù)；引入分解的思想，基于分解的多目標(biāo)進(jìn)化算法進(jìn)行改進(jìn)設(shè)計，對編碼形式、遺傳操作等進(jìn)行設(shè)計；最后引入標(biāo)準(zhǔn)的數(shù)據(jù)集進(jìn)行驗證，證明算法的正確性和有效性。