面向智能制造的柔性車間調度算法研究

何 濤

（溫州職業技術學院，浙江 溫州 325000）

一、引言

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

本文面向智能制造的需求對作業車間調度優化管理問題進行研究，根據多品種小批量生產的柔性車間作業實際情況，考慮加工時間、機臺負荷率、總的負荷率等因素，建立調度優化的多目標函數，并引入分解思維對多目標優化算法進行改進設計，實現多目標組合優化的柔性車間調度系統。

二、柔性車間作業調度問題概述

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

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

表1 柔性車間作業調度

為了更加貼近生產時間，本文同時選取最大作業完工時間、最大設備負荷和所有設備總負荷這三個性能指標，建立如下目標函數：

1.最大作業完工時間

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

2.最大的設備負荷WM

式（2）中，Wi是設備Mi的工作負荷。

3.所有設備的總負荷

三、基于MOEA/D 的柔性車間調度的多目標算法設計

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

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

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

圖1 柔性車間作業調度算法流程框架

關鍵步驟包含如下幾個方面：

（一）編碼和解碼

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

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

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

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

圖2 編碼形式

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

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

種群初始化選擇現有的方法較多，各有利弊。常見的方法有：比例選擇（輪盤賭選擇）、穩態繁殖、反向學習選擇、排序選擇法等。為了合適的種群初始化選擇，本文采用隨機的輪盤賭選擇法和精英個體解選擇的兩階段初始化方法。

1.種群初始化

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

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

2.選擇方法

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

其次，保留初始化種群中的精英個體。對所有的個體按照適應度進行排序，挑選群體中最優的幾個個體進行保留。

（三）權重向量的產生

（四）個體交叉操作

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

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

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

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

圖3 交叉過程

（五）變異操作

選擇適當的變異方法局部得到更優的解。根據雙層編碼的特點，變異操作采用兩種方式：第一層部分基因交叉變異，第二層對應基因自變異的形式。具體過程如下：

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

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

圖4 變異過程

四、仿真及分析

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

表2 仿真實例

表3 仿真支配解

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

圖5 甘特圖

五、總結

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