張 琦， 張 彬

（沈陽建筑大學 機械工程學院， 遼寧 沈陽 110168）

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 編碼解碼

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

3.2 粒子的位置更新機制

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

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

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

4 實例仿真與分析

4.1 實例仿真

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

表1 新到達工件

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

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

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

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

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

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

4.2 結(jié)果分析

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

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

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

5 結(jié)論

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