面向作業(yè)車(chē)間重調(diào)度的改進(jìn)合同網(wǎng)機(jī)制研究*

丁彬楚，湯洪濤

（浙江工業(yè)大學(xué) 工業(yè)工程研究所，浙江 杭州 310014）

0 引 言

車(chē)間初始生產(chǎn)調(diào)度方案實(shí)際執(zhí)行時(shí)，會(huì)遇到各種各樣的擾動(dòng)，這些擾動(dòng)會(huì)帶來(lái)重調(diào)度的需求，并且這些擾動(dòng)對(duì)重調(diào)度方法的實(shí)時(shí)性、動(dòng)態(tài)性及其耦合能力都有很高要求?；诙郃gent的調(diào)度技術(shù)采用協(xié)商機(jī)制解決調(diào)度決策中的各類(lèi)沖突，能夠準(zhǔn)確地反映系統(tǒng)的動(dòng)態(tài)重調(diào)度過(guò)程，降低問(wèn)題求解的復(fù)雜性，對(duì)動(dòng)態(tài)的現(xiàn)實(shí)環(huán)境具有良好的靈活性和適應(yīng)性。

現(xiàn)有的協(xié)商機(jī)制中基于合同網(wǎng)（CNP）的協(xié)商機(jī)制最為常用，一般認(rèn)為，合同網(wǎng)協(xié)商機(jī)制具有較好的開(kāi)放性以及動(dòng)態(tài)分配和自然平衡能力。但是，傳統(tǒng)的合同網(wǎng)協(xié)商機(jī)制僅僅規(guī)定單一的工作過(guò)程，本身沒(méi)有優(yōu)化能力和動(dòng)態(tài)學(xué)習(xí)能力，因此具有自學(xué)習(xí)能力的合同網(wǎng)協(xié)商機(jī)制成為了該領(lǐng)域研究的熱點(diǎn)。Csaji等[1]以提高Agent的學(xué)習(xí)能力為目的，提出了基于時(shí)間差分學(xué)習(xí)算法TD(λ)，從而在協(xié)商過(guò)程中獲得更好的投標(biāo)者。Wang和Usher[2-3]為解決動(dòng)態(tài)單機(jī)調(diào)度問(wèn)題中調(diào)度規(guī)則動(dòng)態(tài)優(yōu)化選擇的問(wèn)題，集成了強(qiáng)化學(xué)習(xí)中的Q-學(xué)習(xí)和CNP機(jī)制。王世進(jìn)等[4]在此基礎(chǔ)上，深入探討了集成Q-學(xué)習(xí)和CNP機(jī)制的分布式柔性作業(yè)車(chē)間環(huán)境下作業(yè)動(dòng)態(tài)分配優(yōu)化問(wèn)題，給出了具有針對(duì)性的集成機(jī)制的策略決策過(guò)程和學(xué)習(xí)過(guò)程。Q學(xué)習(xí)能夠使Agent從給定的調(diào)度規(guī)則中選擇出較好的調(diào)度規(guī)則，但是當(dāng)這些啟發(fā)式規(guī)則在學(xué)習(xí)中得不到最優(yōu)解時(shí)，不能及時(shí)得到修正，并且Q學(xué)習(xí)本身無(wú)規(guī)劃能力，不能滿(mǎn)足重調(diào)度需求。張化祥等[5]通過(guò)考慮個(gè)體多步進(jìn)化效果優(yōu)化變異策略的選擇，提出了一種基于Q學(xué)習(xí)的適應(yīng)性進(jìn)化規(guī)劃算法（QEP），用變異策略代替了啟發(fā)式規(guī)則，提供了更多的交互機(jī)會(huì)，使Q學(xué)習(xí)更具有廣泛性。

在以上Q學(xué)習(xí)、QEP等算法的研究基礎(chǔ)上，本研究將其應(yīng)用于動(dòng)態(tài)重調(diào)度問(wèn)題的研究，并引入滾動(dòng)窗口技術(shù)改進(jìn)QEP算法，提出集成QEP和CNP的協(xié)商機(jī)制，以實(shí)現(xiàn)柔性作業(yè)車(chē)間動(dòng)態(tài)重調(diào)度過(guò)程。

1 重調(diào)度假設(shè)及目標(biāo)

本研究中的動(dòng)態(tài)重調(diào)度針對(duì)的對(duì)象為柔性作業(yè)車(chē)間，給出假設(shè)條件如下：

（1）各設(shè)備同一時(shí)刻只能加工一個(gè)工件；

（2）工件在設(shè)備上的加工時(shí)間已知；

（3）正在加工的工件不進(jìn)行重調(diào)度；

（4）調(diào)度過(guò)程中除設(shè)備以外的其他資源充足，無(wú)需調(diào)度。

重調(diào)度的目標(biāo)描述如下：首先，仍應(yīng)盡量保證原調(diào)度方案的優(yōu)化目標(biāo)，即最大完成時(shí)間最?。黄浯?，在實(shí)際的生產(chǎn)過(guò)程中，調(diào)度系統(tǒng)總體上是按照初始調(diào)度方案準(zhǔn)備調(diào)度所需加工工具和材料，當(dāng)調(diào)度方案改變時(shí)，勢(shì)必會(huì)造成這些工具和材料的運(yùn)輸和浪費(fèi)，所以重調(diào)度產(chǎn)生的調(diào)度方案應(yīng)盡量減少與當(dāng)前調(diào)度方案的差異，即最小化與重調(diào)度前調(diào)度方案的背離。

對(duì)于多目標(biāo)的求解方式主要有3種：決策先于優(yōu)化、決策與優(yōu)化交替以及優(yōu)化先于決策[6-7]。本研究采用傳統(tǒng)的決策先于優(yōu)化的方式，給出重調(diào)度目標(biāo)函數(shù)數(shù)學(xué)表達(dá)式如下：

式中：m—作業(yè)車(chē)間設(shè)備數(shù)量，n—調(diào)度工件數(shù)，ni—工件i的工序數(shù)，F(xiàn)h—設(shè)備h完成所有任務(wù)的時(shí)間，Sij—工件i第j道工序重調(diào)度前的開(kāi)工時(shí)間，S′ij—重調(diào)度后開(kāi)工時(shí)間。

2 改進(jìn)QEP重調(diào)度算法

本研究給出的調(diào)度目標(biāo)重點(diǎn)在于吸收和修復(fù)動(dòng)態(tài)事件對(duì)調(diào)度的影響，因此筆者引入滾動(dòng)窗口重調(diào)度技術(shù)。滾動(dòng)窗口技術(shù)的應(yīng)用可以減少動(dòng)態(tài)重調(diào)度涉及的對(duì)象，縮小問(wèn)題求解的規(guī)模[8]，并將該技術(shù)集成到QEP算法中，使算法在求解重調(diào)度問(wèn)題時(shí)具有合理的規(guī)劃性，避免盲目進(jìn)化，提高進(jìn)化效率。

改進(jìn)QEP算法流程設(shè)計(jì)如圖1所示。

圖1 改進(jìn)QEP算法流程

2.1 滾動(dòng)窗口初始化及更新設(shè)計(jì)

當(dāng)生產(chǎn)過(guò)程中有擾動(dòng)事件發(fā)生時(shí)，某工件當(dāng)前加工工序受到影響,并且由于該工件受到工序約束和設(shè)備約束，影響會(huì)進(jìn)一步擴(kuò)散，即重調(diào)度的擴(kuò)散效應(yīng)[9]。研究者通常采用二維分支樹(shù)（即工件分支和設(shè)備分支）來(lái)描述該擴(kuò)散過(guò)程。滾動(dòng)窗口初始化和更新建立在這種擴(kuò)散過(guò)程的基礎(chǔ)上。

針對(duì)3種常見(jiàn)擾動(dòng)事件，滾動(dòng)窗口初始化方法為：

（1）加工延遲。初始滾動(dòng)窗口為延遲工件兩分支上的工單；

（2）設(shè)備故障。初始滾動(dòng)窗口為故障設(shè)備故障時(shí)間內(nèi)待加工工單，如果設(shè)備故障時(shí)間未知，則表示為故障設(shè)備上所有工單；

（3）故障恢復(fù)。初始滾動(dòng)窗口為所有可在該設(shè)備上加工的工單，已完工和正在加工的工單除外，同時(shí)滾動(dòng)窗口內(nèi)工單按照開(kāi)工時(shí)間的先后順序進(jìn)行排列。

本研究設(shè)計(jì)了局部和全局兩種滾動(dòng)窗口更新方法。局部更新是針對(duì)某一工單進(jìn)行更新、整合，步驟如下：

（1）以更新的工單為根節(jié)點(diǎn)，將工件分支和設(shè)備分支上的工單加入滾動(dòng)窗口并刪除更新的工單；

（2）去除滾動(dòng)窗口中重復(fù)的、無(wú)延遲發(fā)生的工單；

（3）按照工單開(kāi)工時(shí)間的先后順序進(jìn)行排序。

全局更新是針對(duì)滾動(dòng)窗口內(nèi)所有工單進(jìn)行更新、整合，步驟如下：

（1）根據(jù)當(dāng)前滾動(dòng)窗口，將各工單工件分支和設(shè)備分支上的工單作為當(dāng)前滾動(dòng)窗口，替換原滾動(dòng)窗口，在二維分支樹(shù)上表示為下一層的工單集；

步驟（2）、（3）同局部更新。

2.2 進(jìn)化分析

Q學(xué)習(xí)通過(guò)選擇最大化Agent帶折扣累積收益的行動(dòng)，可以學(xué)習(xí)到Agent的最優(yōu)行動(dòng)集。進(jìn)化過(guò)程中，研究者若把個(gè)體變異策略看成行動(dòng)，則個(gè)體選擇最優(yōu)變異策略就轉(zhuǎn)化為Agent選擇最優(yōu)行動(dòng)，在選擇最優(yōu)行動(dòng)時(shí)考慮行動(dòng)的立即及多步滯后收益，即計(jì)算折扣累計(jì)收益。

本研究假設(shè)個(gè)體進(jìn)化步長(zhǎng)為m(m>1)，即考慮m-1步滯后收益，個(gè)體開(kāi)始選擇變異策略為a，可以計(jì)算個(gè)體采用行動(dòng)a時(shí)的收益為：

式中：r(a)—個(gè)體采用變異策略a的立即收益，此時(shí)個(gè)體進(jìn)化了一次。

新生成的個(gè)體采用a(1)生成新個(gè)體，此時(shí)收益記為Q(a(1))，依次類(lèi)推，m-1次進(jìn)化后，新生成的個(gè)體采用a(m-1)生成新個(gè)體，此時(shí)收益記為Q(a(m-1))。式（2）為個(gè)體采用a，a(1)，…，a(m-1)變異策略集的累計(jì)收益。定義個(gè)體立即收益r(a)=fp(a)-fo(a)。其中：fp(a)—父代個(gè)體對(duì)應(yīng)的適應(yīng)度值，fo(a)—采用變異策略a后生成的子代個(gè)體對(duì)應(yīng)的適應(yīng)度值。適應(yīng)度函數(shù)計(jì)算公式如下：

其中，函數(shù)f1，f2已在公式（1）中給出。本研究將立即收益代入式（3），得到Q值的計(jì)算公式為：

2.3 改進(jìn)Q學(xué)習(xí)過(guò)程設(shè)計(jì)

在Q學(xué)習(xí)過(guò)程中，為保證滯后收益對(duì)Q(a)的有效性，本研究針對(duì)每個(gè)個(gè)體分配了一個(gè)臨時(shí)滾動(dòng)窗口。

個(gè)體Q學(xué)習(xí)流程設(shè)計(jì)如圖2所示。

Step1：獲取臨時(shí)滾動(dòng)窗口，設(shè)置進(jìn)化代數(shù)t=2；如果臨時(shí)滾動(dòng)窗口為空，轉(zhuǎn)入step5；

圖2 Q學(xué)習(xí)流程圖

Step2：遍歷臨時(shí)滾動(dòng)窗口中每一個(gè)工單，采用Boltzmann選擇每一個(gè)工單對(duì)應(yīng)工序的變異策略；Boltzmann分布計(jì)算變異策略被保留下來(lái)的概率為：

式中：n—工序變異產(chǎn)生的后代個(gè)數(shù)；α—調(diào)節(jié)系數(shù)，α∈(0,1)；T0—初始溫度。

在Q學(xué)習(xí)的初始階段，溫度參數(shù)T設(shè)置較高，系統(tǒng)探索未嘗試的動(dòng)作（選擇非最優(yōu)變異策略），以獲得更多回報(bào)的機(jī)會(huì)；在Q學(xué)習(xí)的后期，筆者設(shè)置較低的溫度參數(shù)，使系統(tǒng)傾向于利用當(dāng)前最優(yōu)的變異策略。

Step3：采用全局更新的方法更新臨時(shí)滾動(dòng)窗口，同時(shí)設(shè)置進(jìn)化代數(shù)加1；

Step4：判斷t是否大于m，或者臨時(shí)滾動(dòng)窗口為空；滿(mǎn)足條件則轉(zhuǎn)step5；不滿(mǎn)足則轉(zhuǎn)step2；

Step5：計(jì)算個(gè)體的Q值，Q學(xué)習(xí)結(jié)束。

以下給出m=2時(shí)的Q學(xué)習(xí)過(guò)程示意圖：

圖3 Q學(xué)習(xí)過(guò)程示意圖

2.4 變異策略

基于文獻(xiàn)[10]的研究，本研究給出以下變異策略：

（1）工序所用設(shè)備不變，加工順序不變，只是調(diào)整各個(gè)工序的開(kāi)始時(shí)間和結(jié)束時(shí)間，記為“設(shè)備不變，順序不變”；

（2）工序所用設(shè)備不變，但在設(shè)備內(nèi)的加工順序可以調(diào)整，記為“設(shè)備不變，順序可變”；

（3）工序使用設(shè)備發(fā)生變化，插入到并行設(shè)備加工列表中，記為“設(shè)備可變，順序可變”。

3 集成QEP的改進(jìn)合同網(wǎng)協(xié)商機(jī)制

擾動(dòng)事件發(fā)生時(shí)，集成QEP的合同網(wǎng)機(jī)制協(xié)商過(guò)程如圖4所示。其基本交互過(guò)程發(fā)生在工序Agent（PA）和設(shè)備Agent（MA）之間。

圖4 QEP-CNP協(xié)商流程圖

基本流程描述如下：

Step1：初始化滾動(dòng)窗口；

Step2：獲取滾動(dòng)窗口中的第一個(gè)工單，生成相應(yīng)的工序Agent（PA），解除原先合約，并獲取調(diào)度需要的相關(guān)信息，包括加工時(shí)間、可加工設(shè)備、設(shè)備上的工單列表等；

Step3：PA向能夠加工它的設(shè)備發(fā)送招標(biāo)請(qǐng)求；

Step4：設(shè)備Agent（MA）作為投標(biāo)方進(jìn)行Q學(xué)習(xí)，根據(jù)工件平均背離、總完成時(shí)間和設(shè)備負(fù)載等生成多份標(biāo)書(shū)，向PA發(fā)送應(yīng)標(biāo)信息；

Step5：PA評(píng)價(jià)各MA發(fā)回的投標(biāo)書(shū)，選擇中標(biāo)的MA和最優(yōu)變異（最大Q值），更新調(diào)度方案；兩份標(biāo)書(shū)評(píng)價(jià)值相等時(shí)，根據(jù)設(shè)備負(fù)載，選擇負(fù)載小的MA和最優(yōu)變異策略；

Step6：采用局部更新方法更新滾動(dòng)窗口；

Step7：判斷滾動(dòng)窗口是否為空；否，轉(zhuǎn)Step2；是，協(xié)商結(jié)束，輸出調(diào)度方案。

4 仿真實(shí)驗(yàn)

本研究將文獻(xiàn)[11]給出的10×10標(biāo)準(zhǔn)算例調(diào)度最優(yōu)解作為初始調(diào)度解，其甘特圖如圖5所示。筆者針對(duì)表1給出的動(dòng)態(tài)事件進(jìn)行重調(diào)度仿真。

圖5 10×10甘特圖（最短加工時(shí)間：t=7 s）

表1 動(dòng)態(tài)事件表

動(dòng)態(tài)重調(diào)度算法選擇參數(shù)如下：完成時(shí)間權(quán)重為0.8，工時(shí)偏差權(quán)重為0.2，進(jìn)化步長(zhǎng)為2，變溫調(diào)節(jié)系數(shù)為0.8，初始溫度為10。由于重調(diào)度協(xié)商過(guò)程中工件和設(shè)備目標(biāo)明確，容易達(dá)成一致，直接受影響的工件重調(diào)度所需要的時(shí)間可以忽略。

本研究通過(guò)仿真得到3個(gè)時(shí)刻重調(diào)度后的甘特圖如圖6所示。

本研究將改進(jìn)的合同網(wǎng)協(xié)商機(jī)制與基本合同網(wǎng)協(xié)商機(jī)制相比，得到的仿真結(jié)果如表2所示。通過(guò)對(duì)比可以看出，改進(jìn)的合同網(wǎng)協(xié)商機(jī)制具有較好的全局優(yōu)化性能。

表2 仿真結(jié)果表

5 結(jié)束語(yǔ)

圖6 動(dòng)態(tài)重調(diào)度甘特圖

本研究針對(duì)面向作業(yè)車(chē)間重調(diào)度問(wèn)題的改進(jìn)合同網(wǎng)協(xié)商機(jī)制進(jìn)行了研究，設(shè)計(jì)了改進(jìn)的QEP算法，提出了集成QEP和合同網(wǎng)的協(xié)商機(jī)制。該協(xié)商機(jī)制具有良好的反應(yīng)能力和全局優(yōu)化性能，但同時(shí)也存在如下問(wèn)題：

首先，針對(duì)多目標(biāo)問(wèn)題，研究者在設(shè)計(jì)目標(biāo)函數(shù)時(shí)采用簡(jiǎn)單的加權(quán)法雖然提高了系統(tǒng)的反應(yīng)能力，但是在一定程度上削弱了系統(tǒng)的優(yōu)化能力；

其次，通過(guò)集成改進(jìn)的QEP算法和合同網(wǎng)，雖然使得多Agent具有一定的自學(xué)習(xí)能力，但出于系統(tǒng)時(shí)間性能的考慮，簡(jiǎn)化了Q學(xué)習(xí)每一步的進(jìn)化操作，并且算法中的變異策略冗余度較高，未能做出有效優(yōu)化。后續(xù)研究將從這幾方面進(jìn)一步改善合同網(wǎng)機(jī)制。

（References）：

[1] CSAJI B，MONOSTORI L，KADAR B.Reinforcement learn?ing in a distributed market-based production control system[J].Advanced Engineering Informatics，2006，20（3）：279-288.

[2] WANG Y，USHER J.Application of reinforcement learning for agent-based production scheduling[J].Engineering Applications of Artificial Intelligence，2005，18（1）：73-82.

[3] WANG Y，USHER J.A reinforcement learning approach for development routing policies in multi-agent production scheduling[J].The International Journal of Advanced Manufacturing Technology，2007，33（3/4）：323-333.

[4] 王世進(jìn).面向制造任務(wù)動(dòng)態(tài)分配的改進(jìn)合同網(wǎng)機(jī)制[J].計(jì)算機(jī)集成制造系統(tǒng)，2011（6）：1257-1263.

[5] 張化祥，陸 晶.基于Q學(xué)習(xí)的適應(yīng)性進(jìn)化規(guī)劃算法[J].自動(dòng)化學(xué)報(bào)，2008（7）：819-822.

[6] 陳 宇.不確定環(huán)境下的多Agent魯棒性生產(chǎn)調(diào)度研究[D].廣州：廣東工業(yè)大學(xué)自動(dòng)化學(xué)院，2009.

[7] 崔遜學(xué).多目標(biāo)進(jìn)化及其應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2006.

[8] 邵斌彬.柔性制造動(dòng)態(tài)多目標(biāo)調(diào)度模型在MES中的研究與應(yīng)用[D].上海：上海交通大學(xué)軟件學(xué)院，2008.

[9] MARLER R，ARORA J.survey of multi-objective optimiza?tion methods for engineering[J].Structural and Multidis?ciplinary Optimization，2004，26（6）：369-395.

[10] 丁 雷，王愛(ài)民，寧汝新.工時(shí)不確定條件下的車(chē)間作業(yè)調(diào)度技術(shù)[J].計(jì)算機(jī)集成制造系統(tǒng)，2010（1）：98-108.

[11] 李修琳，魯建廈，柴國(guó)鐘，等.混合蜂群算法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題[J].計(jì)算機(jī)集成制造系統(tǒng)，2011（7）：1495-1500.