汪浩祥，嚴(yán)洪森，汪 崢

（1.東南大學(xué) 自動化學(xué)院，江蘇 南京 210096；2.南京農(nóng)業(yè)大學(xué) 工學(xué)院，江蘇 南京 210031；3.東南大學(xué) 復(fù)雜工程系統(tǒng)測量與控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210096）

0 引言

航空發(fā)動機(jī)制造技術(shù)是航空工業(yè)發(fā)展的核心技術(shù)，裝配技術(shù)則是航空發(fā)動機(jī)生產(chǎn)的主要技術(shù)構(gòu)成之一。為保證發(fā)動機(jī)安全、穩(wěn)定及精確地運(yùn)行，對其加工和裝配精度要求極高。在一臺發(fā)動機(jī)的裝配過程中，除具有裝配作業(yè)調(diào)度問題（Assembly Job Shop Scheduling Problem，AJSSP）的一般特征外，還有需經(jīng)歷多次分解后再重新裝配的過程。此外，在實(shí)際生產(chǎn)過程中，存在很多具有隨機(jī)性的動態(tài)事件，例如任務(wù)隨機(jī)到達(dá)或檢試不合格等，此類動態(tài)事件的發(fā)生常常導(dǎo)致實(shí)際的生產(chǎn)環(huán)境經(jīng)常呈現(xiàn)出動態(tài)的、不穩(wěn)定的、時(shí)變的特性。

對于航空發(fā)動機(jī)裝配問題，目前已有一些學(xué)者進(jìn)行了研究［1-2］，這些研究主要集中在裝配建模和設(shè)計(jì)方面，對航空發(fā)動機(jī)裝配調(diào)度問題的研究較少。對于普通的裝配車間作業(yè)調(diào)度問題，文獻(xiàn)［3］提出一種基于最小加權(quán)提前期懲罰的裝配車間調(diào)度算法。文獻(xiàn)［4］對裝配環(huán)境下的車間作業(yè)問題提出一種基于可行域搜索的遺傳算法并進(jìn)行調(diào)度。文獻(xiàn)［5］提出一種結(jié)合簡單分派規(guī)則的混合型遺傳算法。文獻(xiàn)［6］基于調(diào)度規(guī)則提出一種由機(jī)器選擇模塊和工序調(diào)度模塊構(gòu)成的調(diào)度算法。然而，現(xiàn)有研究大都只考慮靜態(tài)環(huán)境下的裝配作業(yè)調(diào)度問題，即系統(tǒng)自身參數(shù)已知且固定不變，沒有考慮實(shí)際環(huán)境的動態(tài)變化［7-9］。因此，對于航空發(fā)動機(jī)裝配調(diào)度問題，需要尋求一種能自適應(yīng)環(huán)境變化的動態(tài)調(diào)度策略。

目前，在自適應(yīng)生產(chǎn)調(diào)度方面，已有一些學(xué)者進(jìn)行了研究［10-14］，但對于裝配車間作業(yè)自適應(yīng)調(diào)度問題研究甚少［15］。近年來，隨著國內(nèi)外研究機(jī)構(gòu)對強(qiáng)化學(xué)習(xí)［16］研究的深入，強(qiáng)化學(xué)習(xí)技術(shù)越來越多地被應(yīng)用到生產(chǎn)調(diào)度領(lǐng)域［17-19］，由于強(qiáng)化學(xué)習(xí)方法在求解未知環(huán)境中的序列決策問題時(shí)體現(xiàn)了很好的優(yōu)越性，其自學(xué)習(xí)和在線學(xué)習(xí)的特點(diǎn)特別適合于解決系統(tǒng)擾動較多的自適應(yīng)調(diào)度問題。應(yīng)用強(qiáng)化學(xué)習(xí)方法對調(diào)度規(guī)則（策略）進(jìn)行動態(tài)選取，增強(qiáng)了調(diào)度的自適應(yīng)性，為自適應(yīng)調(diào)度問題的研究開辟了另一條有效途徑。Q學(xué)習(xí)［20］和TD（λ）是應(yīng)用在生產(chǎn)調(diào)度中的兩種最主要的強(qiáng)化學(xué)習(xí)方法，目前已有一些學(xué)者作了這方面的嘗試。如針對Job Shop調(diào)度問題，Aydin等［21］利用Q-Ⅲ算法訓(xùn)練智能體動態(tài)選擇調(diào)度規(guī)則。Wang等［22］將強(qiáng)化學(xué)習(xí)應(yīng)用于動態(tài)單機(jī)調(diào)度研究，利用Q學(xué)習(xí)算法尋找出不同調(diào)度目標(biāo)下最合適的調(diào)度規(guī)則。其后王國磊等［18］、Yang等［19］和Zhang等［23］也分別對利用Q學(xué)習(xí)和TD（λ）算法實(shí)時(shí)選擇調(diào)度規(guī)則問題進(jìn)行了研究。

盡管強(qiáng)化學(xué)習(xí)方法具有良好的應(yīng)用前景，但在自適應(yīng)動態(tài)調(diào)度領(lǐng)域，尤其是裝配作業(yè)調(diào)度問題上仍然沒有太多的應(yīng)用，困難主要在于如何將調(diào)度問題轉(zhuǎn)化為強(qiáng)化學(xué)習(xí)問題以及如何在這些調(diào)度問題上應(yīng)用強(qiáng)化學(xué)習(xí)的方法。由于航空發(fā)動機(jī)部件工序眾多，裝配任務(wù)隨機(jī)到達(dá)且在裝配過程中存在裝配次數(shù)不確定等因素，導(dǎo)致很多狀態(tài)不具備重復(fù)性，通常的表格型強(qiáng)化學(xué)習(xí)方法難以持續(xù)更新每個(gè)狀態(tài)—動作對值，且通常的單層Q學(xué)習(xí)僅通過學(xué)習(xí)調(diào)度策略來合理安排工件的加工順序，很少考慮機(jī)器分配，這對需滿足工序優(yōu)先約束的航空發(fā)動機(jī)裝配問題可能出現(xiàn)機(jī)器負(fù)載和當(dāng)前負(fù)載的不平衡，從而不能有效提高機(jī)器利用率。同時(shí)，對于裝配作業(yè)調(diào)度問題，在之前的大多數(shù)研究中，作業(yè)的到達(dá)時(shí)間都是已知的，并假設(shè)有固定的交貨期，解決的是確定性裝配問題，所用方法對具有眾多不確定性的航空發(fā)動機(jī)自適應(yīng)裝配調(diào)度問題效果不太理想。

知識化制造是一種新的制造理念［24］，它致力于解決現(xiàn)有制造模式中存在的模式單一、缺乏靈活性、不能滿足制造企業(yè)需求的多樣性以及重復(fù)研發(fā)等問題，基于知識化制造理念構(gòu)建的知識化制造系統(tǒng)（Knowledgeable Manufacture System，KMS）以時(shí)間、質(zhì)量、成本、服務(wù)和環(huán)境為主要目標(biāo)，能夠通過學(xué)習(xí)獲取新知識，適應(yīng)新環(huán)境，不斷自我完善和進(jìn)化，具備自適應(yīng)、自學(xué)習(xí)、自進(jìn)化和自重構(gòu)等特征。自適應(yīng)是知識化制造系統(tǒng)的重要特征，它是指針對系統(tǒng)環(huán)境的多變性，系統(tǒng)自身通過對控制（調(diào)度）策略或參數(shù)的調(diào)整，來適應(yīng)外界環(huán)境的變化。

在不確定裝配環(huán)境下，如何減少每道工序的裝配等待時(shí)間，使提前期總成本最小，是航空發(fā)動機(jī)制造企業(yè)優(yōu)化的主要目標(biāo)，也是一類重要的優(yōu)化調(diào)度問題。本文基于強(qiáng)化學(xué)習(xí)方法，結(jié)合知識化制造系統(tǒng)的自適應(yīng)特征，提出用于解決動態(tài)環(huán)境下航空發(fā)動機(jī)裝配自適應(yīng)調(diào)度問題的雙層Q學(xué)習(xí)方法（D-Q算法），上層Q學(xué)習(xí)著眼于局部，學(xué)習(xí)在不同的狀態(tài)采用合適的分派規(guī)則將作業(yè)分配到并行機(jī)器，以最小化設(shè)備空閑和機(jī)器負(fù)荷。而下層Q學(xué)習(xí)則著眼于全局，以最小化作業(yè)整體提前期為目標(biāo)，在不同狀態(tài)學(xué)習(xí)最優(yōu)策略用來對分配到每臺機(jī)器的所有工序進(jìn)行調(diào)度，安排合理的加工順序。采用基于函數(shù)逼近的Q（λ）學(xué)習(xí)算法，以最小化所有工序的總提前期為目標(biāo)，通過合理地定義強(qiáng)化學(xué)習(xí)問題三大要素——動作（調(diào)度規(guī)則）、狀態(tài)特征和回報(bào)函數(shù)，將航空發(fā)動機(jī)自適應(yīng)裝配調(diào)度問題轉(zhuǎn)化為強(qiáng)化學(xué)習(xí)問題；在動態(tài)的生產(chǎn)環(huán)境中，通過在上下兩層適時(shí)調(diào)整調(diào)度策略，實(shí)現(xiàn)航空發(fā)動機(jī)裝配的自適應(yīng)優(yōu)化調(diào)度。

1 問題描述

航空發(fā)動機(jī)的裝配調(diào)度問題既具有一般裝配作業(yè)調(diào)度問題的共性（典型的裝配結(jié)構(gòu)特征），也有其特殊性。由于航空發(fā)動機(jī)是飛機(jī)的關(guān)鍵核心部件，對其合格率要求極高。因此，一臺發(fā)動機(jī)裝配過程中，需經(jīng)歷多次分解和重新裝配的過程。如圖1所示，部件＊、傳裝＊、總裝＊和檢試分別表示多次重復(fù)裝配過程。

而每臺發(fā)動機(jī)又具有典型的裝配結(jié)構(gòu)特征，其裝配物料清單（Bill of Material，BOM）上的部件具有分層結(jié)構(gòu)的裝配優(yōu)先順序，裝配由具體班組完成，具有相同父節(jié)點(diǎn)的部件能在不同班組上同時(shí)進(jìn)行裝配，每個(gè)部件包含具有確定順序的多道工序，即同一部件的不同工序不能在不同班組上同時(shí)裝配，每個(gè)裝配班包含一個(gè)或多個(gè)能力相同的并行裝配組，每個(gè)裝配班可承擔(dān)多道工序的裝配。為方便問題描述，以下表述中的機(jī)器即為裝配組，加工即為裝配。

假設(shè)試車、分解和故檢時(shí)間固定，發(fā)動機(jī)到達(dá)時(shí)間間隔服從負(fù)指數(shù)分布，忽略準(zhǔn)備時(shí)間，工序到達(dá)即可加工，每臺發(fā)動機(jī)至少需要兩次裝配，實(shí)際裝配次數(shù)為一隨機(jī)變量。以最小化所有工序的總提前期為目標(biāo)函數(shù)，建立如下航空發(fā)動機(jī)裝配的自適應(yīng)優(yōu)化調(diào)度數(shù)學(xué)模型：

（1）符號定義

N為發(fā)動機(jī)臺數(shù)；

Ji為第i臺發(fā)動機(jī)的部件數(shù)；

Oiδjk為第i臺發(fā)動機(jī)第δ次裝配的第j個(gè)部件的第k道工序；

O（iδjk）＊為工序Oiδjk的父工序；

O（iδjk）′為不同于工序Oiδjk的另一道工序；

Ciδjk為工序Oiδjk的完工時(shí)間；

Siδjk為工序Oiδjk的開始時(shí)間；

piδjk為工序Oiδjk的實(shí)際加工時(shí)間；

lij為第i臺發(fā)動機(jī)第j個(gè)部件包含的工序數(shù)；

ti為第i臺發(fā)動機(jī)兩次裝配間的試車、分解、故檢時(shí)間總和；

ξi為第i臺發(fā)動機(jī)的裝配次數(shù)；

A為動作（調(diào)度規(guī)則）集。

（2）建立模型

其中：式（1）為目標(biāo)函數(shù)，式（2）～式（8）為約束條件。式（2）為裝配次數(shù)約束，其中ξi為一隨機(jī)變量；式（3）表示決策變量，at（1≤t≤U）為第t步?jīng)Q策時(shí)刻狀態(tài)下選取的動作，其中U為調(diào)度過程中的總決策步數(shù)；式（4）表示工序的實(shí)際加工時(shí)間等于工序的完工時(shí)間與開始時(shí)間的差值，即每道工序在加工時(shí)不允許被中斷；式（5）表示父工序的開始時(shí)間大于或等于子工序的完工時(shí)間，即工序有優(yōu)先約束關(guān)系；式（6）表示每臺發(fā)動機(jī)第2次裝配的工序開始時(shí)間必須在第一次裝配結(jié)束并完成試車、分解和故檢之后，其中為第i臺發(fā)動機(jī)的最后一道工序；式（7）和式（8）表示每個(gè)裝配組內(nèi)同一時(shí)刻只能加工一道工序，其中yiδjk（iδjk）′q為0-1變量，若第q組內(nèi)工序Oiδjk在工序O（iδjk）′前加工則為1，否則為0，β為一大的正數(shù)。需要指出的是：由于最后一道工序無父工序，本文用一個(gè)虛擬工序代替。

2 雙層Q 學(xué)習(xí)方法

Q學(xué)習(xí)是一種典型的強(qiáng)化學(xué)習(xí)方法，具有自適應(yīng)、在線學(xué)習(xí)、試錯以及自我選擇的特點(diǎn)，它不需要建立任何領(lǐng)域模型，而是直接優(yōu)化一個(gè)可迭代計(jì)算的Q函數(shù)，獲得最優(yōu)控制策略。然而，對于單機(jī)動態(tài)調(diào)度問題十分有效的Q學(xué)習(xí)，對不確定調(diào)度環(huán)境下的多機(jī)航空發(fā)動機(jī)裝配問題卻由于缺乏全局眼光而效果欠佳。

為此，針對航空發(fā)動機(jī)裝配自適應(yīng)調(diào)度問題，本文提出一種雙層的Q學(xué)習(xí)算法，通過在機(jī)器選擇層和工序調(diào)度層中分別進(jìn)行Q學(xué)習(xí)，在上下兩層適時(shí)選取合適的調(diào)度規(guī)則，以適應(yīng)環(huán)境的變化，從而實(shí)現(xiàn)航空發(fā)動機(jī)裝配調(diào)度的自適應(yīng)。雙層Q學(xué)習(xí)的自適應(yīng)調(diào)度機(jī)制如圖2所示。

圖2中，上層為機(jī)器選擇層（Machine Selection Module，MSM），下層為工序調(diào)度層（Operation Scheduling Module，OSM）。上層Q學(xué)習(xí)著眼于局部，根據(jù)當(dāng)前系統(tǒng)狀態(tài)學(xué)習(xí)合適的分派規(guī)則，用于分配作業(yè)到可加工該工序的并行機(jī)器，達(dá)到最小化設(shè)備空閑和平衡機(jī)器負(fù)荷的目標(biāo)；下層Q學(xué)習(xí)則著眼于全局，根據(jù)當(dāng)前系統(tǒng)狀態(tài)學(xué)習(xí)最優(yōu)的調(diào)度策略，對分配到每臺機(jī)器的所有工序進(jìn)行調(diào)度，安排合理的加工順序，以最小化作業(yè)整體提前期。

根據(jù)本文目標(biāo)函數(shù)和航空發(fā)動機(jī)生產(chǎn)裝配的特點(diǎn)，結(jié)合最底層工序優(yōu)先（Lowest Level Code，LLC）、最長加工時(shí)間工序優(yōu)先（the Longest Processing Time，LPT）和最短加工時(shí)間工序優(yōu)先（the Shortest Processing Time，SPT）規(guī)則組成四個(gè)新的規(guī)則：LL（LLC＋LPT）規(guī)則、LS（LLC＋SPT）規(guī)則、LPL（LPT＋LLC）規(guī)則和SL（SPT＋LLC）規(guī)則，作為兩層Q學(xué)習(xí)的動作集，同時(shí)定義兩層Q學(xué)習(xí)的狀態(tài)空間，并針對兩層Q學(xué)習(xí)分別設(shè)計(jì)合適的獎懲函數(shù)。

2.1 上層Q 學(xué)習(xí)

上層Q學(xué)習(xí)的主要任務(wù)是將全局緩沖區(qū)中的任務(wù)分配到合適的機(jī)器，因此上層Q學(xué)習(xí)的設(shè)計(jì)就是為了使系統(tǒng)能夠根據(jù)當(dāng)前作業(yè)的特征以及各可用機(jī)器的負(fù)荷合理選擇加工機(jī)器，以提高機(jī)器利用率、平衡機(jī)器當(dāng)前負(fù)載。上層Q學(xué)習(xí)算法流程如圖3所示。

2.1.1 調(diào)度動作

根據(jù)上層Q學(xué)習(xí)目標(biāo)和航空發(fā)動機(jī)裝配的特點(diǎn)，選取LL和LS 兩種調(diào)度規(guī)則作為上層Q學(xué)習(xí)動作集中的動作。當(dāng)選取LL 規(guī)則時(shí)，首先根據(jù)LLC規(guī)則從全局緩沖區(qū)加工隊(duì)列中選取處于發(fā)動機(jī)裝配樹形結(jié)構(gòu)中的最下層工序進(jìn)行加工，若存在相同加工時(shí)間的工序，則進(jìn)一步根據(jù)LPT 規(guī)則選擇具有最長加工時(shí)間的工序進(jìn)行加工。同理，若采用LS規(guī)則，則首先根據(jù)LLC 規(guī)則從全局緩沖區(qū)加工隊(duì)列中選取處于發(fā)動機(jī)裝配樹形結(jié)構(gòu)中的最下層工序進(jìn)行加工，若存在相同加工時(shí)間的工序，則進(jìn)一步根據(jù)SPT 規(guī)則選擇具有最短加工時(shí)間的工序進(jìn)行加工。

工序確定后，將其分配到機(jī)器進(jìn)行加工，若該工序僅能在一臺機(jī)器上加工，則選擇該臺機(jī)器，若工序能在多臺并行機(jī)上加工，則將工序分配給具有最小負(fù)載的機(jī)器加工。

2.1.2 回報(bào)函數(shù)

根據(jù)上層Q學(xué)習(xí)的目標(biāo)，將當(dāng)前所有機(jī)器剩余加工時(shí)間的方差（即負(fù)載平衡因子）作為上層Q學(xué)習(xí)回報(bào)函數(shù)，由于Q學(xué)習(xí)收斂于最大值，故采用其值的相反數(shù)，定義立即回報(bào)為

式中：zq為機(jī)器q的當(dāng)前剩余加工時(shí)間，為當(dāng)前所有機(jī)器的平均剩余加工時(shí)間，m為機(jī)器數(shù)目。通過定義負(fù)載平衡因子作為上層Q學(xué)習(xí)回報(bào)函數(shù)，可以提高機(jī)器利用率、減少工序等待時(shí)間，即可以減少作業(yè)整體提前期，從而有助于達(dá)到最小化所有工序提前期的總目標(biāo)。

為了說明上層Q學(xué)習(xí)的必要性，首先給出如下定義。

定義1 在航空發(fā)動機(jī)裝配中，令機(jī)器緩沖區(qū)中的剩余加工時(shí)間表示機(jī)器負(fù)載，記作ω，則將機(jī)器緩沖區(qū)中當(dāng)前可加工的工序加工時(shí)間之和稱為該機(jī)器的當(dāng)前負(fù)載，用ωt表示。

在航空發(fā)動機(jī)裝配自適應(yīng)調(diào)度中，通過上層Q學(xué)習(xí)，找到合適的工序分配規(guī)則，從全局緩沖區(qū)中選擇工序分配到并行機(jī)器，以提高機(jī)器利用率和平衡各并行機(jī)器的當(dāng)前負(fù)載。下面舉例說明。

如圖4所示，由于航空發(fā)動機(jī)裝配中的工序存在優(yōu)先約束關(guān)系，部件J1的第1 道工序OP11能在M1裝配班中的任何一個(gè)裝配組中進(jìn)行裝配；當(dāng)J1的第2道工序OP12完成后才能開始J3的第1道工序OP31的裝配；J2的第1道工序OP21和最后一道工序OP23都在相同的班組進(jìn)行裝配。由于工序需等其優(yōu)先工序加工完才能加工，若只是簡單地按最小負(fù)載原則將工序分配到負(fù)載最小的機(jī)器，則將使機(jī)器負(fù)載和當(dāng)前負(fù)載出現(xiàn)不平衡。

以M1為例，假設(shè)M1包含兩個(gè)能力相同的并行裝配組M11和M12，可裝配工序OP11，OP21，OP23和OP31，令為工序OP11的加工時(shí)間，同樣地，令分別為工序OP21，OP23和OP31的加工時(shí)間，并令；對于并行裝配組M11和M12，若不通過Q學(xué)習(xí)選擇規(guī)則對工序進(jìn)行班組分配，則其負(fù)荷將可能出現(xiàn)如圖5a所示的分配結(jié)果。需要說明的是，圖5僅表示裝配組負(fù)荷，而非考慮調(diào)度的甘特圖。

按定義1 和工序優(yōu)先約束，可計(jì)算出裝配組M11負(fù)載為，當(dāng)前負(fù)載為；同理可得，M12負(fù)載為，當(dāng)前負(fù)載為

通過在機(jī)器分配中加入上層Q學(xué)習(xí)，選取文中定義的分派規(guī)則選擇工序并結(jié)合最小負(fù)載原則分配到機(jī)器，可得如圖5b所示結(jié)果，經(jīng)計(jì)算得此時(shí)M11負(fù)載為，當(dāng)前負(fù)載為；M12負(fù)載為，當(dāng)前負(fù)載為；此時(shí)M11和M12機(jī)器負(fù)載平衡、其當(dāng)前負(fù)載基本平衡。因此，通過Q學(xué)習(xí)，可以提高機(jī)器利用率和平衡各并行機(jī)器當(dāng)前負(fù)載。

2.2 下層Q 學(xué)習(xí)

當(dāng)一臺發(fā)動機(jī)的所有工序都分配到合適的機(jī)器緩沖區(qū)中時(shí)，下層Q學(xué)習(xí)的目的是使每臺機(jī)器都能夠根據(jù)系統(tǒng)狀態(tài)選擇最優(yōu)的調(diào)度策略，從而達(dá)到最小化作業(yè)整體提前期的全局目標(biāo)。下層Q學(xué)習(xí)算法的流程如圖6所示。

2.2.1 調(diào)度動作

根據(jù)下層Q學(xué)習(xí)目標(biāo)和航空發(fā)動機(jī)的裝配特點(diǎn)，選取LL，LS，LPL和SL四種調(diào)度規(guī)則構(gòu)成底層Q學(xué)習(xí)動作集中的動作，其中規(guī)則LL和LS定義與上層Q學(xué)習(xí)動作相同，不同的是下層規(guī)則是從機(jī)器可加工隊(duì)列中選擇工序，而上層則是從全局緩沖區(qū)中選取。采用LPL 規(guī)則時(shí)，首先采用LPT 規(guī)則從機(jī)器可加工隊(duì)列中選取具有最長加工時(shí)間的工序進(jìn)行加工，若存在相同加工時(shí)間的工序，則進(jìn)一步根據(jù)LLC規(guī)則選擇處于發(fā)動機(jī)裝配樹形結(jié)構(gòu)中的最下層工序進(jìn)行加工。同理，對于SL 規(guī)則，首先根據(jù)SPT 規(guī)則從機(jī)器可加工隊(duì)列中選取具有最短加工時(shí)間的工序進(jìn)行加工，若存在相同加工時(shí)間的工序，則在具有相同工件層的工序中，進(jìn)一步根據(jù)LLC規(guī)則選擇處于發(fā)動機(jī)裝配樹形結(jié)構(gòu)中的最下層工序進(jìn)行加工。

2.2.2 回報(bào)函數(shù)

回報(bào)函數(shù)的定義與調(diào)度的目標(biāo)函數(shù)直接或間接相關(guān)，合適的回報(bào)函數(shù)不但可使即時(shí)回報(bào)反映行為的即時(shí)效果，而且可使累積回報(bào)表征目標(biāo)函數(shù)的大小，反映行為的長期效果，也就是說，更大的累積回報(bào)對應(yīng)更小的提前期。

根據(jù)下層Q學(xué)習(xí)目標(biāo)并結(jié)合本文目標(biāo)函數(shù)，首先定義代表工序Oiδjk裝配提前期信息的示性函數(shù)τiδjk（t），

則定義第u步?jīng)Q策時(shí)刻的立即回報(bào)為

式中為在第u步?jīng)Q策時(shí)段［tu-1，tu］內(nèi)到達(dá)的發(fā)動機(jī)裝配任務(wù)數(shù)。

定理1 令U代表在一個(gè)episode中的決策步數(shù)，一個(gè)episode是指從起始狀態(tài)到目標(biāo)狀態(tài)的完整步驟序列，則在每個(gè)episode中最大化累積回報(bào)等價(jià)于最小化總提前期，即有成立。式中ET為總提前期。

證明

由式（9），式（12）可進(jìn)一步改寫為：

由于本文目標(biāo)函數(shù)即為最小化總提前期，則有

可見，在一個(gè)episode中，最大化累積回報(bào)即等價(jià)于最小化提前期總成本，而Q學(xué)習(xí)算法的目標(biāo)正是最大化每個(gè)episode中的累積回報(bào)，因此定理1確保了當(dāng)Q學(xué)習(xí)目標(biāo)獲得后，也達(dá)到了調(diào)度目標(biāo)。因此用式（10）定義回報(bào)函數(shù)可以將回報(bào)函數(shù)和調(diào)度的目標(biāo)函數(shù)直接聯(lián)系起來，直接反映行為對目標(biāo)函數(shù)的長期影響，有利于找到對全局而言較優(yōu)的調(diào)度策略。

3 Q 學(xué)習(xí)模型

由于航空發(fā)動機(jī)包含眾多部件，并存在多次裝配過程，在裝配過程中通常具有大規(guī)模的狀態(tài)空間，并且很多狀態(tài)不具備重復(fù)性。為了提高算法搜索的精度，用基于梯度下降法的線性函數(shù)對值函數(shù)進(jìn)行逼近，具體地說，就是對每個(gè)動作a，用一個(gè)基函數(shù)的線性組合來近似值函數(shù)，即根據(jù)已經(jīng)經(jīng)歷過的狀態(tài)或狀態(tài)-動作值來近似沒有經(jīng)歷過的狀態(tài)或動作的值，如式（13）所示。

式中：wa為動作a的權(quán)向量并有為關(guān)于式（14）定義的狀態(tài)特征向量，作為基函數(shù)向量。

在學(xué)習(xí)過程中通過不斷調(diào)整基函數(shù)的權(quán)重，來不斷改變相對行為值函數(shù)Q（s，a），其作用相當(dāng)于表格型Q學(xué)習(xí)的值函數(shù)更新方程。采用梯度下降法，應(yīng)用值函數(shù)Q（s，a）相對于權(quán)向量wa的梯度▽waQ（s，a）=ws對權(quán)值進(jìn)行更新，通過更新權(quán)向量來更新Q值函數(shù)。具體過程見3.2節(jié)算法步驟5。

3.1 狀態(tài)特征

狀態(tài)空間的劃分是系統(tǒng)合理選擇調(diào)度規(guī)則的基礎(chǔ)，然而在生產(chǎn)環(huán)境不斷變化的航空發(fā)動機(jī)自適應(yīng)裝配調(diào)度中，完整的系統(tǒng)狀態(tài)是連續(xù)的，且往往可由十幾個(gè)甚至幾十個(gè)狀態(tài)特征刻畫。為便于分析，經(jīng)過大量的仿真實(shí)驗(yàn)，本文選取四種對調(diào)度規(guī)則性能影響較大的狀態(tài)特征指標(biāo)，來反映當(dāng)前時(shí)刻各種工件和設(shè)備的狀態(tài)，以適應(yīng)航空發(fā)動機(jī)對每個(gè)部件裝配的精細(xì)要求。基于上述Q學(xué)習(xí)模型，假設(shè)某發(fā)動機(jī)裝配線有m個(gè)裝配組，可裝配n種型號的發(fā)動機(jī)，裝配任務(wù)動態(tài)隨機(jī)到達(dá)，則分別定義特征f1p，f2p，f3q和f4q（1≤p≤n，1≤q≤m）對當(dāng)前時(shí)刻系統(tǒng)狀態(tài)進(jìn)行描述。

（1）狀態(tài)特征1

式中NJp為當(dāng)前時(shí)刻隊(duì)列中p型號發(fā)動機(jī)的數(shù)量，該特征反映當(dāng)前時(shí)刻隊(duì)列中各型號發(fā)動機(jī)的數(shù)量。

（2）狀態(tài)特征2

（3）狀態(tài)特征3

式中：Ltq為機(jī)器q的剩余加工時(shí)間（緩沖區(qū)中待加工工序的加工時(shí)間之和）為所有機(jī)器的平均剩余加工時(shí)間。該特征表示當(dāng)前時(shí)刻各機(jī)器相對負(fù)載。

（4）狀態(tài)特征4

該特征反映當(dāng)前時(shí)刻各設(shè)備利用情況。由式（14），可得式（13）中基函數(shù)的向量個(gè)數(shù)Nf=2（m＋n）。

在對上述特征值采用比例因子法［18］進(jìn)行正規(guī)化預(yù)處理后，按照本文Q學(xué)習(xí)模型，狀態(tài)s的特征用向量Fs表示，

若有新的發(fā)動機(jī)裝配任務(wù)到達(dá)或有任何部件工序完成裝配，或當(dāng)從全局緩沖區(qū)中分派一道工序到機(jī)器或從機(jī)器隊(duì)列中選擇一道工序進(jìn)行加工時(shí)，都將發(fā)生一次狀態(tài)轉(zhuǎn)移。所有部件工序隨著發(fā)動機(jī)的到達(dá)一次性到達(dá)系統(tǒng)，在系統(tǒng)初始狀態(tài)沒有任務(wù)到達(dá)或等待加工，所有班組空閑，一旦上述引起狀態(tài)改變的事件發(fā)生，狀態(tài)轉(zhuǎn)移到一個(gè)新的狀態(tài)時(shí)，系統(tǒng)就會根據(jù)ε-貪婪策略在上下兩層分別選擇并執(zhí)行動作，同時(shí)計(jì)算回報(bào)值，在下一步?jīng)Q策，系統(tǒng)轉(zhuǎn)移到下一個(gè)狀態(tài)，每次都根據(jù)ε-貪婪策略選擇動作，直到所有任務(wù)裝配結(jié)束。

3.2 算法步驟

基于函數(shù)逼近的Q（λ）值函數(shù)更新算法步驟如下：

步驟2 設(shè)置當(dāng)前狀態(tài)s為初始狀態(tài)s0，按3.1節(jié)定義計(jì)算初始狀態(tài)的特征向量Fs0。

步驟4 執(zhí)行動作a，確定下一個(gè)決策時(shí)刻。當(dāng)有上述引起狀態(tài)改變的事件發(fā)生時(shí)，系統(tǒng)轉(zhuǎn)移到一個(gè)新的狀態(tài)s′，計(jì)算s′的特征向量Fs′，并計(jì)算該步?jīng)Q策的回報(bào)值r（s，a，s′）。

步驟5 按式（15）～式（17）更新式（13）中動作a的權(quán)向量wa。

式中：α為學(xué)習(xí)率，δ（a）為通常的時(shí)間差分（Temporal Difference，TD）誤差，γ（0≤γ＜1）為折扣因子，Q（s′，b）為下一決策時(shí)刻狀態(tài)s′的狀態(tài)動作值，E（a）代表動作a的資格跡向量，且有，λ為更新資格跡的折扣因子。

步驟6 置s=s′，轉(zhuǎn)步驟3。

步驟7 若已裝配發(fā)動機(jī)數(shù)目大于裝配的最大任務(wù)數(shù)，則算法結(jié)束。

4 算法仿真

以某航空發(fā)動機(jī)生產(chǎn)企業(yè)為例，其裝配線有10個(gè)裝配班，包含15個(gè)裝配組，可裝配3種型號的發(fā)動機(jī)，每道工序加工時(shí)間固定，裝配任務(wù)動態(tài)隨機(jī)到達(dá)，假設(shè)到達(dá)間隔服從負(fù)指數(shù)分布，忽略準(zhǔn)備時(shí)間，工序到達(dá)即可加工。圖7為經(jīng)簡化的某型號發(fā)動機(jī)裝配樹形結(jié)構(gòu)圖。圖中數(shù)字含義為：a-b表示第a個(gè)部件的第b道工序。具體部件序號及對應(yīng)的部件名稱如表1所示。

表1 部件序號與部件名稱對照表

每個(gè)裝配班由一個(gè)或二個(gè)能力相同的并行裝配組組成，由每個(gè)裝配組完成航空發(fā)動機(jī)的具體裝配任務(wù)，裝配班組數(shù)及可加工工序如表2所示。

表2 裝配班組及可加工工序

為驗(yàn)證本文雙層Q學(xué)習(xí)D-Q算法的自適應(yīng)性能和調(diào)度效果，考慮不同型號發(fā)動機(jī)到達(dá)頻率差異較大的情況，設(shè)置3種型號發(fā)動機(jī)到達(dá)率參數(shù)分別為λ1=1／50，λ2=1／100和λ3=1／150，代表裝配任務(wù)到達(dá)頻率高、中、低三種情況；每臺發(fā)動機(jī)裝配次數(shù)ξi為一隨機(jī)變量，ξi∈｛2，3，4｝；分別以每加工5臺和10臺發(fā)動機(jī)為一個(gè)episode，每個(gè)episode中各種型號發(fā)動機(jī)隨機(jī)到達(dá)。分別用LL，LS，LPL，SL規(guī)則和本文D-Q算法進(jìn)行仿真，取200 個(gè)episode提前期的總均值作比較，表3 為各種算法的仿真結(jié)果。

表3 200個(gè)Episode平均提前期（與單個(gè)規(guī)則比較）

為進(jìn)一步比較本文雙層Q學(xué)習(xí)算法與單層Q學(xué)習(xí)S-Q算法的運(yùn)行效果（單層Q學(xué)習(xí)是指在工序分配機(jī)器時(shí)不學(xué)習(xí)分配規(guī)則，采用最小負(fù)載原則分配機(jī)器，而只在機(jī)器選擇工序進(jìn)行加工時(shí)學(xué)習(xí)調(diào)度規(guī)則），以N=10為例，分別用單層Q學(xué)習(xí)算法和本文D-Q算法對200個(gè)episode進(jìn)行仿真，考慮到各種隨機(jī)因素的影響，依次計(jì)算每20個(gè)episode提前期的均值和200 個(gè)episode提前期的總均值，兩種算法運(yùn)行結(jié)果如表4所示。

表4 N＝10時(shí)200個(gè)Episode平均提前期（與S-Q 算法比較）

依次取每20個(gè)episode的平均提前期作比較，圖8給出了兩種算法調(diào)度結(jié)果的變化趨勢。

表3顯示，在不同型號發(fā)動機(jī)到達(dá)頻率變化幅度較大的情況下，本文D-Q算法的調(diào)度結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于其他四種規(guī)則，顯示出良好的自適應(yīng)性能，且隨著發(fā)動機(jī)臺數(shù)的增加，本文D-Q算法結(jié)果的優(yōu)勢愈加明顯。由表4可知，采用本文D-Q算法比S-Q算法總均值提高11.7%，總體上表現(xiàn)出更好的優(yōu)勢，從圖8可以看出，D-Q算法在多數(shù)情況下都優(yōu)于S-Q算法，且具有更好的穩(wěn)定性。

5 結(jié)束語

本文以某航空發(fā)動機(jī)裝配線為背景，以最小化所有工序總提前期為目標(biāo)，針對裝配環(huán)境的不確定性，提出了基于雙層Q學(xué)習(xí)的自適應(yīng)優(yōu)化調(diào)度算法。算法基于強(qiáng)化學(xué)習(xí)方法，結(jié)合知識化制造的自適應(yīng)特征，針對各層調(diào)度目標(biāo)和本文目標(biāo)函數(shù)分別定義了調(diào)度規(guī)則和回報(bào)函數(shù)，設(shè)計(jì)了兩層Q學(xué)習(xí)的自適應(yīng)調(diào)度機(jī)制，并定義了四個(gè)狀態(tài)特征對系統(tǒng)狀態(tài)進(jìn)行描述，同時(shí)給出了適合航空發(fā)動機(jī)裝配的Q學(xué)習(xí)自適應(yīng)調(diào)度模型，并證明了回報(bào)函數(shù)與目標(biāo)函數(shù)的一致性。經(jīng)仿真實(shí)驗(yàn)結(jié)果表明，在航空發(fā)動機(jī)裝配自適應(yīng)調(diào)度中，采用本文定義的雙層Q學(xué)習(xí)方法比單層Q學(xué)習(xí)總體上顯示了更好的自適應(yīng)性能，在各種情況下都顯示出良好的效果；與單個(gè)規(guī)則相比，調(diào)度結(jié)果遠(yuǎn)優(yōu)于其他四種規(guī)則，且隨著發(fā)動機(jī)臺數(shù)的增加，優(yōu)勢愈加明顯。在裝配環(huán)境變化頻繁的情況下，總體上顯示了更好的自適應(yīng)性能。該方法通過在不確定的生產(chǎn)環(huán)境中，在上下兩層適時(shí)調(diào)整調(diào)度策略，實(shí)現(xiàn)航空發(fā)動機(jī)裝配的自適應(yīng)優(yōu)化調(diào)度，為不確定生產(chǎn)環(huán)境下的裝配作業(yè)車間調(diào)度問題的研究開辟了一條有效的途徑，同時(shí)對通常的Job Shop和Flow Shop型自適應(yīng)調(diào)度問題也具有很好的適用性和優(yōu)越性。

由于航空發(fā)動機(jī)裝配是人工裝配，對精度的要求還涉及工人熟練程度以及一些主觀因素等。在航空發(fā)動機(jī)裝配車間中，工序的加工時(shí)間與其所在裝配組內(nèi)的工人數(shù)也有關(guān)系。為此，下一步將考慮將每個(gè)裝配組內(nèi)的工人數(shù)及熟練程度視為系統(tǒng)參數(shù)，通過系統(tǒng)參數(shù)的調(diào)整達(dá)到系統(tǒng)自身的調(diào)整，對航空發(fā)動機(jī)裝配的自適應(yīng)調(diào)度問題進(jìn)行進(jìn)一步研究。

［1］WANG Chen'en，YU Hong，ZHANG Wenlei，et al.Objectoriented aero-engine assembly models［J］.Computer Integrated Manufacturing Systems，2010，16（5）：942-948（in Chinese）.［王成恩，于 宏，張聞雷，等.面向?qū)ο蟮暮娇瞻l(fā)動機(jī)裝配模型［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16（5）：942-948.］

［2］TANG Xinmin，ZHONG Shisheng.Aero-engine assembly sequence planning based on discrete-time pontryagin's minimum principl［J］.Control and Decision，2008，23（11）：1221-1230（in Chinese）.［湯新民，鐘詩勝.基于離散時(shí)間最優(yōu)控制的航空發(fā)動機(jī)裝配序列規(guī)劃［J］.控制與決策，2008，23（11）：1221-1230.］

［3］PATHUMNAKULA S，EGBELU P J.An algorithm for minimizing weighted earliness penalty in assembly job shops［J］.International Journal of Production Economics，2006，103（1）：230-245.

［4］WANG Fuji，ZHAO Guokai，JIA Zhenyuan，et al.Assembly job shop scheduling based on feasible solution space genetic algorithm［J］.Computer Integrated Manufacturing Systems，2010，16（1）：115-120（in Chinese）.［王福吉，趙國凱，賈振元，等.基于可行域遺傳算法的裝配作業(yè)調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16（1）：115-120.］

［5］CHAN F T S，WONG T C，CHAN L Y.Lot streaming for product assembly in job shop environment［J］.Robotics and Computer Integrated Manufacturing，2008，24（3）：321-331.

［6］CHEN J C，CHEN K H，WU J J，et al.A study of the flexible job shop scheduling problem with parallel machines and reentrant process［J］.International Journal of Advanced Manufacturing Technology，2008，39（3／4）：344-354.

［7］CUMMINGS D H，MCKOY P J E.Minimizing production flow time in a process and assembly job shop［J］.International Journal of Production Research，1998，36（8）：2315-2332.

［8］PARK M W，KIM Y D.A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints［J］.European Journal of Operational Research，2000，123（3）：504-518.

［9］WANG Linping，JIA Zhenyuan，WANG Fuji.Multi-product complete job-shop scheduling problem and its solution［J］.System Engineering—Theory &Practice，2009，29（9）：73-77（in Chinese）.［王林平，賈振元，王福吉.多產(chǎn)品綜合作業(yè)調(diào)度問題及其求解［J］.系統(tǒng)工程理論與實(shí)踐，2009，29（9）：73-77.］

［10］TAN Yiyong，WANG Rui，F(xiàn)AN Yushun，et al.Adaptive scheduling method for real-time tasks in distributed workflow［J］.Computer Integrated Manufacturing Systems，2010，16（9）：1887-1895（in Chinese）.［譚宜勇，王 銳，范玉順，等.分布式工作流中的自適應(yīng)實(shí)時(shí)任務(wù)調(diào)度方法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16（9）：1887-1895.］

［11］CAO Zhengcai，ZHAO Huidan，WU Qidi.Failure prediction&maintenance scheduling for semiconductor wafer fabrication based on adaptive neuro-fuzzy inference system［J］.Computer Integrated Manufacturing Systems，2010，16（10）：2181-2186（in Chinese）.［曹政才，趙會丹，吳啟迪.基于自適應(yīng)神經(jīng)模糊推理系統(tǒng)的半導(dǎo)體生產(chǎn)線故障預(yù)測及維護(hù)調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16（10）：2181-2186.］

［12］CAI Zhengying，XIAO Renbin，TAN Yong，et al.Fuzzy adaptive production plan dispatching of cycle supply chain under uncertainty conditions［J］.Control and Decision，2008，23（5）：524-529（in Chinese）.［蔡政英，肖人彬，譚 勇，等.不確定條件下循環(huán)供應(yīng)鏈模糊自適應(yīng)生產(chǎn)計(jì)劃調(diào)度［J］.控制與決策，2008，23（5）：524-529.］

［13］NOROOZI A，HADI M，ABADI I N K.Research on computational intelligence algorithms with adaptive learning approach for scheduling problems with batch processing machines［J］.Neurocomputing，2013，101：190-203.

［14］BEHNAMIAN J，GHOMI S M T F.The heterogeneous multi-factory production network scheduling with adaptive communication policy and parallel machine［J］.Information Sciences，2013，219：181-196.

［15］SUSAN K H，JONATHAN F B，DOUGLAS J M.A GRASP for simultaneously assigning and sequencing product families on flexible assembly lines［J］.Annals of Operations Research，2013，203（1）：295-323.

［16］SUTTON R S，BARTO A G.Reinforcement learning：An introduction［M］.Cambridge，Mass.，USA：MIT Press，1998.

［17］WEI Y Z，ZHAO M Y.A reinforcement learning-based approach to dynamic job shop scheduling［J］.Acta Automatica Sinica，2005，31（5）：765-771.

［18］WANG Guolei，LIN Lin，ZHONG Shisheng.Clustering state membership-based Q-learning for dynamic scheduling［J］.Chinese High Technology Letters，2009，19（4）：428-433（in Chinese）.［王國磊，林 琳，鐘詩勝.基于聚類狀態(tài)隸屬度的動態(tài)調(diào)度Q-學(xué)習(xí)［J］.高技術(shù)通訊，2009，19（4）：428-433.］

［19］YANG H B，YAN H S.An adaptive approach to dynamic scheduling in knowledgeable manufacturing cell［J］.International Journal of Advanced Manufacture Technology，2009，42（3／4）：312-320.

［20］WATKINS C，DAYAN P.Q-learning［J］.Machine Learning，1992，8（3／4）：279-292.

［21］AYDIN M E，?ZTEMEL E.Dynamic job-shop scheduling using reinforcement learning Agents［J］.Robotics and Autonomous Systems，2000，33（2）：169-178.

［22］WANG Y C，USHER J M.Application of reinforcement learning for agent based production scheduling［J］.Engineering Applications of Artificial Intelligence，2005，18（1）：73-82.

［23］ZHANG Z C，ZHENG L，LI N.Minimizing mean weighted tardiness in unrelated parallel machine scheduling with reinforcement learning［J］.Computers &Operations Research，2012，39（7）：1315-1324.

［24］YAN Hongsen，LIU Fei.Knowledgeable manufacturing system—a new kind of advanced manufacturing system［J］.Computer Integrated Manufacturing Systems，2001，7（8）：7-11（in Chinese）.［嚴(yán)洪森，劉 飛.知識化制造系統(tǒng)——新一代先進(jìn)制造系統(tǒng)［J］.計(jì)算機(jī)集成制造系統(tǒng)，2001，7（8）：7-11.］