基于順序相關調(diào)整時間的FJSP與設備維護計劃集成優(yōu)化*

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

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

?

基于順序相關調(diào)整時間的FJSP與設備維護計劃集成優(yōu)化*

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

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

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

關鍵詞：柔性作業(yè)車間；車間調(diào)度；設備維護；順序相關調(diào)整時間

0引言

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

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

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

1問題描述

1.1設備維護問題描述

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

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

(1)

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

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

(2)

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

1.2FJSP-SDST問題描述

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

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

2數(shù)學模型的建立

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

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

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

3兩階段算法的設計

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

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

圖1　算法流程圖

3.1第一階段：基礎FJSP-SDST調(diào)度方案的生成

(1)編碼

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

圖2編碼示例

(2)FJSP-SDST解碼

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

(3)交叉

為了保證交叉后得到的子代仍是可行解，采用基于工序編碼的交叉方法，即交叉操作只改變父代中的工序序列，保留工序?qū)臋C器到子代。交叉過程如圖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交換，同時交換兩個工序?qū)臋C器，得到子代。

圖4　變異示例

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

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

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

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

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

4實例驗證

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

圖6　未優(yōu)化的原始調(diào)度維護方案甘特圖

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

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

基于MATLAB R2012b平臺開發(fā)實現(xiàn)本算法，并進行多次仿真實驗。

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

圖7　考慮順序相關調(diào)整時間的調(diào)度維護優(yōu)化方案甘特圖

表3　設備預防維護的相關參數(shù)

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

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

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

表4　計算結果對比

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

5結論

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

[參考文獻]

[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] 喻明讓, 張英杰, 陳琨,等. 考慮調(diào)整時間的作業(yè)車間調(diào)度與預防性維修集成方法[J]. 西安交通大學學報,2015, 49(6): 16-20.

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

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

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

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

[7] 李傳鵬,王桂從,崔煥勇. 柔性作業(yè)車間調(diào)度問題研究現(xiàn)狀及發(fā)展趨勢[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] 吳秀麗, 張志強, 杜彥華, 等. 改進細菌覓食算法求解柔性作業(yè)車間調(diào)度問題[J]. 計算機集成制造系統(tǒng),2015, 21(5): 1262-1270.

[10] 趙詩奎. 求解柔性作業(yè)車間調(diào)度問題的兩級領域搜索混合算法[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] 徐建有, 董乃群, 顧樹生. 帶有順序相關調(diào)整時間的多目標流水車間調(diào)度問題[J]. 計算機集成制造系統(tǒng),2013, 19(12): 3170-3176.

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

[15] 高亮, 張國輝, 王曉娟. 柔性作業(yè)車間調(diào)度智能算法及其應用[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—)，女，湖北松滋人，三峽大學講師，博士，研究方向為生產(chǎn)調(diào)度及智能算法應用，制造系統(tǒng)建模仿真優(yōu)化等，(E-mail)maria_zhajing@hotmail.com。

中圖分類號：TH166;TG659

文獻標識碼：A