動態(tài)環(huán)境下的柔性作業(yè)車間調度問題研究

張 琦， 張 彬

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

3 離散粒子群算法設計

3.1 編碼解碼

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

3.2 粒子的位置更新機制

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

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

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

4 實例仿真與分析

4.1 實例仿真

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

表1 新到達工件

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

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

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

圖2 設備故障重調度方案甘特圖

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

圖3 新工件達到重調度方案甘特圖

4.2 結果分析

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

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

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

5 結論

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