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

何 濤

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

一、引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（一）編碼和解碼

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

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

表示生產(chǎn)的工件工序的加工先后順序?yàn)椋篛21-O11-O31-O12-O22-O13，即為形成了一個(gè)編碼染色體的第一層。

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

圖2 編碼形式

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

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

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

1.種群初始化

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

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

2.選擇方法

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

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

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

（四）個(gè)體交叉操作

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

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

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

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

圖3 交叉過程

（五）變異操作

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

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

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

圖4 變異過程

四、仿真及分析

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

表2 仿真實(shí)例

表3 仿真支配解

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

圖5 甘特圖

五、總結(jié)

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