基于關鍵鏈的需求視窗技術在柔性車間調度中的應用

代大齊

摘 要：針對柔性車間調度問題，運用需求視窗來表征其加工環境的模糊性及市場需求，并建立滿意度函數，作為車間調度模型的目標函數。為了應對調度過程的復雜性，運用多色集合建立基本信息約束圍道矩陣來改進遺傳算法，結合關鍵鏈，提出基于關鍵鏈的需求視窗技術。通過仿真實例驗證了給出的調度方法的可行性和有效性。

關鍵詞：柔性車間調度;關鍵鏈;需求視窗;遺傳算法

中圖分類號：TH165文獻標識碼：A文章編號：1003-5168（2020）04-0033-03

Abstract： Aiming at the flexible job-shop scheduling problem， fuzzy working environment and market demand about flexible job-shop were described by demand time window， and the satisfaction function was established as the objective function of the shop scheduling model. In order to solve the complexity of scheduling， Polychromatic Sets were used to build constraint contour matrix so that the genetic algorithm was improved. Combined with critical chain， a method of demand time window based on critical chain was proposed. The effectiveness and feasibility of this scheduling method were validated by simulation experiments.

Keywords： flexible job-shop;scheduling critical chain;demand time window;genetic algorithm

生產車間調度問題是公認的強NP-hard[1]問題，具有重要的實際意義和理論價值。柔性作業車間調度問題（Flexible Job-Shop Scheduling Problem，FJSP）的研究擴展了經典作業調度，是當前車間調度問題研究的熱點之一[2]。通過相關算法及改進算法解決調度問題是較為常用的一種手段[3-5]。趙詩奎提出一種融合改進鄰域結構的混合算法[6]，石小秋等提出遺傳雜草算法[7]等用于柔性車間調度。目前，在對FJSP的研究上，單一調度的針對性應用研究較多，而對于FJSP的復雜性，大多沒有進行有效的分類、簡化處理，且優化出的調度方案通用性、實用性不強。

本文在分析柔性調度技術、方法的基礎上，結合實際情況，運用關鍵鏈簡化復雜的FJSP系統，以控制視窗建立針對模糊環境的滿意度函數，將關鍵鏈和需求視窗技術相結合，并運用多色集合（Polychromatic Sets，PS）[8-9]建立基本信息圍道矩陣改進遺傳算法來解決柔性車間的調度問題。

1 調度關鍵鏈的確立

在調度中存在眾多加工瓶頸，瓶頸因素[10]就組成了關鍵鏈條[11-12]。其中有兩個重要約束：一是機械約束，即關鍵設備;二是時間約束，即關鍵時序。

2 需求視窗與滿意度函數

需求視窗也叫需求時間窗，是就一個時間段進行控制，要求做到準時交貨，是時間上的交貨寬放域。若[ri和rj]分別表示需求期望上界和下界，那么需求視窗[Wt=ri-rj]，以[ti]表示完工時間，則期望函數[hi（ti）]（滿意度函數）可以表示為：

有時調度關鍵鏈有多條，那么滿意度函數為（2）式，也是目標函數。

3 仿真實例

某柔性車間，生產5種產品，其加工工序時間如表1所示。

表1中，括號外為實際加工時間，括號內為加工的上下界時間，也可看作是市場期望的正常的加工時間及期望的下界和上界，當然也可以看作是實際生產車間的模糊加工環境。

本例從機械設備和時間約束綜合考慮確定調度關鍵為設備M3#和M2#，并組成關鍵鏈，即M3#→M2#，關鍵鏈組成為2臺設備，條數只有一條。運用PS理論建立約束圍道矩陣以有利于最優解的生成，PS建立的是基于基本信息的圍道約束矩陣，由實際的柔性車間的基本信息生成。

在遺傳算法的編碼上采用工序編碼，種群大小設為10，交叉率為0.3，變異率為0.08，最大進化代數設為200。運行后獲得如圖1和圖2所示的結果。

圖2為調度方案，1-1表示第一個工件的第一道工序，對應長度為加工時長，相同工件為同一個顏色，其他類推。

4 實例分析

采用的是5×5×5案例，即5種類型的工件，工序數最大的為5道工序，在5臺設備上加工。與普通車間調度的區別是，該調度車間為柔性車間，設備都具備多工序加工能力，屬于多功能機床，如機床M3#具備11道工序的加工能力。實例中柔性加工車間調度問題具有代表性，解決方案的最終運行結果也是有效、可行的。

實例中的不足是多功能機床局限于獨占性約束，即每臺設備同一時間只具備一道工序的加工能力，不具備同時多道工序的加工能力。在柔性加工車間中，如果有同時性工序加工能力的加工中心類機床存在時，即假設在實例中M3#具備某2道工序的同時加工能力，問題的解決辦法是：在圍道矩陣中添加一臺具備該工序加工能力的虛擬設備，變成6臺設備的形式來解決問題，即5×5×6。

在關鍵鏈技術的運用上，本例僅選擇了綜合優先級高的M2#、M3#機床組成關鍵鏈，這是由于實例中加工機床、工序數目較少，無須挑選更多關鍵設備或工序組建關鍵鏈。當遇見較為復雜的柔性車間時，關鍵鏈可以更長、更多。在運用時，人的因素尤為重要，人需要結合實際情況在關鍵鏈長短、條件上進行適當判別。

實例主要基于M3#、M2#這兩臺關鍵機床的市場需求（同時也可以看成是模糊性加工環境或人為意愿要求）進行優化，其關注點側重于解決確立出來的關鍵機床。從運行結果來看，在經過近80代的迭代后，這兩臺機床的平均滿意度達到了66%的最高值，滿足了市場對關鍵機床的期望。

5 結論

通過仿真實例說明了采用基于關鍵鏈技術的需求視窗在柔性車間調度中應用的可行性。同時還應看到的是，以結合需求視窗滿意度為目標函數的調度，調度結果是根據市場需求或模糊加工環境得出的，更能反映柔性車間生產的實際情況，調度更具有實際意義。

參考文獻：

[1]Demir Y，Isleyen S K. Evaluation of mathematical models for flexible job-shop scheduling problems [J]. Applied Mathematical Modeling，2013（3）：977-988.

[2]Zribi N，Kacem I，Karnel A E. Assignment and scheduling in flexible job-shops by hierarchical optimization[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part C （Applications and Reviews），2007（4）：652-661.

[3]彭乘風，陳慶新，毛寧，等.具有無序工序生產特征的混合柔性 流水車間在線調度[J].計算機集成制造系統，2019（11）：2775-2787.

[4]Chaudhy I. Job shop scheduling problem with alternative machines using genetic algorithms [J]. Journal of central south university，2012（5）：1322-1333.

[5]吳銳，郭順生，李益兵，等.改進人工蜂群算法求解分布式柔性作業車間調度問題[J].控制與決策，2019（12）：2527-2536.

[6]趙詩奎.柔性作業車間調度的改進鄰域結構混合算法[J].計算機集成制造系統，2018（12）：3060-3072.

[7]石小秋，李炎炎，鄧丁山，等.基于自適應變級遺傳雜草算法的FJSP研究[J].機械工程學報，2019（6）：223-232.

[8]王崴，馬躍，徐浩，等.基于多色集合理論的螺栓裝配工藝建模方法[J].計算機集成制造系統，2014（20）：1851-1858.

[9]傅衛平，劉冬梅，來春為，等.基于多色集合的改進遺傳算法求解多品種柔性調度問題[J].計算機集成制造系統，2011（5）：1004-1010.

[10]劉明周，凌琳，唐娟.基于漂移瓶頸的制造車間生產批量/提前期研究[J].中國機械工程，2013（2）：220-225.

[11]謝志強，楊靜，周勇，等.基于工序集的動態關鍵路徑多產品制造調度算法[J].計算機學報，2011（2）：406-412.

[12]Mohammad， Raeesi N， Ziad.Kobti. A memetic algorithm for job shop scheduling using a critical-path-based local search heuristic[J]. Memetic computing，2012（3）：231-245.