林 煊，陳慶新，毛 寧

(廣東工業(yè)大學(xué) 廣東省計(jì)算機(jī)集成制造重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510006)

0 引言

隨著人們生活水平的逐步提高，個(gè)性化需求越來越旺盛，家具行業(yè)也開始朝著個(gè)性化和定制化的方向發(fā)展。與傳統(tǒng)家具相比，定制家具板材的材料和規(guī)格多種多樣，生產(chǎn)成本較高。因此，為節(jié)省原材料成本,定制家具生產(chǎn)商通常將多個(gè)客戶的訂單整合到一起統(tǒng)一下料，以最大限度地提高板材利用率。板材加工完成后，再將每位客戶的家具板材從中分揀出來進(jìn)行打包發(fā)貨。上述過程雖然節(jié)省了原材料成本，但也造成后續(xù)分揀作業(yè)成本的上升。在此背景下，具有低錯(cuò)誤率以及高效率的自動(dòng)化分揀方式開始逐漸取代傳統(tǒng)的手工分揀模式。

目前，分揀系統(tǒng)已廣泛應(yīng)用于醫(yī)藥、煙草、快遞等行業(yè)的物流配送環(huán)節(jié)，而關(guān)于分揀系統(tǒng)問題的研究也越來越引起學(xué)者的重視。文獻(xiàn)[1]以人工揀選系統(tǒng)為背景，考慮分揀貨品重量對(duì)分揀順序的影響，研究了一類具有出庫優(yōu)先順序約束的訂單排序問題，提出一種求解該問題的精確算法;文獻(xiàn)[2]針對(duì)自動(dòng)化立體倉庫出入庫調(diào)度問題，引入Petri網(wǎng)方法對(duì)問題進(jìn)行建模，并以系統(tǒng)總體效益最優(yōu)為目標(biāo)，提出一種基于遺傳算法的調(diào)度規(guī)則決策方法，解決自動(dòng)化立體倉庫的出入庫調(diào)度規(guī)則優(yōu)化的多約束性、多目標(biāo)問題;文獻(xiàn)[3]以雙揀選區(qū)自動(dòng)揀選系統(tǒng)為背景，提出一種虛擬視窗算法，通過提前訂單開始分揀時(shí)間，以壓縮貨物之間的距離，從而節(jié)約分揀時(shí)長(zhǎng);文獻(xiàn)[4-5]在文獻(xiàn)[3]所提出的壓縮合流分揀策略的基礎(chǔ)上，研究了品項(xiàng)分配優(yōu)化問題，提出一種啟發(fā)式聚類算法進(jìn)行求解?，F(xiàn)有關(guān)于分揀系統(tǒng)調(diào)度策略的研究大多集中在人工揀選系統(tǒng)和自動(dòng)倉儲(chǔ)系統(tǒng)，在少部分關(guān)于自動(dòng)分揀系統(tǒng)優(yōu)化方法的研究中，主要圍繞在品項(xiàng)分配問題，而鮮有關(guān)于自動(dòng)分揀系統(tǒng)出入庫調(diào)度策略的研究。因此，本文研究不僅填補(bǔ)了目前定制家具自動(dòng)分揀系統(tǒng)出入庫調(diào)度問題研究的空白，也豐富了現(xiàn)有自動(dòng)分揀系統(tǒng)分揀調(diào)度策略的研究。

定制家具分揀作業(yè)可細(xì)分為條碼識(shí)別、尺寸檢測(cè)、入庫暫存、出庫4項(xiàng)作業(yè)。分揀出庫的板件經(jīng)由移載機(jī)合流以及線體運(yùn)輸，到達(dá)后方的打包機(jī)進(jìn)行打包處理，出庫作業(yè)的高效性和準(zhǔn)確性將直接影響包裝作業(yè)的開展。因此，本文研究對(duì)于提升板式家具自動(dòng)分揀中出庫及包裝作業(yè)的整體效率具有重要的應(yīng)用意義。

本文研究的自動(dòng)分揀系統(tǒng)出庫打包問題可抽象為一種帶裝配操作的三階段混合流水車間問題。其中：第一階段機(jī)械手出庫和第二階段移載機(jī)合流可表示為機(jī)器加工處理階段；第三階段打包機(jī)的打包作業(yè)類似裝配作業(yè)將多塊板件組裝成一個(gè)包件。針對(duì)此類調(diào)度問題，已有部分學(xué)者進(jìn)行了相關(guān)研究。文獻(xiàn)[6]考慮每個(gè)階段有多臺(tái)同等并行機(jī)，將兩機(jī)裝配流水車間拓展為兩階段混流裝配問題;文獻(xiàn)[7]考慮工件的運(yùn)輸階段，將兩階段的裝配流水車間調(diào)度問題拓展為三階段裝配流水車間調(diào)度問題，在證明問題為NP難問題的同時(shí)，分析了問題的下界。多階段裝配車間調(diào)動(dòng)問題是NP難題，在合理的時(shí)間內(nèi)難以求得問題的最優(yōu)解，因此能夠快速求解問題近似解的啟發(fā)式算法，目前正成為該領(lǐng)域研究的熱點(diǎn)。對(duì)于兩階段問題，文獻(xiàn)[8]以最小化最大完工時(shí)間和平均完工時(shí)間的加權(quán)和為優(yōu)化目標(biāo)，構(gòu)造了模擬退火(Simulated Annealing, SA)算法、禁忌搜索(Taboo Search, TS)算法和蟻群優(yōu)化(Ant Colony Optmization, ACO)算法3種有效求解該類問題的元啟發(fā)式算法;文獻(xiàn)[9]考慮與文獻(xiàn)[8]相同的模型，提出一種融合變鄰域搜索機(jī)制的離散粒子群優(yōu)化(Discrete Particle Swarm Optimization, DPSO)算法，并實(shí)驗(yàn)證明了所提算法相較于SA算法和TS算法的優(yōu)越性。對(duì)于三階段問題，文獻(xiàn)[10]以最小化最大完工時(shí)間和平均完工時(shí)間的加權(quán)和為目標(biāo)，提出一種SA求解算法;此后，文獻(xiàn)[11]在文獻(xiàn)[10]所研究問題的基礎(chǔ)上，又提出一種變鄰域搜索(Variable Neighborhood Search, VNS)算法，實(shí)驗(yàn)表明，VNS算法的表現(xiàn)優(yōu)于文獻(xiàn)所提的SA算法，而SA算法在時(shí)間耗費(fèi)上更有優(yōu)勢(shì);文獻(xiàn)[12]總結(jié)了目前有效求解三階段裝配車間調(diào)度問題的元啟發(fā)式算法，通過融合變鄰域搜索機(jī)制，提出了混合遺傳算法(Hybrid Genetic Algorithm, HGA)、混合分布估計(jì)算法(Hybrid Estimation of Distribution Algorithms, HEDA)和混合差分進(jìn)化算法(Hybrid Discrete Differential Evolution, HDDE)?，F(xiàn)有關(guān)于啟發(fā)式算法的研究主要集中在迭代尋優(yōu)的元啟發(fā)式算法，而本文針對(duì)出庫打包調(diào)度問題的特殊性，將設(shè)計(jì)一種更為高效的構(gòu)造類啟發(fā)式算法。

不同于一般的多階段裝配流水車間問題，本文研究的出庫打包調(diào)度問題中，板件除了在第一階段有確定的處理機(jī)器外，還具有確定的先后包裝順序以及一定的運(yùn)輸時(shí)間。為了避免板件經(jīng)由線體輸送以及移載機(jī)合流后，到達(dá)打包機(jī)的順序出錯(cuò)，從而影響包裝作業(yè)的開展，應(yīng)當(dāng)控制同一個(gè)包裝任務(wù)內(nèi)的板件在第一階段機(jī)器上的處理順序。因此，第一階段可表示為工件加工具有優(yōu)先順序約束以及工件加工具有指定機(jī)器的并行機(jī)調(diào)度問題。目前，針對(duì)此類問題的研究成果并不多，文獻(xiàn)[13]研究了工件在第一階段加工具有指定機(jī)器且第二階段只有一臺(tái)機(jī)器的兩階段流水車間問題，并證明了該問題為NP難問題;文獻(xiàn)[14]證明了工序之間具有任意加工優(yōu)先順序約束，且工序所指派加工機(jī)器確定的兩臺(tái)平行機(jī)調(diào)度問題是NP難問題;文獻(xiàn)[15]在文獻(xiàn)[14]的基礎(chǔ)上，考慮實(shí)際加工環(huán)境，研究了一種以最小化最大完工時(shí)間為目標(biāo)，工件具有單位加工時(shí)間且工件加工具有鏈狀優(yōu)先順序約束以及指定機(jī)器約束的兩臺(tái)并行機(jī)調(diào)度問題(U2-Chain問題)，并給出求解該問題的近似算法。

本文研究的定制家具出庫打包調(diào)度問題是上述相關(guān)文獻(xiàn)研究問題的結(jié)合和推廣，創(chuàng)新點(diǎn)主要體現(xiàn)在以下3個(gè)方面：①在現(xiàn)有關(guān)于帶裝配操作的流水車間問題的研究中，對(duì)于加工階段和裝配階段均有多臺(tái)并行機(jī)組成的復(fù)雜系統(tǒng)的研究相對(duì)較少，本文研究的三階段調(diào)度問題中每個(gè)階段均有多臺(tái)并行機(jī)；②本文不僅考慮了板件在工序間轉(zhuǎn)移的運(yùn)輸時(shí)間，還考慮了板件運(yùn)輸時(shí)間對(duì)控制板件到達(dá)打包機(jī)先后順序的影響；③大多數(shù)研究均是以最小化最大完工時(shí)間為優(yōu)化目標(biāo)，但是在實(shí)際加工環(huán)境中，考慮單個(gè)目標(biāo)并不能保證系統(tǒng)整體性能的優(yōu)化。本文在考慮盡可能短的時(shí)間內(nèi)完成所有包裝任務(wù)的同時(shí)，為減少板件在第一階段貨架的存儲(chǔ)時(shí)長(zhǎng)以及板件在包裝工位等待的平均時(shí)長(zhǎng)，以最大包裝完工時(shí)間、最大出庫完工時(shí)間以及板件在包裝工位的總等待時(shí)間三者的和最小化作為問題的優(yōu)化目標(biāo)。

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

1.1 問題描述

定制家具自動(dòng)分揀系統(tǒng)的出庫打包調(diào)度問題可抽象為一類三階段流水作業(yè)排序問題，其中每階段均由多臺(tái)同等并行機(jī)構(gòu)成。其與傳統(tǒng)的混合裝配流水車間調(diào)度問題之間主要存在以下3點(diǎn)差異：①在現(xiàn)有的裝配流水車間問題研究中，很少考慮裝配任務(wù)內(nèi)工件的優(yōu)先順序約束，而在定制家具的包裝環(huán)節(jié)中，根據(jù)已知的包內(nèi)板件堆疊次序要求，包內(nèi)板件的包裝處理次序存在確定的優(yōu)先約束關(guān)系，板件在出庫后經(jīng)由線體輸送和合流移載機(jī)合流后的順序需要滿足此優(yōu)先約束；②在實(shí)際的自動(dòng)分揀系統(tǒng)布局中，處于不同分揀單元的分揀機(jī)與第二階段合流移載機(jī)之間的運(yùn)輸距離可能存在差異，相較于少數(shù)考慮運(yùn)輸時(shí)間影響的裝配車間問題，本文還考慮了距離的差異對(duì)合流順序的影響；③傳統(tǒng)的裝配車間問題中每個(gè)裝配任務(wù)的工件數(shù)相同，每個(gè)工件有指定的唯一加工機(jī)器，加工機(jī)器數(shù)量等于每個(gè)裝配任務(wù)的工件數(shù)，而在出庫打包問題中，每個(gè)包裝任務(wù)的板件數(shù)量不盡相同，包內(nèi)板件可暫存在任意分揀單元內(nèi)，一臺(tái)分揀機(jī)可能兼顧一個(gè)包裝任務(wù)內(nèi)多塊板件的出庫作業(yè)。

問題可簡(jiǎn)述為：假設(shè)有n個(gè)包裝任務(wù)，每個(gè)任務(wù)Ji有Qi塊板件，每塊板件均需要先后經(jīng)過出庫A、移載B、包裝C三道工序的處理，其中工序A只可以由板件所在分揀單元E內(nèi)的唯一一臺(tái)機(jī)械手處理，工序B可以在第二階段任意一臺(tái)機(jī)器進(jìn)行處理，同一個(gè)包裝任務(wù)的工序C需要在第三階段任意相同的打包機(jī)上處理。板件在每道工序間處理需要經(jīng)過線體轉(zhuǎn)運(yùn)，板件從工序A不同機(jī)器出發(fā)到達(dá)工序B機(jī)器所耗費(fèi)的運(yùn)輸時(shí)間TA不同，而從工序B出發(fā)到達(dá)工序C機(jī)器的運(yùn)輸時(shí)間TB均相同。在第一階段，因?yàn)榘寮鎯?chǔ)的分揀單元確定已知，所以有確定的處理機(jī)器。在第三階段，同一個(gè)任務(wù)內(nèi)的板件處理具有一定的先后順序約束，板件在經(jīng)由線體運(yùn)輸?shù)竭_(dá)包裝工位的順序必須滿足此順序約束，且只有當(dāng)一個(gè)任務(wù)處理完畢才能處理下一個(gè)任務(wù)；一臺(tái)機(jī)器在同一時(shí)間只能處理一塊板件；工序在處理過程中遵循不可搶占原則。目標(biāo)是最小化板件最大包裝完工時(shí)間、最大出庫完工時(shí)間以及總等待時(shí)間三者的總和。

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

首先針對(duì)問題進(jìn)行數(shù)學(xué)模型構(gòu)建，模型決策變量描述如下：

Sik為板件i在第k階段機(jī)器上的開工時(shí)間；

目標(biāo)函數(shù)：

minf=α1×max(Ci3)+α2×max(Ci1)+

(1)

s.t.

?i=1,2,…,n，?k=1,2,3；

(2)

(3)

(4)

?j=1,2,…,n，?k=1,2,3；

(5)

?j=1,2,…,n，?k=1,2,3，?m=1,2,…,mk;

(6)

?k=1,2,3，?m=1,2,…,mk；

(7)

(8)

Ximk=Xjmk，?k=3，?m=1,2,…,mk，

?Oij=1；

(9)

?i=1,2,…,n，?j=1,2,…,n，?k=3；

(10)

?i=1,2,…,n，?j=1,2,…,n，?k=1,2,3；

(11)

Rik=Cik-1+Tk-1,k，?i=1,2,…,n，?k=2,3;

(12)

Sik≥Rik，?i=1,2,…,n，?k=1,2,3；

(13)

Cik=Sik+Pik，?i=1,2,…,n，?k=1,2,3。

(14)

其中：

i,j為板件編號(hào)；

n為板件總數(shù)；

k為處理階段數(shù)；

α1，α2，1-α1-α2分別表示出庫完工時(shí)間、包裝完工時(shí)間和板件在包裝工位等待時(shí)間在目標(biāo)函數(shù)中所占權(quán)重；

Cik為k階段板件i的完工時(shí)間；

Sik為k階段板件i的開工時(shí)間；

Pik為k階段板件i的處理時(shí)間；

Ximk表示k階段板件i是否被指派到機(jī)器m上加工，如果是，則Ximk=1，否則Ximk=0；

mk為k階段機(jī)器數(shù)量；

Uijmk表示k階段的機(jī)器m上，板件j是否緊跟在板件i之后處理，如果是，則Uijmk=1，否則Uijmk=0；

Tkk′為k階段到k′階段的線體運(yùn)輸時(shí)間；

Rik為k階段板件i的到達(dá)時(shí)間；

Oij表示板件i、j是否在同一個(gè)包件，且板件j緊跟在板件i之后處理，如果是，則Oij=1，否則Oij=0；

L為一個(gè)非常大的正數(shù)。

其中：式(2)表示在各階段板件與自身不存在緊前緊后關(guān)系；式(3)和式(4)表示在各階段板件最多先于或緊跟在另一塊板件之后處理；式(5)表示在各階段板件i與板件j之間僅存在唯一的緊前緊后關(guān)系；式(6)表示在各階段如果板件被指派到某臺(tái)機(jī)器上處理，則在這臺(tái)機(jī)器上一定存在關(guān)于該塊板件的緊前緊后關(guān)系；式(7)表示各階段各臺(tái)機(jī)器一次只能處理一塊板件；式(8)表示各階段板件只可以被指派到一臺(tái)機(jī)器上處理；式(9)表示在第三階段同一個(gè)包裝任務(wù)的板件必須在同一臺(tái)機(jī)器上處理；式(10)表示在第三階段同一個(gè)包裝任務(wù)的板件需要按照指定順序處理；式(11)表示各階段機(jī)器只有處理完一塊板件后才能處理下一塊；式(12)表示板件到達(dá)各階段機(jī)器的時(shí)間等于其在上一階段機(jī)器的完工時(shí)間加上運(yùn)輸時(shí)間，需要注意的是第一階段到第二階段的運(yùn)輸時(shí)間因第一階段板件處理的機(jī)器不同而異；式(13)表示各階段板件的開工時(shí)間不能早于其到達(dá)時(shí)間；式(14)表示各階段板件的完工時(shí)間等于其開工時(shí)間加上處理時(shí)間。

2 啟發(fā)式算法

對(duì)于NP難的排序調(diào)度問題，隨著問題規(guī)模的增大，精確算法的計(jì)算負(fù)擔(dān)呈指數(shù)級(jí)增長(zhǎng)，不適用于求解工程問題。因此，可在合理時(shí)間內(nèi)得到高質(zhì)量解的啟發(fā)式算法是目前研究的重點(diǎn)，主要集中在優(yōu)先規(guī)則、分解算法以及元啟發(fā)式方法。其中優(yōu)先規(guī)則由于計(jì)算效率高且易于使用，在實(shí)際問題中應(yīng)用最為廣泛，但也具有短視的缺點(diǎn)，長(zhǎng)期表現(xiàn)不佳；元啟發(fā)式算法是獨(dú)立于問題的技術(shù)，可以應(yīng)用在非常廣泛的問題上，但不能保證效率，求解效率相較于優(yōu)先規(guī)則耗費(fèi)明顯；分解算法兼具上述兩類算法的特點(diǎn)，在求解效率及求解效果上均有不錯(cuò)的保證。由于定制家具自動(dòng)分揀系統(tǒng)對(duì)調(diào)度算法的實(shí)時(shí)性要求較高，基于出庫打包調(diào)度問題，構(gòu)造一種兼顧性能和效率的高效啟發(fā)式算法是本文算法設(shè)計(jì)的重點(diǎn)和難點(diǎn)。

針對(duì)出庫打包調(diào)度問題，本文構(gòu)造一種啟發(fā)式算法。關(guān)于多階段流水車間調(diào)度問題的研究，文獻(xiàn)[16-17]提出一種分階段求解具有多階段流水車間調(diào)度問題的思路;文獻(xiàn)[18]針對(duì)帶裝配操作的三階段混合流水車間調(diào)度問題，提出將問題分解為兩個(gè)子問題求解，先確定裝配階段成品的裝配順序，再確定成品內(nèi)各工件在加工階段的加工順序。本文基于上述思想，構(gòu)建求解出庫打包調(diào)度問題的近似算法。首先將復(fù)雜的出庫打包調(diào)度問題按階段分解為3個(gè)子問題：①確定板件在第三階段機(jī)器的加工順序(問題Ⅰ);②確定板件在第一階段機(jī)器的開工時(shí)間(問題Ⅱ);③確定板件在第二階段機(jī)器的開工時(shí)間(問題Ⅲ)。針對(duì)問題Ⅰ，采用最長(zhǎng)加工時(shí)間優(yōu)先規(guī)則(Longest Process Time，LPT)確定第一階段各臺(tái)機(jī)器Mi的加工序列Si；針對(duì)問題Ⅱ，將Si作為初始序列，通過改進(jìn)的轉(zhuǎn)移瓶頸算法(Modified Shifting Bottleneck Heuristic, MSBH)確定板件在第一階段機(jī)器的開工時(shí)間Si；針對(duì)問題Ⅲ，根據(jù)問題Ⅱ確定的板件開工時(shí)間Si，計(jì)算得到板件序列Q1，通過算法FAM(first available machine)將Q1的板件安排到第二階段的平行機(jī)上。由此得到求解出庫打包調(diào)度問題的近似算法H*，下面詳細(xì)介紹所分解的3個(gè)子問題以及相應(yīng)的求解算法。

2.1 確定第三階段各打包機(jī)板件處理順序

此階段問題可抽象為以最小化最大完工時(shí)間為優(yōu)化目標(biāo)的并行機(jī)調(diào)度問題，以三元組法表示為Pm||Cmax。對(duì)于求解Pm||Cmax問題的啟發(fā)式算法很多，其中最常用的是啟發(fā)式規(guī)則列表調(diào)度(List Scheduling，LS)算法以及LPT，本文擬采用LPT規(guī)則求解問題Ⅰ，算法步驟如下：

步驟1計(jì)算每個(gè)包裝任務(wù)的板件總處理時(shí)間ti，將任務(wù)按處理時(shí)間ti遞減排序，得包裝任務(wù)序列bq。

步驟2在每個(gè)任務(wù)內(nèi)按照規(guī)定的板件處理順序?qū)Π寮M(jìn)行排列，得到更新后序列bq′。

步驟3每次從序列bq′中取第一個(gè)任務(wù)bq1，安排到當(dāng)前總加工時(shí)長(zhǎng)Sm最小的打包機(jī)m上，更新m的總加工時(shí)長(zhǎng)Sm=Sm+Pbq1，更新m的包裝序列Sm=Sm+bq1，更新序列bq′=bq′-bq1。如果bq′為空，得到各打包機(jī)板件包裝序列Sm；否則，繼續(xù)步驟3。

2.2 確定第一階段板件出庫開始時(shí)間

問題Ⅱ求解的關(guān)鍵在于考慮板件在各階段機(jī)器的處理時(shí)間和機(jī)器間的運(yùn)輸時(shí)間，進(jìn)而確定第一階段各分揀單元內(nèi)板件的出庫開始時(shí)間，使得板件到達(dá)打包機(jī)的順序符合問題Ⅰ確定的各打包機(jī)板件處理序列Sm。

通過前文分析，該類問題可抽象為工件加工具有鏈狀優(yōu)先約束且工件加工具有指定機(jī)器的并行機(jī)調(diào)度問題。參考文獻(xiàn)[15]的求解思路，將子問題Ⅰ求得的板件序列Sm視為作業(yè)車間調(diào)度問題的加工任務(wù)Tm，板件序列的每一個(gè)板件Jk(Jk∈Sm)等同于加工任務(wù)Tm的每一道工序Ok(Ok∈Tm),加工工序Ok的機(jī)器即為板件Jk在第一階段所指派的機(jī)器，因此問題Ⅱ可進(jìn)一步抽象為一種工序具有重入特征的作業(yè)車間問題。對(duì)于作業(yè)車間問題，擬采用文獻(xiàn)[19]所提的轉(zhuǎn)移瓶頸法(Shifting Bottleneck Heuristic, SBH)作為問題Ⅱ的求解算法，算法步驟如下：

步驟1將調(diào)度問題以析取圖表示。

步驟2將機(jī)器集合表示為M，將已完成調(diào)度的機(jī)器集合M0置空。

步驟3選擇瓶頸機(jī)器，mp∈M-M0。

步驟4針對(duì)瓶頸機(jī)器mp，調(diào)用單機(jī)問題求解算法確定此臺(tái)瓶頸機(jī)器上工序的加工順序，在析取圖上將方向錯(cuò)誤的虛弧刪除，將此臺(tái)機(jī)器加入已調(diào)度的機(jī)器集合M0中。

步驟5當(dāng)集合M0=M表示所有機(jī)器完成調(diào)度，算法停止，否則，轉(zhuǎn)步驟3。

MSBH算法求解作業(yè)車間調(diào)度問題主要考慮3個(gè)關(guān)鍵點(diǎn)：①確定問題的析取圖表示方式，即上述過程的步驟1；②確定單機(jī)問題的求解順序，即上述過程的步驟3，文獻(xiàn)[20]通過實(shí)驗(yàn)驗(yàn)證了TML(total machine load)規(guī)則用于確定瓶頸機(jī)器的優(yōu)越性，因此本文選擇總處理時(shí)間最大的機(jī)器作為瓶頸機(jī)器；③確定單機(jī)問題的求解算法，即步驟4確定瓶頸機(jī)器上工序的加工順序。下面分別對(duì)步驟1的表示方法和步驟4的求解方法進(jìn)行說明。

2.2.1 確定析取圖表示方式

假設(shè)經(jīng)過LPT規(guī)則算法確定了第三階段3臺(tái)打包機(jī)的板件包裝序列，分別為：{1，2，3}、{4，5，6}、{7，8，9}，其中{1，5，7}、{2，4，6，8}、{3，9}分別存儲(chǔ)在同一分揀單元，每個(gè)包裝序列可抽象表示成車間調(diào)度問題中的一個(gè)工件，每塊板件為工件中的一道工序。析取圖如圖1所示，每一點(diǎn)表示一道工序，圖中最長(zhǎng)路徑表示調(diào)度問題的最大完工時(shí)間。圖1中實(shí)線弧的方向表示同一個(gè)工件上工序間加工的先后順序，虛線弧的方向表示同一機(jī)器上的工序在此機(jī)器上加工的先后順序。問題的求解就是刪減工序間多余的虛線弧，使得工序間僅存在確定方向的單向虛弧，即確定機(jī)器上工序加工的先后順序，使得析取圖的最長(zhǎng)路徑的距離最小。

為盡可能減少板件在打包機(jī)的等待時(shí)間，根據(jù)相鄰兩道工序所指派的機(jī)器相同與否，確定實(shí)線弧相鄰兩點(diǎn)間的距離為

dij=

(15)

式中：Ti,k,p表示板件i由階段k機(jī)器到階段p的運(yùn)輸時(shí)間;M表示一個(gè)接近0的實(shí)數(shù)。

對(duì)于同一個(gè)工件在同一機(jī)器處理的不相鄰且間隔最短的兩道工序也存在一個(gè)開工時(shí)間的約束關(guān)系，如圖1中點(diǎn)4和點(diǎn)6間的距離和虛線弧相鄰兩點(diǎn)間的距離均可由式(16)確定。

dij=Pi1。

(16)

式中：dij表示點(diǎn)i指向點(diǎn)j的距離,即出庫開始時(shí)間間隔；Pik表示板件i在k階段機(jī)器的處理時(shí)間。

2.2.2 單機(jī)問題求解算法

SBH算法將復(fù)雜的作業(yè)車間調(diào)度問題分解為若干個(gè)以最小化最大拖期時(shí)間為目標(biāo)、工序具有到達(dá)時(shí)間和交貨期時(shí)間的單機(jī)調(diào)度問題進(jìn)行求解，三元組法表示為1||r||Lmax。工序的到達(dá)時(shí)間rn和交貨期時(shí)間dn分別為：

rik=L(0,ik)，

(17)

dik=L(0,n)-L(ik,n)+Pik。

(18)

其中：ik表示工序;L(p,q)表示p、q兩點(diǎn)在析取圖DG上的最長(zhǎng)距離；0、n分別為析取圖初始頂點(diǎn)和終點(diǎn)；Pik為加工時(shí)間。

針對(duì)1||r||Lmax問題，文獻(xiàn)[21]已驗(yàn)證最早交貨期(Earliest Due Date，EDD)優(yōu)先規(guī)則是求解問題的有效算法。本文擬采用基于EDD規(guī)則的最早交貨期松弛(Earliest Due Date Slack, EDDS)算法作為單機(jī)問題的求解算法，算法步驟如下(其中的工序指代本文問題中的板件)：

步驟2計(jì)算各工序的到達(dá)時(shí)間ri，交貨期時(shí)間di。

步驟3判斷集合Ou是否為空，如果是，則執(zhí)行步驟7；否則執(zhí)行步驟4。

步驟7調(diào)度結(jié)束。

2.3 確定板件在第二階段移載機(jī)的開工時(shí)間

此階段問題可表示為以最小化最大完工時(shí)間為優(yōu)化目標(biāo)，工件帶到達(dá)時(shí)間的并行機(jī)調(diào)度問題，三元組法表示為Pm||Ri||Cmax。求解Pm||Ri||Cmax問題的啟發(fā)式算法有很多種，Panwalker等[22]歸納了8個(gè)基本原則，其中研究最多的是列表算法(List Scheduling,LS)。關(guān)于列表算法，Graham[23]提出了FAM和LBM(last busy machine)兩種特殊算法。FAM算法基本思路是：已知一個(gè)工件序列S，每次始終選擇序列S的第一個(gè)未調(diào)度工件到使其能最早開工的機(jī)器上；LBM算法的基本思想則是：每次始終選擇序列S的最后一個(gè)未調(diào)度工件到使其最晚開工的機(jī)器上。本文擬采用FAM算法求解該子問題，算法步驟如下：

步驟1根據(jù)算式Ri,2=Si,1+Pi,1+T1,i,2,計(jì)算板件到達(dá)第二階段機(jī)器的時(shí)間，其中Si,1為子問題Ⅱ確定的板件開始時(shí)間，Pi,1為板件在第一階段的處理時(shí)間，Ti,1,2為板件在兩階段機(jī)器間的運(yùn)輸時(shí)間。

步驟2板件按照Ri,2不減排序，得到序列Q1。

步驟3每次選擇序列Q1的第一個(gè)未調(diào)度板件，安排到使其能最早開工的機(jī)器上，直到序Q1內(nèi)的板件全部排完。

3 算例仿真及結(jié)果分析

3.1 算例設(shè)計(jì)

由于本文研究的問題并非一類經(jīng)典調(diào)度問題，在現(xiàn)有文獻(xiàn)中難以找到針對(duì)本類調(diào)度問題的測(cè)試數(shù)據(jù)集。因此，擬借鑒文獻(xiàn)[24]給出的調(diào)度規(guī)則評(píng)估模擬算例的生成方法產(chǎn)生本文的測(cè)試數(shù)據(jù)集，該方法采用裂區(qū)試驗(yàn)的設(shè)計(jì)方法進(jìn)行仿真實(shí)驗(yàn)。結(jié)合本文問題研究的特點(diǎn)，總結(jié)出問題的主要因素為板件規(guī)模大小S，其中包括包件個(gè)數(shù)g和包內(nèi)板件個(gè)數(shù)n兩個(gè)主要參數(shù)。包件個(gè)數(shù)g有10、30、50三種規(guī)模；包內(nèi)板件數(shù)量n從區(qū)間[1,15]的離散分布均勻產(chǎn)生，即板件規(guī)模有小、中、大3個(gè)水平。此外，包內(nèi)板件分散度D、各階段機(jī)器數(shù)M、目標(biāo)函數(shù)權(quán)值W以及求解問題的調(diào)度算法Al是影響問題求解的關(guān)鍵因素，作為本次裂區(qū)試驗(yàn)的二級(jí)因素。根據(jù)同一個(gè)包內(nèi)板件在分揀單元的分布情況，包內(nèi)板件分散度分為低分散度與高分散度兩個(gè)水平，低分散度表示包內(nèi)板件均位于同一個(gè)分揀單元，高分散度表示包內(nèi)板件按照堆疊順序間隔分布于互不相同的分揀單元。例如有3個(gè)分揀單元，板件1、2、3、4均同屬于一個(gè)包件，按照高離散度分布，板件1、2、3、4將分別存儲(chǔ)于單元1、2、3、1。此外，機(jī)器規(guī)模包含小，中，大3個(gè)規(guī)模，分別為(2,1,4)，(3,2,6)，(5,3,9)，其中數(shù)字分別表示第一、二、三階段機(jī)器數(shù)量，板件在3個(gè)階段機(jī)器的處理時(shí)間t分別從區(qū)間為[9,15]、[1,5]、[2,25]的均勻分布中產(chǎn)生。目標(biāo)函數(shù)權(quán)值共有[0.2,0.7,0.1]、[0.7,0.2,0.1]、[0.4,0.5,0.1]三組，第一、二、三位數(shù)分別表示出庫完工時(shí)間、包裝完工時(shí)間、板件在包裝工位等待時(shí)間在目標(biāo)函數(shù)中的權(quán)重。板件在第一和第二階段，第二和第三階段間的運(yùn)輸時(shí)間分別從區(qū)間[5,15]、[5,10]的均勻分布中隨機(jī)產(chǎn)生。

裂區(qū)試驗(yàn)選取的調(diào)度算法，除了本文所提出的H*調(diào)度算法，基于文獻(xiàn)[25]所提的組合多種簡(jiǎn)單調(diào)度規(guī)則構(gòu)成組合規(guī)則求解調(diào)度問題的思路，結(jié)合目前幾種以最小化最大完工時(shí)間為優(yōu)化目標(biāo)的有效調(diào)度規(guī)則包括加工開始時(shí)間最早優(yōu)先(Earliest Start Time，EST)、LPT、Palmer、Gupta、剩余加工時(shí)間最短優(yōu)先(Most Work Remaining，MWKR)，提出EST-LPT、ECT-LPT、EST-Palmer、EST-Gupata、MWKR-LPT 5種組合啟發(fā)式算法，其中EST規(guī)則解決機(jī)械手出庫調(diào)度問題，LPT規(guī)則解決包裝調(diào)度問題，Palmer、Gupta規(guī)則都是求解經(jīng)典flow-shop問題的有效算法，為適應(yīng)本問題的求解，需要將每個(gè)階段的多臺(tái)機(jī)器虛擬成一臺(tái)機(jī)器。此外，為進(jìn)一步驗(yàn)證所構(gòu)造算法的有效性，重新實(shí)現(xiàn)文獻(xiàn)[9-10，12]所提的有效求解裝配流水車間問題的5種元啟發(fā)式算法作為對(duì)比算法，加入包括變鄰域搜索機(jī)制的HGA、HEDA、HDDE算法和混合離散粒子群算法(Hybrid discrete PSO, HPSO)以及SA算法。為公平比較5種元啟發(fā)式算法的性能，基于文獻(xiàn)[12]的思想，設(shè)置算法的最大CPU運(yùn)行時(shí)間(ρ×nms，n為板件數(shù)，ρ取100、300、500),設(shè)置3種時(shí)長(zhǎng)的終止條件，以比較元啟發(fā)式算法在不同運(yùn)行時(shí)間下的性能，而在與其余啟發(fā)式算法的比較中只取ρ=500，即迭代次數(shù)最大的結(jié)果。至此，試驗(yàn)共包含5個(gè)影響因子，其中問題規(guī)模S為試驗(yàn)唯一的主因素，具有3個(gè)水平；二級(jí)因素共4個(gè)，分別為包內(nèi)板件分散度D，具有2個(gè)水平；機(jī)器規(guī)模M，具有3個(gè)水平；目標(biāo)函數(shù)權(quán)值W，具有3個(gè)水平；求解算法Al，具有13個(gè)水平。最后，為了進(jìn)行更為全面的分析，實(shí)驗(yàn)將重復(fù)10次，即每種因素水平組合的問題將重復(fù)10次。因此，本次試驗(yàn)共需求解7 020個(gè)問題實(shí)例。

3.2 仿真結(jié)果及分析

所有問題的求解算法已在MATLAB 2016b仿真軟件編程實(shí)現(xiàn)，并在中央處理器為Intel Corei32.42 GHZ，內(nèi)存4 GB的計(jì)算機(jī)上進(jìn)行仿真試驗(yàn)。為了比對(duì)H*算法與最優(yōu)解間的偏差，采用IBM公司的數(shù)學(xué)規(guī)劃優(yōu)化軟件CPLEX對(duì)數(shù)學(xué)模型進(jìn)行求解。由于CPLEX內(nèi)置的分支定界算法在大規(guī)模問題上求解耗時(shí)過長(zhǎng)，只選擇7 020個(gè)算例中機(jī)器規(guī)模為(2,1,4)，板件個(gè)數(shù)在20～30塊的小規(guī)模算例進(jìn)行對(duì)比。如表1所示為各板件數(shù)下啟發(fā)式算法與精確算法求得結(jié)果的平均值比對(duì)，ARPD表示近似解與最優(yōu)解的相對(duì)偏差百分比RPD的平均值。結(jié)果顯示，H*算法的ARPD均在3%以下。

表1 小規(guī)模算例求解結(jié)果與最優(yōu)解偏差

試驗(yàn)設(shè)計(jì)采用IBM公司的SPSS統(tǒng)計(jì)軟件，首先對(duì)所有調(diào)度算法求得的7 020個(gè)問題實(shí)例的結(jié)果進(jìn)行正態(tài)性檢驗(yàn)，在驗(yàn)證數(shù)據(jù)滿足正態(tài)分布后，采用變異系數(shù)分析方法(ANalysis of VAriance, ANOVA)對(duì)結(jié)果進(jìn)行顯著性分析。限于篇幅，省略ANOVA分析的詳細(xì)結(jié)果。結(jié)果顯示，主因素以及所有二級(jí)因素在顯著水平5%上P值均小于0.000 1，達(dá)到極顯著標(biāo)準(zhǔn)。為了分析不同算法的性能差異，選擇包含算法因素Al在內(nèi)的最高階交互作用顯著的因素進(jìn)行進(jìn)一步的簡(jiǎn)單效應(yīng)分析。結(jié)果顯示，算法、板件數(shù)、分散度的三因素交互效應(yīng)(Al×S×D)以及算法、機(jī)器規(guī)模、分散度的三因素交互效應(yīng)(Al×M×D)最為顯著。

表2所示為不同板件規(guī)模以及分散度下算法的兩兩比較，表3所示為不同板件規(guī)模以及機(jī)器規(guī)模下算法的兩兩比較。限于篇幅，只列出其他算法與H*算法的比較，為方便表示，小于0.001的P值以0值取代，并將P值小于0.05的結(jié)果，即差異顯著的結(jié)果標(biāo)注為“*”。從表2中可以看出，在與簡(jiǎn)單組合規(guī)則的比較中，小規(guī)模高分散度下H*算法的表現(xiàn)與EST-LPT、EST-Palmer、MWKR-LPT三種調(diào)度規(guī)則的差異不顯著，在其余板件規(guī)模以及分散度下，H*算法的表現(xiàn)要顯著優(yōu)于其余7種組合規(guī)則算法。在與元啟發(fā)式算法的比較中，小規(guī)模任意分散度下H*算法的表現(xiàn)與5種元啟發(fā)式算法差異不顯著;中等規(guī)模低分散度下H*算法的表現(xiàn)顯著劣于SA算法，與其余4種元啟發(fā)式算法差異不顯著;中等規(guī)模高分散度下H*算法的表現(xiàn)與SA算法差異不顯著，而顯著優(yōu)于其余4種元啟發(fā)式算法;大規(guī)模低分散度下H*算法的表現(xiàn)顯著劣于SA算法，顯著優(yōu)于HGA和HDE算法，與HPSO和HEDA算法差異不顯著;高分散度下H*算法的表現(xiàn)與SA算法差異不顯著，而顯著優(yōu)于其余算法。由表3可以看出，在與簡(jiǎn)單組合規(guī)則的比較中，任意機(jī)器規(guī)模以及分散度下H*算法表現(xiàn)顯著優(yōu)于所有組合規(guī)則算法。在與元啟發(fā)式算法的比較中，小、中等機(jī)器規(guī)模低分散度下H*算法表現(xiàn)顯著差于SA算法，與其余元啟發(fā)式算法差異不顯著;大機(jī)器規(guī)模低分散度下與所有元啟發(fā)式算法差異不顯著;任意機(jī)器規(guī)模高分散度下H*算法表現(xiàn)與SA算法差異不顯著，而顯著優(yōu)于其余元啟發(fā)式算法。

表2 Al×S×D簡(jiǎn)單效應(yīng)分析結(jié)果

表3 Al×M×D簡(jiǎn)單效應(yīng)分析結(jié)果

為直觀比較算法間的偏差，以每個(gè)實(shí)例下不同算法所求得的最佳解作為實(shí)例的最優(yōu)值，計(jì)算7 020個(gè)實(shí)例下的RPD值，根據(jù)Al×S×D、Al×M×D的維度匯總計(jì)算平均相對(duì)偏差百分比ARPD。結(jié)果如圖2和圖3所示。在任意板件規(guī)模和機(jī)器規(guī)模的低分散度下，組合規(guī)則的平均偏差A(yù)RPD遠(yuǎn)高于元啟發(fā)式算法和H*算法。而在高分散度下，隨著板件規(guī)模的增大和機(jī)器規(guī)模的減小，組合規(guī)則的偏差甚至低于除SA算法之外的元啟發(fā)式算法。在所有參數(shù)組合下H*算法的ARPD均遠(yuǎn)小于組合規(guī)則算法，接近元啟發(fā)式算法的平均偏差，甚至低于除SA算法之外的其余元啟發(fā)式算法的平均偏差，在低分散度下與求解效果最好的SA算法偏差在7%左右。而在高分散度下，隨著問題規(guī)模的增大，H*算法的ARPD趨近于0。

為進(jìn)一步驗(yàn)證算法在求解不同規(guī)模問題上的有效性，從時(shí)間耗費(fèi)上進(jìn)行調(diào)度算法的比較。表4給出了每個(gè)調(diào)度規(guī)則在不同規(guī)模板件數(shù)量和機(jī)器數(shù)量下的中央處理器平均運(yùn)行時(shí)間。結(jié)果顯示，所有調(diào)度規(guī)則的CPU運(yùn)行時(shí)間均隨著板件數(shù)規(guī)模的增大而上升，其中H*調(diào)度算法比其他組合規(guī)則算法運(yùn)行時(shí)間長(zhǎng)，但都是在可接受的范圍內(nèi)。此外，從表4中還可以發(fā)現(xiàn)，隨著機(jī)器規(guī)模的增大，所有算法的運(yùn)行時(shí)間呈下降趨勢(shì)?？紤]不同元啟發(fā)式算法的收斂速度存在差異，為公平對(duì)比不同元啟發(fā)式算法的求解性能，統(tǒng)一對(duì)不同元啟發(fā)式算法設(shè)置一個(gè)相同的最大CPU運(yùn)行時(shí)間，作為元啟發(fā)式算法的運(yùn)行停止準(zhǔn)則。圖4所示為不同分散度的3種運(yùn)行時(shí)長(zhǎng)下，元啟發(fā)式算法的平均偏差A(yù)RPD，虛線表示H*算法的ARPD值?？梢钥闯觯S著運(yùn)行時(shí)間上升，SA算法偏差變化不大，基本收斂至局部最優(yōu)解，而其余元啟發(fā)式算法依然還有提升空間。另外，在低分散度下，當(dāng)ρ≤300，即運(yùn)行時(shí)間小于300nms時(shí)，H*算法的ARPD均小于HGA、HDE、HEDA、HPSO算法，隨著運(yùn)行時(shí)間上升為ρ=500，HEDA、HPSO的ARPD才低于H*算法。在高分散度下，當(dāng)ρ=100時(shí)，H*算法的ARPD值與SA算法相近，即使在最大運(yùn)行時(shí)長(zhǎng)ρ=500，其ARPD依然小于HGA、HDE、HEDA、HPSO算法的ARPD。

表4 啟發(fā)式算法的實(shí)例平均運(yùn)行時(shí)間

綜合以上分析，本文所提H*算法在求解的效果上明顯好于其余調(diào)度規(guī)則，接近甚至優(yōu)于元啟發(fā)式算法求解效果，且相較于迭代尋優(yōu)的元啟發(fā)式算法，隨著任務(wù)數(shù)量的增加,H*算法的運(yùn)行時(shí)間均在可接受范圍之內(nèi)，即使面對(duì)大規(guī)模問題，也能在足夠短的時(shí)間內(nèi)得到高質(zhì)量解，滿足出庫打包調(diào)度實(shí)時(shí)求解的要求，是所研究的出庫打包調(diào)度問題的一種有效求解算法。

4 結(jié)束語

本文將定制家具自動(dòng)分揀作業(yè)中的出庫及包裝作業(yè)抽象為一類考慮板件在相鄰兩階段機(jī)器間具有一定運(yùn)輸時(shí)間，且板件處理具有優(yōu)先順序約束及機(jī)器約束的三階段柔性裝配流水車間調(diào)度問題，并建立了相應(yīng)的數(shù)學(xué)模型。

針對(duì)本文研究的數(shù)學(xué)模型，構(gòu)造了一種求解該類問題的啟發(fā)式算法H*?；诹褏^(qū)試驗(yàn)設(shè)計(jì)的思想設(shè)計(jì)了該類問題的仿真算例，并與另外構(gòu)造的7種組合規(guī)則算法以及5種元啟發(fā)式算法進(jìn)行性能比較。算例的仿真及結(jié)果分析表明了H*算法對(duì)于求解所研究的出庫打包調(diào)度問題的有效性和優(yōu)越性。

本文研究的出庫打包調(diào)度問題中，出庫階段的加工機(jī)器(即機(jī)械手)不考慮隨機(jī)事件干擾，但在實(shí)際分揀作業(yè)中，可能存在單個(gè)機(jī)械手需要處理入庫及出庫兩類任務(wù)的情況。因?yàn)闄C(jī)械手需要兼顧入庫任務(wù)，分揀機(jī)械手的可出庫時(shí)間具有不確定性，所以考慮第一階段機(jī)械手狀態(tài)不確定性的動(dòng)態(tài)調(diào)度規(guī)則將是下一步研究工作的重點(diǎn)。