基于關(guān)鍵鏈的需求視窗技術(shù)在柔性車間調(diào)度中的應(yīng)用

代大齊

摘 要：針對(duì)柔性車間調(diào)度問題，運(yùn)用需求視窗來表征其加工環(huán)境的模糊性及市場(chǎng)需求，并建立滿意度函數(shù)，作為車間調(diào)度模型的目標(biāo)函數(shù)。為了應(yīng)對(duì)調(diào)度過程的復(fù)雜性，運(yùn)用多色集合建立基本信息約束圍道矩陣來改進(jìn)遺傳算法，結(jié)合關(guān)鍵鏈，提出基于關(guān)鍵鏈的需求視窗技術(shù)。通過仿真實(shí)例驗(yàn)證了給出的調(diào)度方法的可行性和有效性。

關(guān)鍵詞：柔性車間調(diào)度;關(guān)鍵鏈;需求視窗;遺傳算法

中圖分類號(hào)：TH165文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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

生產(chǎn)車間調(diào)度問題是公認(rèn)的強(qiáng)NP-hard[1]問題，具有重要的實(shí)際意義和理論價(jià)值。柔性作業(yè)車間調(diào)度問題（Flexible Job-Shop Scheduling Problem，F(xiàn)JSP）的研究擴(kuò)展了經(jīng)典作業(yè)調(diào)度，是當(dāng)前車間調(diào)度問題研究的熱點(diǎn)之一[2]。通過相關(guān)算法及改進(jìn)算法解決調(diào)度問題是較為常用的一種手段[3-5]。趙詩奎提出一種融合改進(jìn)鄰域結(jié)構(gòu)的混合算法[6]，石小秋等提出遺傳雜草算法[7]等用于柔性車間調(diào)度。目前，在對(duì)FJSP的研究上，單一調(diào)度的針對(duì)性應(yīng)用研究較多，而對(duì)于FJSP的復(fù)雜性，大多沒有進(jìn)行有效的分類、簡(jiǎn)化處理，且優(yōu)化出的調(diào)度方案通用性、實(shí)用性不強(qiáng)。

本文在分析柔性調(diào)度技術(shù)、方法的基礎(chǔ)上，結(jié)合實(shí)際情況，運(yùn)用關(guān)鍵鏈簡(jiǎn)化復(fù)雜的FJSP系統(tǒng)，以控制視窗建立針對(duì)模糊環(huán)境的滿意度函數(shù)，將關(guān)鍵鏈和需求視窗技術(shù)相結(jié)合，并運(yùn)用多色集合（Polychromatic Sets，PS）[8-9]建立基本信息圍道矩陣改進(jìn)遺傳算法來解決柔性車間的調(diào)度問題。

1 調(diào)度關(guān)鍵鏈的確立

在調(diào)度中存在眾多加工瓶頸，瓶頸因素[10]就組成了關(guān)鍵鏈條[11-12]。其中有兩個(gè)重要約束：一是機(jī)械約束，即關(guān)鍵設(shè)備;二是時(shí)間約束，即關(guān)鍵時(shí)序。

2 需求視窗與滿意度函數(shù)

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

有時(shí)調(diào)度關(guān)鍵鏈有多條，那么滿意度函數(shù)為（2）式，也是目標(biāo)函數(shù)。

3 仿真實(shí)例

某柔性車間，生產(chǎn)5種產(chǎn)品，其加工工序時(shí)間如表1所示。

表1中，括號(hào)外為實(shí)際加工時(shí)間，括號(hào)內(nèi)為加工的上下界時(shí)間，也可看作是市場(chǎng)期望的正常的加工時(shí)間及期望的下界和上界，當(dāng)然也可以看作是實(shí)際生產(chǎn)車間的模糊加工環(huán)境。

本例從機(jī)械設(shè)備和時(shí)間約束綜合考慮確定調(diào)度關(guān)鍵為設(shè)備M3#和M2#，并組成關(guān)鍵鏈，即M3#→M2#，關(guān)鍵鏈組成為2臺(tái)設(shè)備，條數(shù)只有一條。運(yùn)用PS理論建立約束圍道矩陣以有利于最優(yōu)解的生成，PS建立的是基于基本信息的圍道約束矩陣，由實(shí)際的柔性車間的基本信息生成。

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

圖2為調(diào)度方案，1-1表示第一個(gè)工件的第一道工序，對(duì)應(yīng)長(zhǎng)度為加工時(shí)長(zhǎng)，相同工件為同一個(gè)顏色，其他類推。

4 實(shí)例分析

采用的是5×5×5案例，即5種類型的工件，工序數(shù)最大的為5道工序，在5臺(tái)設(shè)備上加工。與普通車間調(diào)度的區(qū)別是，該調(diào)度車間為柔性車間，設(shè)備都具備多工序加工能力，屬于多功能機(jī)床，如機(jī)床M3#具備11道工序的加工能力。實(shí)例中柔性加工車間調(diào)度問題具有代表性，解決方案的最終運(yùn)行結(jié)果也是有效、可行的。

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

在關(guān)鍵鏈技術(shù)的運(yùn)用上，本例僅選擇了綜合優(yōu)先級(jí)高的M2#、M3#機(jī)床組成關(guān)鍵鏈，這是由于實(shí)例中加工機(jī)床、工序數(shù)目較少，無須挑選更多關(guān)鍵設(shè)備或工序組建關(guān)鍵鏈。當(dāng)遇見較為復(fù)雜的柔性車間時(shí)，關(guān)鍵鏈可以更長(zhǎng)、更多。在運(yùn)用時(shí)，人的因素尤為重要，人需要結(jié)合實(shí)際情況在關(guān)鍵鏈長(zhǎng)短、條件上進(jìn)行適當(dāng)判別。

實(shí)例主要基于M3#、M2#這兩臺(tái)關(guān)鍵機(jī)床的市場(chǎng)需求（同時(shí)也可以看成是模糊性加工環(huán)境或人為意愿要求）進(jìn)行優(yōu)化，其關(guān)注點(diǎn)側(cè)重于解決確立出來的關(guān)鍵機(jī)床。從運(yùn)行結(jié)果來看，在經(jīng)過近80代的迭代后，這兩臺(tái)機(jī)床的平均滿意度達(dá)到了66%的最高值，滿足了市場(chǎng)對(duì)關(guān)鍵機(jī)床的期望。

5 結(jié)論

通過仿真實(shí)例說明了采用基于關(guān)鍵鏈技術(shù)的需求視窗在柔性車間調(diào)度中應(yīng)用的可行性。同時(shí)還應(yīng)看到的是，以結(jié)合需求視窗滿意度為目標(biāo)函數(shù)的調(diào)度，調(diào)度結(jié)果是根據(jù)市場(chǎng)需求或模糊加工環(huán)境得出的，更能反映柔性車間生產(chǎn)的實(shí)際情況，調(diào)度更具有實(shí)際意義。

參考文獻(xiàn)：

[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]彭乘風(fēng)，陳慶新，毛寧，等.具有無序工序生產(chǎn)特征的混合柔性 流水車間在線調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng)，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ìn)人工蜂群算法求解分布式柔性作業(yè)車間調(diào)度問題[J].控制與決策，2019（12）：2527-2536.

[6]趙詩奎.柔性作業(yè)車間調(diào)度的改進(jìn)鄰域結(jié)構(gòu)混合算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2018（12）：3060-3072.

[7]石小秋，李炎炎，鄧丁山，等.基于自適應(yīng)變級(jí)遺傳雜草算法的FJSP研究[J].機(jī)械工程學(xué)報(bào)，2019（6）：223-232.

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

[9]傅衛(wèi)平，劉冬梅，來春為，等.基于多色集合的改進(jìn)遺傳算法求解多品種柔性調(diào)度問題[J].計(jì)算機(jī)集成制造系統(tǒng)，2011（5）：1004-1010.

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

[11]謝志強(qiáng)，楊靜，周勇，等.基于工序集的動(dòng)態(tài)關(guān)鍵路徑多產(chǎn)品制造調(diào)度算法[J].計(jì)算機(jī)學(xué)報(bào)，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.