基于順序相關調整時間的FJSP與設備維護計劃集成優化*

查　靚，金　花，潘志成，袁慶松

(三峽大學 機械與動力學院，湖北 宜昌　443002)

?

基于順序相關調整時間的FJSP與設備維護計劃集成優化*

查靚，金花，潘志成，袁慶松

(三峽大學 機械與動力學院，湖北 宜昌443002)

摘要：為了能根據設備的實際工作時間制定維護計劃，以及利用設備空閑時間進行預防維護，研究了考慮順序相關調整時間(SDST)的柔性作業車間調度(FJSP)和設備維護計劃的集成優化問題。以完工時間最小為目標，建立FJSP-SDST與不等周期設備維護的集成優化模型。提出了基于遺傳優化的兩階段算法，先得到基礎FJSP-SDST的調度方案，然后在設備的可靠度低于閾值時安排不等周期實時維護計劃，以一定的概率在基礎調度方案中的空閑時間段插入維護時間，從而得到集成方案。針對某實例的計算結果表明，考慮順序相關調整時間的調度方案的總完成時間優于原調度方案的總完成時間，集成優化方案的總完成時間優于定期維護方案的總完成時間。

關鍵詞：柔性作業車間；車間調度；設備維護；順序相關調整時間

0引言

在實際生產系統運行過程中，調度計劃的實施取決于設備的穩定性，設備故障會對計劃執行所產生的不良影響；簡單依據歷史經驗安排的設備維護計劃容易導致過度維護，浪費寶貴的人力和相關資源。因此，為實現生產調度與設備維護之間的有效平衡，最大化企業的整體利益，必須將兩者進行集成優化。

在最近少數幾篇關于生產調度和設備維護的集成研究中，Khamseh, A[1]等研究了流水車間的成組調度問題與預防維護的集成優化，文章僅對相似的并行機系統進行了研究。喻明讓[2]等的研究針對的是一般作業車間的調度問題與預防維護的集成優化，沒有考慮修復非新的不等周期設備維護情況。宋文家[3]等的研究針對柔性作業車間，利用改進加權TOPSIS方法和混合殖民競爭算法求解集成優化方案，但該研究沒有考慮調整時間，使得設備可靠度比實際偏低，從而造成提前安排設備維護計劃，降低了設備利用率。因此在FJSP和設備維護計劃的集成優化研究中，有必要單獨考慮順序相關調整時間。

基于上述分析，本文以完工時間最小為目標，基于威爾分布的故障密度函數和不等周期實時維護策略，建立了考慮順序相關調整時間的FJSP與設備維護計劃集成優化模型，設計了基于遺傳優化的兩階段算法進行求解。針對某實例的計算結果表明該模型及算法的有效性，得到的集成優化方案不僅能夠保證生產的連續進行，而且具有更好的生產效率。

1問題描述

1.1設備維護問題描述

設備的預防維護計劃需確定間隔多久進行一次預防維護(即預防維護周期)和進行一次預防維護所需的時間。

設備的可靠度是指設備在壽命周期內完成規定功能的能力。隨著設備的運轉，當可靠度低于一定的閾值時進行維護以避免出現故障造成停機。設備可靠度的計算與其故障概率密度函數有關，故障概率密度是指機器在單位時間發生故障的概率，由于在機械加工車間使用的大多是機電類設備，故障概率概率更接近威爾分布[4]，依據文獻[5]，設備在運行時刻t的故障概率密度函數f(t)如式(1)所示：

(1)

其中，t代表設備運轉的第t時刻，β為形狀參數，不同的β決定不同的分布曲線形狀，η為尺度參數，二者都與設備使用時間t無關。

根據式(1)設備在t時刻的可靠度R(t)如下式(2)計算[5]：

(2)

本文假設設備每次進行預防維護所需時間相同，在實際應用中可依據各設備歷史運行數據進行確定。

1.2FJSP-SDST問題描述

FJSP的一般描述為：n個工件在m臺設備上加工，每個工件的加工有k道工序，工序順序是確定的[7]。FJSP具有加工路徑柔性的特點，每道工序可以在多臺不同的設備上加工，但使用的設備不同加工時間也不同。因此，FJSP包含兩個子問題：確定工序的設備選擇和確定各設備上工序的加工順序[8-10]。

當某臺設備上的加工產品改變時，一般需要卸下已加工完成的工件、除屑、更換工具、夾具或模具、裝載待加工工件等，所耗費的時間為調整時間[11]。此時設備處于停機狀態，在維修計劃中調整時間不應計入設備的工作時間，此外，該調整時間與相鄰工序之間的相似性有關，加工順序會影響調整時間的長短，進而影響整個加工完成時間。維修計劃的插入會影響工件在設備上開始加工的時間和完工時間，因此需要對FJSP-SDST與設備維護計劃進行集成優化。

2數學模型的建立

建立FJSP-SDST與設備維護計劃的集成優化模型如下：

(3)

s.t.stij+x(ij)l×p(ij)l≤etij

(4)

etij≤sti(j+1)

(5)

etij≤Cmax

(6)

(7)

etij×x(ij) l+tl×q(ij)(hd)l×g(ij)(hd)l+tz(ij)(hd)l×g(ij)(hd)l≤

sthd×xhdl+L(1-g(ij)(hd)l)

(8)

Rl(t)≤Rl,min

(9)

其中，i和h代表工件序號，i,h=(1,2,…,n)；Kj表示工件j加工的總工序數；j和d表示工序序號；l表示設備序號，l=(1,2,…,m)；p(ij)l表示工件i的第j道工序在設備l上的加工時間；stij表示工件i的第j道工序加工開始時間(不包括調整時間)；etij表示工件i的第j道工序加工結束時間；tz(ij)(hd)l表示設備l先加工工件i的第j道工序接著加工工件h的第d道工序的調整時間；tl為機器l的維護時間；Ci表示工件i的完工時間；Cmax表示加工的最大完工時間；L為一個極大的正數；變量xijl=1表示工件i的第j道工序在設備l上加工，否則xijl=0；g(ij)(hd)l=1表示在設備l連續加工工件i的第j道工序和工件h的第d道工序，否則g(ij)(hd)l=0；q(ij)(hd)l=1表示在設備l加工工件i的第j道工序和工件h的第d道工序之間需要維護，否則q(ij)(hd)l=0。

目標函數(3)表示追求總完工時間最短，約束條件(4)和(5)表示同一工件加工順序符合工序的先后順序約束；式(6)表示每個工件的完工時間不得超過總完工時間；式(7)表示同一時刻同一工序只能在一臺設備上加工；式(8)表示同一臺設備的上道工序完工時間加上維護時間和調整時間小于下道工序的加工開始時間；式(9)表示設備的可靠度應小于其可靠度閾值。

3兩階段算法的設計

由于該集成優化問題為NP-難問題，直接求解非常困難，因此設計了一種基于遺傳優化的兩階段算法。算法流程如圖1所示。

初始化種群后，第一階段不考慮維護計劃利用遺傳算法的交叉、變異算子得到多個基礎FJSP-SDST調度方案。第二階段，基于基礎調度方案，根據機器可靠度模型和不等周期維護規則生成維護計劃，以一定的概率將維護時間插入機器加工的空閑時間，得出對應的多個調度維護集成方案，計算適應度值，保留精英解，然后根據輪盤賭規則選擇若干個個體截取FJSP-SDST部分復制到下一代種群，算法反復搜索直到滿足停止條件，此時輸出保留在外部的精英解即為集成優化方案。

圖1　算法流程圖

3.1第一階段：基礎FJSP-SDST調度方案的生成

(1)編碼

由于FJSP同時需要確定工序的設備選擇和確定各設備上工序的加工順序，因此采用基于工序和機器的編碼方法。個體由兩部分組成，前半部分為工序編碼，用來確定工序的加工先后順序，每道工序用對應工件號表示；后半部分為機器編碼，用來選擇每道工序的加工機器，用機器號表示。每個編碼序列即為FJSP的一個可行解。假設某柔性作業車間有3臺設備，待加工4個工件，每個工件包含2道工序。如圖2所示，工序序列為(O11O41O21O12O31O42O22O32)，機器上的加工序列為：機器1(O41O42)，機器2(O12O31O22)，機器3(O11O21O32)。Oij表示工件i的第j道工序。

圖2編碼示例

(2)FJSP-SDST解碼

基于FJSP-SDST的問題模型，需要在安排工件加工開始之前確定順序相關調整時間。當工序為設備上第1道工序或者工序與該設備上的緊前工序屬同一工件時，工序在機器上的順序相關調整時間為0。具體解碼規則：首先判斷當前工序號分別為工件和設備上的第幾道工序；然后計算當前工序所屬工件的緊前工序和設備上的緊前工序完工時間的差值Δt，若Δt=0，則調整開始時間任取兩者之一，若0<Δt≤tz(ij)(hd)l,則調整開始時間為設備上緊前工序的完工時間，若Δt>tz(ij)(hd)l，則調整開始時間為工件緊前工序的完工時間減去調整時間。工件或機器加工開始時間為調整開始時間加上調整時間，工件或設備加工結束時間為加工開始時間加上工序在設備上的加工時間。依次類推，直到工序序列的工件號安排完成，解碼過程結束，得到基礎FJSP-SDST的總完工時間。

(3)交叉

為了保證交叉后得到的子代仍是可行解，采用基于工序編碼的交叉方法，即交叉操作只改變父代中的工序序列，保留工序對應的機器到子代。交叉過程如圖3所示為：首先，將所有工件隨機分成兩個集合A1和A2(圖3中A1包含工件1和3，A2包含工件2和4)；然后，復制父代1包含在A1中(工件1和3)的工序序列到子代1，復制父代2包含在A2中(工件2和4)的工序序列到子代2，保留它們的位置和順序，復制父代1包含在A1中(工件1和3)的工序序列到子代2，復制父代2包含在A2中(工件2和4)的工序序列到子代1，保留它們的順序。

圖3　交叉示例

(4)變異

采用基于工序編碼的兩點變異方式，隨機選取工序序列兩個位置的工序號交換位置，保持所有工件工序分配的機器不變，如圖4所示，把工序序列中位置3的工序4與位置5的工序3交換，同時交換兩個工序對應的機器，得到子代。

圖4　變異示例

3.2第二階段：維護計劃的概率插入

經過第一階段，得到了若干個基礎FJSP-SDST調度方案，明確了每臺設備上工件加工的順序和工時，可計算出設備的可靠度，當可靠度到達閾值時，需要安排維護任務，如果此時設備正好是空閑的，且空閑時間大于維護時間，可直接插入維護計劃，但如果此時設備上正在執行加工任務，有兩種選擇：①提前進行維護保養，再執行當前加工任務，稱為前移式；②等到當前加工結束后再進行維護保養，稱為后移式，但如果加工時間較長導致維護周期太長，任務結束時設備損耗非常嚴重，甚至出現故障。如圖5所示，虛線處是設備可靠度達到閾值的時刻，設備1的維護計劃采用的是后移式，設備2的維護計劃是前移式，很好的利用設備的空閑時間來進行維修保養，縮短總的完成時間。

圖5　前移式和后移式維護計劃示例

STEP1：取一個基本的FJSP-SDST方案。初始化，設置當前工序Oij為工序序列中的第一個工序，維護次數el=0，(l=1,2,...m)，以及初始可靠度閾值。

STEP4：判斷當前工序是否是工序序列中的最后一道工序，如果是此子程序結束，計算總完工時間；否則，更新當前工序為工序序列中的下一個工序，轉STEP2。

4實例驗證

某柔性作業車間包含6臺設備，加工6個工件，每個工件包含6道工序，車間原來采用的維護方案是每隔35個時間單位進行一次維護，調度維護方案的甘特圖如圖6所示，黃色部分為加工時間，紅色部分為設備維護時間，該方案的總完工時間為128個時間單位，維護次數14次。

圖6　未優化的原始調度維護方案甘特圖

通過對加工過程的進一步分析，可分離出每道工序的實際加工時間和順序相關調整時間，如表1和表2所示。

表1　每道工序的可選設備及加工時間

基于MATLAB R2012b平臺開發實現本算法，并進行多次仿真實驗。

首先僅運行第一階段程序求解考慮順序相關調整時間后的柔性作業調度問題(FJSP-SDST)，算法相關參數設置如下：種群規模N=100,迭代次數為50，交叉概率Pc=0.8，變異概率Pm=0.05，維護方案仍是每隔35個時間單位進行一次維護，得到優化后的調度維護方案的甘特圖如圖7所示，藍色為調整時間，此時總完工時間為117，比不考慮順序調整時間的原始方案的總完工時間減少11個時間單位，表明將每道工序的實際加工時間和順序調整時間分離，進行基于順序相關調整時間的調度優化有助于得到完工時間更短的方案。

圖7　考慮順序相關調整時間的調度維護優化方案甘特圖

表3　設備預防維護的相關參數

采用本文設計的兩階段算法計算得到集成優化方案，甘特圖如圖8所示。例如設備6在第26個時間單位時，可靠度降到閾值，需要進行維護，此時該設備上正在進行工件1的第3道工序的加工，將此維護任務提前到該工序之前，可利用生產空閑時間進行維護。又如設備4在28個單位時間時，需要進行維護，此時該設備上正在進行工件3的第3道工序的加工，該工序完工后可靠度為0.843，仍在安全范圍內，將該維護任務推后在該工序完成后的空閑時間再進行。

圖8　FJSP-SDST與設備維護計劃集成優化方案甘特圖

集成優化方案的最大完工時間為112個時間單位，維護次數8次。如表4所示，該集成優化方案與未優化的原始方案相比，總完工時間減少16個時間單位，維護次數減少6次；與僅考慮了順序相關調整時間的調度維護優化方案(FJSP-SDST)相比，總完工時間減少5個時間單位，維護次數減少6次。

表4　計算結果對比

本文所提的調度和設備維護集成優化方法由于充分利用了調度方案中的空閑時間進行預防維護，因此有助于提高了生產效率和機器使用率。

5結論

本文針對FJSP-SDST與集成優化研究問題，建立了以最大完工時間最小為目標的調度與維護集成優化模型，設計了基于遺傳優化的兩階段算法，在FJSP-SDST調度基礎上，依據設備可靠度模型和不等周期維護規則，利用前移式和后移式在設備空閑時間段插入維護計劃。實例計算表明，考慮順序相關調整時間有助于找到完工時間更短的調度方案，生產調度與設備維護計劃集成優化有助于利用調度方案中的空閑時間進行預防維護，將加工時間和調整時間分離有助于更準確的計算設備累積運行時間及其可靠度，進一步減少預防維護的次數。考慮順序相關調整時間的FJSP與設備維護集成優化方案既保證了連續生產，也減少了因不科學的設備維護計劃造成的生產資源浪費，大大提高了機器利用率和生產效率。

[參考文獻]

[1] Khamseh A , Jolai F, Babaei M. Integrating sequence-dependent group scheduling problem and preventive maintenance in flexible flow shops[J]. International Journal of Advanced Manufacturing Technology. 2014, 77(4): 173-185.

[2] 喻明讓, 張英杰, 陳琨,等. 考慮調整時間的作業車間調度與預防性維修集成方法[J]. 西安交通大學學報,2015, 49(6): 16-20.

[3] 宋文家, 張超勇, 尹勇, 等. 基于多目標混合殖民竟爭算法的設備維護與車間調度集成優化[J]. 中國機械工程,2015,25(11): 1478-1487.

[4] 李苗群.基于可靠性的設備預防性維護策略研究[D].西安: 西安電子科技大學, 2011.

[5] 魏永合,劉雪麗,牛保國. 基于故障預測的預防性維修策略優化模型[J]. 組合機床與自動化加工技術,2015(7):91-94.

[6] 劉繁茂.面向故障過程的多設備可靠性分析與維修決策 [D]. 武漢:華中科技大學, 2010.

[7] 李傳鵬,王桂從,崔煥勇. 柔性作業車間調度問題研究現狀及發展趨勢[J]. 組合機床與自動化加工技術,2012(11): 109-112.

[8] Wang Ling, Zhou Gang, Xu Ye, et al. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology. 2012, 50(4): 303-315.

[9] 吳秀麗, 張志強, 杜彥華, 等. 改進細菌覓食算法求解柔性作業車間調度問題[J]. 計算機集成制造系統,2015, 21(5): 1262-1270.

[10] 趙詩奎. 求解柔性作業車間調度問題的兩級領域搜索混合算法[J]. 機械工程學報, 2015, 51(14): 175-184.

[11] Allahverdi A, Ng C T, Cheng T C E, et al. A survey of scheduling problems with setup times or costs [J]. European Journal of Operational Research, 2008, 187(3):985-1032.

[12] Ruiz R, Maroto C，Alcaraz J. Solving the flow-shop scheduling problem with sequence dependent setup times using advanced metaheuristics[J]. European Journal of Operational Research. 2005,165(1): 34-54.

[13] 徐建有, 董乃群, 顧樹生. 帶有順序相關調整時間的多目標流水車間調度問題[J]. 計算機集成制造系統,2013, 19(12): 3170-3176.

[14] 周亞勤, 李蓓智, 楊建國. 調整時間與工序順序相關的Job shop調度優化方法研究[J]. 中國機械工程,2005,16(10): 914-918.

[15] 高亮, 張國輝, 王曉娟. 柔性作業車間調度智能算法及其應用[M]. 武漢:華中科技大學出版社, 2012.

(編輯趙蓉)

Integrated Optimization of Flexible Job Shop Scheduling Problem and Equipment Maintenance Plan with Sequence-dependent Setup Times

ZHA Jing,JIN Hua,PAN Zhi-cheng,YUAN Qing-song

(College of Mechanical & Power Engineering, Three Gorges University, Yichang Hubei 443002, China)

Abstract：In order to draw up an equipment maintenance plan based on actual working time and free time, the paper studied the integrated optimization of flexible job shop scheduling problem (FJSP) and equipment maintenance plan with sequence-dependent setup times (SDST). The object of the integrated optimization model is to pursue the minimum of makespan. The paper proposed a two-stage algorithm based on the genetic algorithm to solve the problem. Firstly generated basic FJSP-SDST schedules. Secondly probabilistically arranged the unequal periodic equipment maintenance at the equipment’s free time if the reliability of the equipment is below the threshold value. Then obtained an integrated plan. The optimization result of a practical example showed that the makespan of FJSP-SDST was less than the original one and the makespan of the integrated optimization was less than the makespan of equipment maintenance at regular intervals.

Key words：flexible job shop; shop scheduling; equipment maintenance; sequence-dependent setup time

文章編號：1001-2265(2016)05-0155-06

DOI:10.13462/j.cnki.mmtamt.2016.05.042

收稿日期：2016-12-11；修回日期：2016-01-12

*基金項目：湖北省教育廳科學技術研究項目(Q20151206)

作者簡介：查靚(1978—)，女，湖北松滋人，三峽大學講師，博士，研究方向為生產調度及智能算法應用，制造系統建模仿真優化等，(E-mail)maria_zhajing@hotmail.com。

中圖分類號：TH166;TG659

文獻標識碼：A