高 勃，孫嘉玉，李學漢，趙宏軍，王 穎

（1.北京交通大學計算機與信息技術學院，北京 100044；2.北京交通大學電子信息工程學院，北京 100044；3.北京機械工業(yè)自動化研究所有限公司，北京 100120）

0 引言

智能制造全流程[1]中的多品種批量柔性生產(chǎn)作業(yè)過程[2,3]涉及多種產(chǎn)品[4～10]，每種產(chǎn)品又可以分為若干個調(diào)度子批進行加工和生產(chǎn)，每個子批的生產(chǎn)需要多個工藝流程，每個工藝流程可以由多條生產(chǎn)線來完成，因此如何劃分子批，并且為每個子批選取合理的加工路線是需要研究的重要決策問題[11～13]。生產(chǎn)總量一定時，批量過小會導致生產(chǎn)線調(diào)整時間以及工件搬運時間增加，并且子批數(shù)過多使得優(yōu)化算法的搜索空間增大，算法開銷過高。而當批量過大時，同一子批當前工藝流程所需時間變長，造成后續(xù)工藝的生產(chǎn)線處于空閑等待的時間過長，生產(chǎn)效率降低。因此本文研究適當?shù)姆峙呗砸约芭女a(chǎn)順序和生產(chǎn)線選擇的問題，以有效降低生產(chǎn)線不必要的空閑時間，降低算法的計算復雜度，縮短所需的生產(chǎn)時間[8,14～18]。

1 多品種批量柔性生產(chǎn)調(diào)度問題建模

1.1 問題描述

以圖1所示的芯體某線為例，說明多品種批量柔性生產(chǎn)調(diào)度問題。該芯體總線包含三段工藝流程，分別為預裝、釬焊和總成，分別包括四條、一條和兩條生產(chǎn)線。預計生產(chǎn)的產(chǎn)品類型有I種，生產(chǎn)線的產(chǎn)能及其與產(chǎn)品類型的匹配關系如表1所示。

表1 生產(chǎn)線產(chǎn)能及其與產(chǎn)品品種的關系

圖1 芯體某線示意圖

在生產(chǎn)過程中產(chǎn)品之間沒有優(yōu)先級之分，但是每種產(chǎn)品都有確定的加工工藝次序，在相應工藝流程加工時，可根據(jù)表1選擇加工每個子批的生產(chǎn)線。因此整個生產(chǎn)調(diào)度流程如圖2所示，即根據(jù)給定的每種產(chǎn)品的訂單需求以及生產(chǎn)線的情況，實現(xiàn)如下的調(diào)度任務：結合訂單情況，通過優(yōu)化算法給出每種產(chǎn)品的子批數(shù)和每個子批的批量，并將所有子批進行排序，同時為每一個子批選擇合適的生產(chǎn)線以及在每條生產(chǎn)線上的開始時間，最終使得完成生產(chǎn)任務所需要的生產(chǎn)時間最短。

圖2 生產(chǎn)調(diào)度流程示意圖

決策時需滿足以下約束：1）每種產(chǎn)品都按照預裝、釬焊和總成的順序依次加工；2）每個子批的任一工件的任一工藝流程不能被中斷；3）同一子批的每個工件的上一段工藝加工結束才能開始下一段工藝；4）任一子批一旦選定生產(chǎn)線進行加工，加工時間則確定；5）決策結果需滿足表1中生產(chǎn)線與產(chǎn)品類型的對應關系以及產(chǎn)能限制。

1.2 數(shù)學模型

在數(shù)學建模過程中使用到的變量如表2所示。

表2 變量定義表

表2 （續(xù)）

進而可以將多品種批量柔性生產(chǎn)的調(diào)度問題，建立如下的數(shù)學模型：

式(1)是調(diào)度優(yōu)化的目標函數(shù)，通過比較不同的方案下所有訂單任務加工結束的時間，選擇時間最短的方案作為最優(yōu)的分批調(diào)度結果。式(2)中每種產(chǎn)品的每個子批完成最后一段工藝流程時叫做一個子批加工完成；式 (3)表示每個子批的所有工件加工完成叫做子批加工結束；式(4)表示對每種產(chǎn)品的每一個子批的每一個流程有且僅有一條生產(chǎn)線進行生產(chǎn)即可；式(5)表示當兩個不同的子批選擇同一條生產(chǎn)線進行生產(chǎn)時，需等前一個子批加工結束才能進行下一個子批的生產(chǎn)；式(6)表示生產(chǎn)線的產(chǎn)能限制。

2 基于模擬退火算法的子批劃分方案

先進行子批劃分的求解，目標是確定每種產(chǎn)品的子批數(shù)以及批量。

采用不等批量等分批的情況，具體來說，當每種產(chǎn)品的目標生產(chǎn)量不同時，不同產(chǎn)品劃分的子批數(shù)是不相同的，但是對于每一種產(chǎn)品都采用等分批的方式，即同一種產(chǎn)品的每一個子批大小相等。因此，每種產(chǎn)品子批數(shù)最小值為1，即整批生產(chǎn)，子批數(shù)的最大值為Xi，即每一個工件作為一個子批，其他可能的子批數(shù)是Xi的約數(shù)，然后將產(chǎn)品i進行等量分批。假設Xi=10，可以分為Qi={1，2，5，10}批，則每個子批包含的工件數(shù)位Pi={10，5，2，1}。對于多種產(chǎn)品來說，最終的分批情況是從每一種產(chǎn)品的可能分批集合中取出一個值組成最終的分批結果，例如產(chǎn)品j的總量為Xj=15，則Qj={1，3，5，15}，那么同時加工產(chǎn)品i和產(chǎn)品j時可能的分批方案有4×4=16種。隨著生產(chǎn)產(chǎn)品種類的增多以及產(chǎn)品總量的增加，可選分批方案的組合數(shù)是非常大的，因此采用了模擬退火算法進行分批方案的搜索。

具體來說，該算法的搜索空間是所有可能存在的分批策略，每一個策略可以表示成{Q1，Q2…，Qi，…，QI}。第k次迭代時，當前的策略表示成Sk，當前最優(yōu)的策略表示成S0，同時f（Sk）和f（S0）表示對應分批策略通過生產(chǎn)排產(chǎn)方案能夠獲得的最大適應度值，具體計算方法將會在下一節(jié)中給出，且有f（Sk）＜f（S0）；對于另外一個策略Sm來說，如果f（Sm）＞f（S0），那么Sm=S0；否則，當f（Sm）＞f（Sk）的時候，那么Sk+1=Sm；若f（Sm）＜f（Sk），那么根據(jù)下式的接受概率使得Sk+1=Sm，相當于以概率1-PSA，舍棄Sm，意味著與當前分批方案Sk差值越小的方案被接受為下一次迭代策略的概率越大，遵循了擇優(yōu)的原則。需要說明的是，為了加速搜索的過程，Sm的產(chǎn)生是從Sk的領域中隨機選取的。鄰域意味著兩個策略只有其中一種產(chǎn)品的子批數(shù)目不同，如{1，3}的鄰域包含{1，1}，{1，5}，{3，5}等，但是不包括{2，5}，{2，1}等。

3 基于遺傳算法的生產(chǎn)排產(chǎn)方案

3.1 編碼方法

結合批量柔性生產(chǎn)的特點，采用基于批量的染色體和基于子批的染色體相結合的編碼方式?；谂康娜旧w用于給出每種產(chǎn)品采用的子批劃分方式，子批數(shù)以及各個子批的批量大小。

基于子批染色體采用矩陣編碼方法，第一行是工藝編碼層，第二行是生產(chǎn)線編碼層，第三行是加工時間編碼層。其中工藝編碼與生產(chǎn)線編碼均為顯性基因，參與交叉和變異操作，加工時間編碼為隱性基因，不需要參與交叉、變異，但是需要根據(jù)交叉變異的結果進行重新編碼。

工藝編碼層采用基于子批的編碼方式，即每一個基因都由子批編號表示，同一子批的不同工藝段都由相同的子批編號表示，這些相同編號出現(xiàn)的次序就代表該子批的工藝進行順序。其中子批編號采用產(chǎn)品類型和子批號配對的形式，即[類型，序號]，如[1，5]表示類型為1的第1個子批。一共有I類產(chǎn)品，每種產(chǎn)品需要生產(chǎn)Qi批，每個批次都經(jīng)過N段工藝，那么第一行含有個基因，其中有N個重復的基因按照出現(xiàn)的先后順序分別代表對應子批的工藝流程1到N，保證生成染色體的有效性。

生產(chǎn)線編碼層和加工時間編碼層都采用基于整數(shù)的編碼方式。生產(chǎn)線碼由生產(chǎn)線編號組成，根據(jù)工藝編碼層的基因隨機選擇對應工藝段的可選生產(chǎn)線，將生產(chǎn)線編號填入生產(chǎn)線編碼層對應位置，使得生成的生產(chǎn)線編碼均為有效編碼。加工時間碼則根據(jù)相應的批量染色體，工藝碼和生產(chǎn)線碼計算得到。

3.2 解碼方法

解碼操作與編碼操作的過程是相逆的，解碼操作是將染色體中每個基因攜帶的子批加工信息轉(zhuǎn)化為子批加工順序的信息，進而轉(zhuǎn)換為可行性調(diào)度解的過程：首先依據(jù)基于子批的染色體編碼基因串確定分配到每段工藝的生產(chǎn)線，然后根據(jù)基因串上各個子批出現(xiàn)的先后順序確定每條生產(chǎn)線的各個子批的先后加工順序。根據(jù)染色體解碼得到生產(chǎn)排產(chǎn)甘特圖，橫軸代表時刻，縱軸代表所有的生產(chǎn)線編號，不同顏色的矩形條代表不同的子批，其長度代表加工時間，不同的染色體對應不同的甘特圖，從中找出花費時間最小的一個作為最優(yōu)解。

3.3 適應度函數(shù)

適應度函數(shù)是遺傳算法進行選擇操作的重要依據(jù)，關系到整個群體的進化行為，其設計取決于所要求解的優(yōu)化問題[2]。排產(chǎn)方案以最小化最后一個批次的最后一個工件的最后一段工藝的完成時間為目標，因此，為了使非負值的適應度大小能夠直觀地體現(xiàn)每個染色體的優(yōu)劣程度，適應度函數(shù)設計為：

其中，g（x）為目標函數(shù)。適應度函數(shù)是目標函數(shù)的倒數(shù)，目標函數(shù)的值越小，相應的適應度值就越大，代表染色體的個體優(yōu)勢越大，那么被選中進行后續(xù)進化操作的概率也就越大。

3.4 交叉操作

3.4.1 基于加工工藝編碼染色體的交叉

針對子批編號在染色體上出現(xiàn)的順序進行的交叉操作，操作過程中子批編號與生產(chǎn)線編號的對應關系保持不變。具體操作可以描述為：首選選擇待交叉的兩條父染色體P1和P2，在兩條染色體上隨機選擇一個基因作為交叉子批，交換P1和P2中該子批在染色體中的位置，其他未選中的子批的順序從左到右保持不變填入空缺位置，從而獲得子代染色體S1和S2。

3.4.2 基于生產(chǎn)線編碼染色體的交叉

針對子批的某一工藝段有多條生產(chǎn)線進行的交叉操作，保持各子批編號出現(xiàn)的順序不變，子批編號與可選生產(chǎn)線編號的對應關系發(fā)生改變。具體的操作過程可以描述為：首先產(chǎn)生一個由0/1組成的隨機交叉編碼串，其總長度與染色體長度相等，然后找到P1染色體中交叉編碼串中1對應位置的相應工藝順序，并與P2染色體中對應工藝的生產(chǎn)線碼互換。由于交換的是相同子批的相同工藝的加工生產(chǎn)線，交換后的生產(chǎn)線均為相應工藝的其他可選擇的生產(chǎn)線，只需對加工時間碼進行相應的重新編碼即可得有效染色體。

3.5 變異操作

3.5.1 基于加工工藝編碼染色體的變異

采用雙點逆序變異法，在變異過程中子批編號出現(xiàn)的順序發(fā)生改變，但是子批編號與生產(chǎn)線編號的對應關系保持不變。具體的變異過程可以描述為：首先，在父染色體P1上隨機地挑選兩個變異點；然后將P1上兩個變異點之外的基因原封不動地遺傳到子染色體S5中，基因值和位置順序均保持不變；之后將P1上兩個變異點之內(nèi)的基因順序逆轉(zhuǎn)同時遺傳到子染色體S5中，最后得到新的子染色體S5。

3.5.2 基于生產(chǎn)線編碼染色體的變異

采用兩點變異法，選取兩點分別修改對應可選擇的生產(chǎn)線編碼，并修改加工時間。具體的過程描述為：首先在父染色體P1上隨機地選取兩個變異點；在子染色體上將這兩個基因位上的生產(chǎn)線編碼改為其他可選的生產(chǎn)線；將父染色體P1中除了兩個變異點之外的基因值遺傳到子代S6中，基因值和位置順序均保持不變，最后得到新的子染色體S6。

3.6 選擇操作

選擇策略是算法對群體進行“優(yōu)勢選拔”的操作，目的是將群體中具有競爭優(yōu)勢的優(yōu)質(zhì)個體遺傳到下一代。采用精英保留機制，具體過程為：首先，計算父代種群以及經(jīng)過交叉和變異操作以后后生成的新種群中每一個個體的適應度值，然后選出適應度值最高的P個個體形成子代種群。

4 基于分批的多品種柔性生產(chǎn)調(diào)度

通過將模擬退火算法和遺傳算法相結合，得出多品種柔性生產(chǎn)線上的批量調(diào)度優(yōu)化方案，具體流程圖如圖3所示。

圖3 多品種柔性生產(chǎn)批量調(diào)度流程圖

5 實驗驗證

5.1 實驗環(huán)境及參數(shù)設置

采取2.1節(jié)給出的柔性生產(chǎn)線模型，其中每種產(chǎn)品與每條生產(chǎn)線的對應關系以及每種產(chǎn)品的完成每個流程段上的加工時間如表3所示。

表3 產(chǎn)品與生產(chǎn)線對應關系及生產(chǎn)用時

模擬退火算法的迭代次數(shù)選取所有可能的分批方案的50%，遺傳算法的迭代次數(shù)為GEN=50，種群規(guī)模為50，交叉概率為0.9，變異概率為0.1，使用MATLAB搭建了實驗環(huán)境，進行了仿真實驗。

5.2 每種產(chǎn)品生產(chǎn)需求總量相同時的分批調(diào)度方案

首先針對每種產(chǎn)品的生產(chǎn)總量相同時的批量調(diào)度情況進行了仿真，在這種情況下，每種產(chǎn)品的子批數(shù)是相等的，每個子批的大小也是相同的，以每種產(chǎn)品的生產(chǎn)總量為10，20和100三種情況為例，分批結果和調(diào)度結果如表4所示。

表4 每種產(chǎn)品生產(chǎn)總量相同時的分批以及生產(chǎn)排產(chǎn)結果

此外，以每種產(chǎn)品的總量都是20為例，對所有可能的分批方案的生產(chǎn)用時進行了曲線繪制，如圖4所示。

圖4 每種產(chǎn)品生產(chǎn)總量為20時最短完工時間與分批子批數(shù)的關系

該圖橫軸表示每種產(chǎn)品的子批數(shù)量，縱軸表示完成所有訂單生產(chǎn)任務的總用時。當子批數(shù)為1時，表示整批生產(chǎn)的情況，即不進行批量劃分，但是由于生產(chǎn)總量比較大，需要等待一整批在一個工藝流程段完成生產(chǎn)以后才能開始下一個工藝流程，會造成比較長的等待時間，從而得出的生產(chǎn)用時較其他分批情況要長；隨著子批的增多，生產(chǎn)用時逐漸縮短，但是減小的速度逐漸變小，當子批數(shù)為20時，表示每種產(chǎn)品的每個工件都作為一個子批進行生產(chǎn)，在不考慮中間操作環(huán)節(jié)所需要的時間消耗的情況下，可以有效縮短生產(chǎn)線等待的時間，因此所需要的時間最小。但是實際操作中子批劃分過小會造成中間操作增多，因此選取比較合理的中間值作為實際生產(chǎn)的最優(yōu)分批方案來進行批量調(diào)度比較合理。值得注意的是，所選擇的方案相比整批方案，所需的完工時間呈現(xiàn)大幅度的降低，并且與單個產(chǎn)品作為一個子批的情況相比，所需的完工時間相差不大。

5.3 每種產(chǎn)品生產(chǎn)需求總量不同時的分批調(diào)度方案以及生產(chǎn)排產(chǎn)甘特圖

為了更加符合實際的生產(chǎn)情況，進一步仿真了每種產(chǎn)品的需求生產(chǎn)總量不同時的分批以及生產(chǎn)調(diào)度結果，如表5所示。

表5 每種產(chǎn)品生產(chǎn)總量不同時的分批和生產(chǎn)排產(chǎn)結果

根據(jù)上表可知當生產(chǎn)總量Xi比較小的時候，子批數(shù)量Qi也比較小，隨著Xi的增加，Qi也相應增加，但是子批的批量Pi與總量Xi的大小相關性不大。

以表5中第一行為例，圖5給出了最終的生產(chǎn)排產(chǎn)甘特圖，橫軸表示生產(chǎn)用時，縱軸代表生產(chǎn)線編號，矩形條表示產(chǎn)品i的第j個子批在每個工藝段所選擇的生產(chǎn)線上的生產(chǎn)用時，總的生產(chǎn)用時為186。可以看出每種產(chǎn)品的每一個子批的加工順序都符合2.1節(jié)給出的工藝流程，加工時間和生產(chǎn)線選擇符合表3的前提條件。

圖5 生產(chǎn)排產(chǎn)甘特圖

6 結語

采用模擬退火算法與遺傳算法相結合的方法解決了多品種柔性批量作業(yè)的分批調(diào)度問題，得出了子批與批量柔性分批及工藝流程與生產(chǎn)線優(yōu)化調(diào)度策略，進而可以在給定訂單生產(chǎn)總任務量的情況下得到最優(yōu)的柔性分批以及批量調(diào)度的生產(chǎn)排產(chǎn)方案，并且針對每種產(chǎn)品的子批數(shù)和批量大小對生產(chǎn)效率的影響進行了實驗仿真與分析，實驗結果表明了所提方案的有效性和可行性。

后續(xù)研究需增加約束條件比如訂單優(yōu)先級和緩存區(qū)限制等，使研究方案更加符合工廠的實際生產(chǎn)，尋求合理的方法解決實際的多目標優(yōu)化問題。