張 琦， 張 彬

（沈陽(yáng)建筑大學(xué) 機(jī)械工程學(xué)院， 遼寧 沈陽(yáng) 110168）

0 引言

柔性作業(yè)車間調(diào)度問題 （flexible job-shop problem，F(xiàn)JSP）是目前最常見的車間調(diào)度類型。而在實(shí)際的生產(chǎn)制造車間中，在加工過程中會(huì)出現(xiàn)多種突發(fā)的動(dòng)態(tài)事件，如人員短缺、交貨期提前、設(shè)備損壞、緊急插單、生產(chǎn)材料短缺等事件的發(fā)生。 并且突發(fā)事件在現(xiàn)代生產(chǎn)車間中發(fā)生概率越來越高，因此對(duì)于動(dòng)態(tài)環(huán)境下的FJSP 問題研究有著極其重要的意義。

近年來動(dòng)態(tài)環(huán)境下的FJSP 問題的研究成為了熱點(diǎn)。文獻(xiàn)[1]針對(duì)帶有設(shè)備故障的動(dòng)態(tài)調(diào)度問題，其提出了一種兩階段的粒子群算法。 文獻(xiàn)[2]針對(duì)動(dòng)態(tài)環(huán)境下的FJSP問題， 提出了一種滾動(dòng)窗口與模擬退火算法相結(jié)合的求解方法。 文獻(xiàn)[3]針對(duì)設(shè)備故障，新工件的到達(dá)兩類動(dòng)態(tài)時(shí)間的發(fā)生，提出了一種混合重調(diào)度策略，并通過改進(jìn)多差分進(jìn)化算法對(duì)其進(jìn)行求解。 文獻(xiàn)[4]提出了一種雙層深度Q 網(wǎng)絡(luò)的在線重調(diào)度方法，來解決帶有新工件到達(dá)的動(dòng)態(tài)FJSP 問題，并通過與現(xiàn)有的調(diào)度規(guī)則和調(diào)度方法進(jìn)行了比較，驗(yàn)證了該方法的通用性。 文獻(xiàn)[5]針對(duì)作業(yè)取消、新工件到達(dá)、設(shè)備發(fā)生故障、工作時(shí)間變化的四種情況，提出了一種基于蒙特卡洛樹搜索算法的重調(diào)度方法，來解決該動(dòng)態(tài)環(huán)境下的FJSP 問題。 文獻(xiàn)[6]通過將遺傳算法與集成仿真相融合的方法對(duì)有生設(shè)備故障事件發(fā)生的動(dòng)態(tài)環(huán)境下調(diào)度問題進(jìn)行求解。

綜上所述， 目前針對(duì)動(dòng)態(tài)環(huán)境下的FJSP 問題研究，多數(shù)學(xué)者針對(duì)設(shè)備故障和新工件到達(dá)， 這兩類動(dòng)態(tài)事件的動(dòng)態(tài)調(diào)度進(jìn)行研究， 同時(shí)這兩類事件是生產(chǎn)車間中最為常見的事件， 因此本文針對(duì)這兩類動(dòng)態(tài)事件提出了一種基于改進(jìn)離散粒子算法的動(dòng)態(tài)調(diào)度方法。

1 動(dòng)態(tài)柔性作業(yè)車間調(diào)度數(shù)學(xué)建模

1.1 動(dòng)態(tài)柔性作業(yè)車間調(diào)度問題描述

動(dòng)態(tài)柔性作業(yè)車間調(diào)度問題（Dynamic flexible job shop scheduling problem，DFJSP）可描述為：有n 個(gè)待加工工件，可在m 臺(tái)設(shè)備上加工。 所有工件的各條工藝路線已知并且唯一。 車間生產(chǎn)是一個(gè)動(dòng)態(tài)的環(huán)境，生產(chǎn)訂單也不是連續(xù)性的到達(dá)。 本文對(duì)實(shí)際加工過程中新工件到達(dá)、加工設(shè)備故障兩類動(dòng)態(tài)事件的處理，當(dāng)動(dòng)態(tài)發(fā)生時(shí)，要對(duì)現(xiàn)有調(diào)度方案進(jìn)行及時(shí)合理調(diào)整，即根據(jù)現(xiàn)有系統(tǒng)狀態(tài)，進(jìn)行設(shè)備再分配以及工序再排序， 以使現(xiàn)有方案與新方案有序銜接在滿足約束條件的情況下，優(yōu)化某些性能指標(biāo)。動(dòng)態(tài)柔性作業(yè)車間調(diào)度需滿足以下約束條件： 同一工件的各道加工工序之間有著明確的加工順序； 各不同工件的工序無(wú)先后順序；在一段時(shí)間內(nèi)一臺(tái)設(shè)備只加工一個(gè)工序；工件開始加工，無(wú)法中斷；每道工序只能在設(shè)備上加工一次；在加工設(shè)備發(fā)生故障時(shí)，正在該設(shè)備上加工的工序可以中斷；若因設(shè)備故障而重調(diào)度時(shí)，在該設(shè)備上正加工的工件，需重新進(jìn)行加工。

1.2 動(dòng)態(tài)柔性作業(yè)車間調(diào)度問題數(shù)學(xué)模型

上述由n 個(gè)待加工工件和m 臺(tái)可選加工設(shè)備組成的動(dòng)態(tài)FJSP，優(yōu)化目標(biāo)為最大完工時(shí)間，數(shù)學(xué)模型如下：

式中：M={Mh｜1≤h≤m}表示設(shè)備集合；J={Ji｜1≤i≤n}表示工 件 集 合；Ci表 示 工 件Ji的 完 工 時(shí) 間；O={Oij｜1≤i≤ni}表示工件的工序Oij集合；Mij={Mh｜Xijh=1}表示工序Oij的可選設(shè)備集；Tijh，Tijs表示工序在設(shè)備上的加工時(shí)間；Sijh，Segs表示工序Oij在設(shè)備Mh，Ms上的加工開始時(shí)間；Eijh，Eegs表示工序Oij，Oeg在設(shè)備Mh，Ms上的加工結(jié)束時(shí)間；Xijh=1 表示工序Oij在設(shè)備Mh上加工；Yijegh=1 表示工序Oij優(yōu)于工序Oeg進(jìn)行加工；TD表示重調(diào)度時(shí)刻。 式（1）為最小化最大完工時(shí)間；式（2）為同工件的不同工序有先后順序；式（3）為工序在加工中，不能停止；式（4）為在任一時(shí)刻，在各臺(tái)設(shè)備上只能加工一道工序；式（5）表示在重調(diào)度時(shí)刻，工序正在加工，設(shè)備需進(jìn)行調(diào)整方式。

2 動(dòng)態(tài)調(diào)度策略

本文選取基于周期性與事件驅(qū)動(dòng)的混合重調(diào)度策略與滾動(dòng)窗口技術(shù)對(duì)動(dòng)態(tài)FJSP 問題進(jìn)行處理。 對(duì)于加工設(shè)備損壞和新工件到達(dá)的情況， 應(yīng)用基于事件驅(qū)動(dòng)的重調(diào)度策略能夠快速反應(yīng)并給出新的調(diào)度方案。 對(duì)于在一段時(shí)間內(nèi)沒有動(dòng)態(tài)事件發(fā)生的情況， 通過周期性重調(diào)度策略預(yù)先避免動(dòng)態(tài)事件對(duì)生產(chǎn)加工的影響。

（1）設(shè)備故障處理策略。 在實(shí)際生產(chǎn)車間中，生產(chǎn)設(shè)備故障不可避免。 因此， 為確保生產(chǎn)任務(wù)的正常有序執(zhí)行，必須進(jìn)行再調(diào)度。 當(dāng)加工設(shè)備發(fā)生故障時(shí)，將該設(shè)備上的后續(xù)工序， 安排至后續(xù)工序的其他可選設(shè)備上進(jìn)行加工。對(duì)變化后的工序進(jìn)行重調(diào)度，從而整個(gè)生產(chǎn)過程得到優(yōu)化。 當(dāng)此設(shè)備故障修復(fù)后再將該設(shè)備重新列入到各個(gè)工件各道工序的可選設(shè)備集中， 再對(duì)所有工件的后續(xù)工序進(jìn)行重調(diào)度。

（2）新工件到達(dá)處理策略。在動(dòng)態(tài)柔性作業(yè)車間調(diào)度的環(huán)境下，新工件到達(dá)的情況時(shí)有發(fā)生。新工件到達(dá)情況的發(fā)生時(shí)，不立即進(jìn)行重調(diào)度，而是等待重調(diào)度周期的到達(dá)在進(jìn)行重調(diào)度。

3 離散粒子群算法設(shè)計(jì)

3.1 編碼解碼

柔性作業(yè)車間調(diào)度問題涉及工序以及該工序的生產(chǎn)設(shè)備分配，所以本文采用設(shè)備選擇基于工序順序的整數(shù)編碼[7]。

3.2 粒子的位置更新機(jī)制

本文對(duì)文獻(xiàn)[8]中的粒子位置的更新公式進(jìn)行了重新設(shè)計(jì)，使算法更適用于求解FJSP。 本文在此基礎(chǔ)上，離散粒子群算法的更新方式進(jìn)行設(shè)計(jì)，位置更新公式如下：

式中：ωt—慣性權(quán)重；C1—自我認(rèn)知系數(shù)；C2—社會(huì)系數(shù)；—個(gè)體最優(yōu)值；gBt—全局最優(yōu)值；h（）—對(duì)粒子執(zhí)行擾動(dòng)操做。

公式（6）分為三部分，第一部分函數(shù)h（Xit）的作用為交換Xit中的分量（相當(dāng)于粒子的飛行速度），粒子的速度變化包含粒子Xit的變化中。 此部分的更新應(yīng)用了的變異操作來對(duì)其進(jìn)行更新操作。 設(shè)備部分采用采用隨機(jī)變異操作，工序部分采用插入式變異操作，以避免非法解的產(chǎn)生，同時(shí)減少了算法的運(yùn)算時(shí)間。第二部分函數(shù)反映了對(duì)自身信息的繼承，粒子與個(gè)體最優(yōu)pBit進(jìn)行交叉操作，工序部分采用文獻(xiàn)[9]提出的IPOX 交叉操作。 設(shè)備部分采用均勻交叉的方式。 第三部分函數(shù)反映了粒子向全局最優(yōu)粒子gBt的信息進(jìn)行學(xué)習(xí)。其執(zhí)行過程與第二部分函數(shù)執(zhí)行過程相同。

4 實(shí)例仿真與分析

4.1 實(shí)例仿真

為了驗(yàn)證本章所提方法的有效性，在文獻(xiàn)[10]中的案例基礎(chǔ)上，依據(jù)實(shí)際加工車間中的加工環(huán)境，增加了設(shè)備故障、新工件到達(dá)兩類動(dòng)態(tài)事件的數(shù)據(jù)，并對(duì)各動(dòng)態(tài)數(shù)據(jù)分別進(jìn)行優(yōu)化調(diào)度。 表1 中給出了1 個(gè)新到工件的可選加工設(shè)備以及對(duì)應(yīng)的加工時(shí)間。

表1 新到達(dá)工件

（1）案例初始調(diào)度方案求解。 實(shí)際案例，利用本文所提的離散粒子群算法對(duì)該實(shí)際案例進(jìn)行初始調(diào)度， 所求得初始調(diào)度方案如圖1 所示，。 其中最大完工時(shí)間為43。在后面的動(dòng)態(tài)調(diào)度時(shí)將該方案作為初始方案。

圖1 動(dòng)態(tài)調(diào)度方案甘特圖

（2）設(shè)備故障重調(diào)度。假設(shè)設(shè)備M4 在時(shí)刻30 時(shí)損壞，并且無(wú)法快速地進(jìn)行修復(fù)，因此需進(jìn)行重調(diào)度，設(shè)備故障重調(diào)度方案甘特圖，如圖2 所示。

圖2 設(shè)備故障重調(diào)度方案甘特圖

（3）在初始調(diào)度方案的執(zhí)行過程中，在時(shí)刻17 有一個(gè)新工件到達(dá)，并且在時(shí)刻18 時(shí)，到達(dá)周期性重調(diào)度時(shí)刻，進(jìn)行重調(diào)度，新工件達(dá)到重調(diào)度方案甘特圖，如圖3 所示。

圖3 新工件達(dá)到重調(diào)度方案甘特圖

4.2 結(jié)果分析

通過分別對(duì)設(shè)備故障、 新工件到達(dá)兩類突發(fā)動(dòng)態(tài)事件的仿真調(diào)度試驗(yàn)研究， 在仿真實(shí)驗(yàn)結(jié)果中能夠得出以下結(jié)論：

（1）應(yīng)用基于周期性與事件驅(qū)動(dòng)的混合重調(diào)度策略與滾動(dòng)窗口技術(shù)對(duì)動(dòng)態(tài)FJSP 求解，所求調(diào)度方案能夠滿足復(fù)雜多變的動(dòng)態(tài)生產(chǎn)環(huán)境要求。因此，該方法能夠解決動(dòng)態(tài)車間調(diào)度問題。

（2）當(dāng)發(fā)生突發(fā)動(dòng)態(tài)事件后求得的重調(diào)度結(jié)果中，其完工時(shí)間均保持在合理可行的范圍內(nèi)， 其證明離散粒子群算法是求解動(dòng)態(tài)環(huán)境下柔性作業(yè)車間調(diào)度方案的一種可行方法。

5 結(jié)論

針對(duì)動(dòng)態(tài)環(huán)境下的FJSP 問題，首先建立了該問題數(shù)學(xué)模型， 并針對(duì)問題提出了一種基于改進(jìn)離散粒子群算法的動(dòng)態(tài)調(diào)度方法。 該方法結(jié)合滾動(dòng)窗口策略以及基于周期性與事件驅(qū)動(dòng)的混合重調(diào)度策略， 以適應(yīng)動(dòng)態(tài)環(huán)境下的FJSP 問題， 并通過對(duì)兩類突發(fā)動(dòng)態(tài)事件的仿真實(shí)驗(yàn)，證明了本文所提的方法對(duì)求解動(dòng)態(tài)環(huán)境下的FJSP 問題的可行性。