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

(三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院，湖北 宜昌　443002)

?

基于順序相關(guān)調(diào)整時(shí)間的FJSP與設(shè)備維護(hù)計(jì)劃集成優(yōu)化*

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

(三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院，湖北 宜昌443002)

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

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

0引言

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

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

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

1問題描述

1.1設(shè)備維護(hù)問題描述

設(shè)備的預(yù)防維護(hù)計(jì)劃需確定間隔多久進(jìn)行一次預(yù)防維護(hù)(即預(yù)防維護(hù)周期)和進(jìn)行一次預(yù)防維護(hù)所需的時(shí)間。

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

(1)

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

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

(2)

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

1.2FJSP-SDST問題描述

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

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

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

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

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

3兩階段算法的設(shè)計(jì)

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

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

圖1　算法流程圖

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

(1)編碼

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

圖2編碼示例

(2)FJSP-SDST解碼

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

(3)交叉

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

圖3　交叉示例

(4)變異

采用基于工序編碼的兩點(diǎn)變異方式，隨機(jī)選取工序序列兩個(gè)位置的工序號交換位置，保持所有工件工序分配的機(jī)器不變，如圖4所示，把工序序列中位置3的工序4與位置5的工序3交換，同時(shí)交換兩個(gè)工序?qū)?yīng)的機(jī)器，得到子代。

圖4　變異示例

3.2第二階段：維護(hù)計(jì)劃的概率插入

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

圖5　前移式和后移式維護(hù)計(jì)劃示例

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

STEP4：判斷當(dāng)前工序是否是工序序列中的最后一道工序，如果是此子程序結(jié)束，計(jì)算總完工時(shí)間；否則，更新當(dāng)前工序?yàn)楣ば蛐蛄兄械南乱粋€(gè)工序，轉(zhuǎn)STEP2。

4實(shí)例驗(yàn)證

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

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

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

表1　每道工序的可選設(shè)備及加工時(shí)間

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

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

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

表3　設(shè)備預(yù)防維護(hù)的相關(guān)參數(shù)

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

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

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

表4　計(jì)算結(jié)果對比

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

5結(jié)論

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

[參考文獻(xià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)整時(shí)間的作業(yè)車間調(diào)度與預(yù)防性維修集成方法[J]. 西安交通大學(xué)學(xué)報(bào),2015, 49(6): 16-20.

[3] 宋文家, 張超勇, 尹勇, 等. 基于多目標(biāo)混合殖民竟?fàn)幩惴ǖ脑O(shè)備維護(hù)與車間調(diào)度集成優(yōu)化[J]. 中國機(jī)械工程,2015,25(11): 1478-1487.

[4] 李苗群.基于可靠性的設(shè)備預(yù)防性維護(hù)策略研究[D].西安: 西安電子科技大學(xué), 2011.

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

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

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

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

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

[15] 高亮, 張國輝, 王曉娟. 柔性作業(yè)車間調(diào)度智能算法及其應(yīng)用[M]. 武漢:華中科技大學(xué)出版社, 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

*基金項(xiàng)目：湖北省教育廳科學(xué)技術(shù)研究項(xiàng)目(Q20151206)

作者簡介：查靚(1978—)，女，湖北松滋人，三峽大學(xué)講師，博士，研究方向?yàn)樯a(chǎn)調(diào)度及智能算法應(yīng)用，制造系統(tǒng)建模仿真優(yōu)化等，(E-mail)maria_zhajing@hotmail.com。

中圖分類號：TH166;TG659

文獻(xiàn)標(biāo)識碼：A