面向智能工業(yè)的柔性裝配批量調(diào)度優(yōu)化策略

高 勃，孫嘉玉，李學(xué)漢，趙宏軍，王 穎

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

0 引言

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

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

1.1 問(wèn)題描述

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

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

圖1 芯體某線示意圖

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

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

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

1.2 數(shù)學(xué)模型

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

表2 變量定義表

表2 （續(xù)）

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

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

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

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

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

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

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

3.1 編碼方法

結(jié)合批量柔性生產(chǎn)的特點(diǎn)，采用基于批量的染色體和基于子批的染色體相結(jié)合的編碼方式。基于批量的染色體用于給出每種產(chǎn)品采用的子批劃分方式，子批數(shù)以及各個(gè)子批的批量大小。

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

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

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

3.2 解碼方法

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

3.3 適應(yīng)度函數(shù)

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

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

3.4 交叉操作

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

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

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

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

3.5 變異操作

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

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

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

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

3.6 選擇操作

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

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

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

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

5 實(shí)驗(yàn)驗(yàn)證

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

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

表3 產(chǎn)品與生產(chǎn)線對(duì)應(yīng)關(guān)系及生產(chǎn)用時(shí)

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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

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